4.3 Stacks and Queues2Data Structures and Data TypesData types•Set of values.•Set of operations on those values.•Some are built in to Java: int, double, char, . . .•Most are not: Complex, Picture, Charge, Stack, Queue, Graph, . . .Data structures.•Represent data. •Represent relationships among data.•Some are built in to Java: arrays, String, . . .•Most are not: linked list, circular list, tree, sparse array, graph, . . .Design challenge for every data type: What data structure to use?•Requirement 1: Space usage.•Requirement 2: Time usage for data-type methodsthis lecturethis lecture TSP next lecture3CollectionsFundamental data types.•Set of operations (add, remove, test if empty) on generic data.•Intent is clear when we insert.•Which item do we remove?Stack. (this lecture)•Remove the item most recently added. •Ex: cafeteria trays, Web surfing.Queue. (see text)•Remove the item least recently added.•Ex: Registrar's line.Symbol Table. (next lecture)•Remove item with a given key.•Ex: Phone bookFIFO = "first in first out"LIFO = "last in first out"4Pushdown Stacks5Stack APIofbestthewasittimesofbestthewasitofbestthewasitbestthewasitpush pop popStack Client Example 1: Reverse6public class Reverse{ public static void main(String[] args) { StackOfStrings stack = new StackOfStrings(); while (!StdIn.isEmpty()) stack.push(StdIn.readString()); while (!stack.isEmpty()) StdOut.print(stack.pop()); StdOut.println(); }}% more tiny.txtit was the best of times% java Reverse tiny.txttimes of best the was ittimesofbestthewasitstack contents whenStdIn is emptyStack Client Example 2: Test Client7public static void main(String[] args){ StackOfStrings stack = new StackOfStrings(); while (!StdIn.isEmpty()) { String item = StdIn.readString(); if (item.compareTo("-") != 0) stack.push(item); else System.out.print(stack.pop()); } System.out.println();}% more test.txtto be or not to - be - - that - - - is% java StackOfStrings < test.txtto be not that or betonotorbetostack contents just before first pop() operationStack Client Example 3: Balanced Parentheses8( ( ( a + b ) * d ) + ( e * f ) )( ) ( ) ( ) ( ) pushpushpushpushpoppoppoppopStack Client Example 3: Balanced Parentheses9public class Balanced{ public static void main(String[] args) { StackOfStrings stack = new StackOfStrings(); while (!StdIn.isEmpty()) { String item = StdIn.readString(); if (item.compareTo("(") == 0) stack.push(item); if (item.compareTo(")") == 0) { if (stack.isEmpty()) { StdOut.println(“Not balanced”); return; } stack.pop(); } } if (!stack.isEmpty()) StdOut.println(“Not balanced”); else StdOut.println(“Balanced”); }}% java Balanced( ( ( a + b ) * d ) + ( e * f ) )Balanced% java Balanced( ( a + b ) * d ) + ( e * f ) )Not balanced10Stack: Array ImplementationArray implementation of a stack.•Use array a[] to store N items on stack.•push() add new item at a[N].•pop() remove item from a[N-1].public class ArrayStackOfStrings{ private String[] a; private int N = 0; public ArrayStackOfStrings(int max) { a = new String[max]; } public boolean isEmpty() { return (N == 0); } public void push(String item) { a[N++] = item; } public String pop() { return a[--N]; }}notorbetostack contents after4th push() operationto be or notNa[0] a[1] a[2] a[3]PROBLEM: How big to make array? (Stay tuned.)Temporary solution: Make client provide capacity.poppush11Array Stack: TracepushpopTEQ on StacksQ. Can we always insert pop commands (-) to make strings come out sorted?Ex 1: 6 5 4 3 2 1 - - - - - Ex 2: 1 - 2 - 3 - 4 - 5 - 6 -Ex 3: 4 1 - 3 2 - - - 6 5 - -1213Array Stack: PerformanceRunning time. Push and pop take constant time. !Memory. Proportional to client-supplied capacity, not number of items. "Problem. •API does not call for capacity (never good to change API)•Client might have multiple stacks •Client might not know what capacity to use (depends on its client)Challenge. Stack implementation where space use is not fixed ahead of time.14Linked Lists15Sequential vs. Linked Data StructuresSequential data structure. Put object one next to another.•TOY: consecutive memory cells.•Java: array of objects.Linked data structure. Include in each object a link to the another one.•TOY: link is memory address of next object.•Java: link is reference to next object.Key distinctions.•Array: arbitrary access, fixed size.•Linked list: sequential access, variable size.Linked structures.•Not intuitive, overlooked by naive programmers•Flexible, widely used method for organizing data"Carol"nullC0C1--C2C3"Alice"CAC4C5--C6C7--C8C9"Bob"C0CACBvalueaddr"Alice""Bob"C0C1"Carol"-C2C3--C4C5--C6C7--C8C9--CACBvalueaddrarraylinked listget ith elementget next elementSingly-linked data structuresFrom the point of view of a particular object, all of these structureslook the same: Multiply linked structures: many more possibilities!16Sequential list (this lecture)Circular list (TSP)General caseRhoTree17Linked list.•Simplest linked structure.•A recursive data structure.•A item plus a pointer to another linked list (or empty list).•Unwind recursion: linked list is a sequence of items.Node data type.•A reference to a String.•A reference to another Node.Linked Listspublic class Node{ private String item; private Node next;}Alice Bob Carolfirstitemnextspecial pointer value null terminates listConfusing point: Purpose of data structure is to represent data in a data type but, we also use data types to implement data structures18Building a Linked ListNode third = new Node();third.item = "Carol";third.next = null;Node second = new Node();second.item = "Bob";second.next = third;Node first = new Node();first.item = "Alice";first.next = second;"Carol"nullC0C1--C2C3"Alice"CAC4C5--C6C7--C8C9"Bob"C0CACB--CCCD--CECFValueaddrCarolitemnextthirdC0thirdmain memoryBobsecondCAsecondAlicefirstC4firstnull19Stack Push: Linked List Implementationsecond = first;first.item = item;first.next = second;first = new Node();best the was itfirstofsecondbest the was itfirstsecondbest the was itfirstsecondbest the was itfirst20Stack Pop: Linked List