Robert Sedgewick and Kevin Wayne • Copyright © 2005 • http://www.Princeton.EDU/~cos2262.6 Stacks and Queues2 Stacks and QueuesFundamental 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.! Remove the item most recently added.! Analogy: cafeteria trays, Web surfing.Queue.! Remove the item least recently added.! Analogy: Registrar's line.FIFO = "first in first out"LIFO = "last in first out"enqueuedequeuepoppush3Client, Implementation, InterfaceSeparate interface and implementation so as to:! Build layers of abstraction.! Reuse software.! Ex: stack, queue, symbol table.Interface: description of data type, basic operations.Client: program using operations defined in interface.Implementation: actual code implementing operations.4Client, Implementation, InterfaceBenefits.! Client can't know details of implementation !client has many implementation from which to choose.! Implementation can't know details of client needs !many clients can re-use the same implementation.! Design: creates modular, re-usable libraries.! Performance: use optimized implementation where it matters.Interface: description of data type, basic operations.Client: program using operations defined in interface.Implementation: actual code implementing operations.5StackStack operations.! push() Insert a new item onto stack.! pop() Delete and return the item most recently added.! isEmpty() Is the stack empty?poppushpublic static void main(String[] args) { StringStack stack = new StringStack(); while(!StdIn.isEmpty()) { String s = StdIn.readString(); stack.push(s); } while(!stack.isEmpty()) { String s = stack.pop(); System.out.println(s); }}a sample stack client6Stack Pop: Linked List Implementationbest the was itbest the was itfirst = first.next;best the was itreturn item;firstfirstfirstof item = first.item;7Stack Push: Linked List Implementationbest the was itsecondbest the was itbest the was itfirstofsecond = first;first.item = item;first.next = second;best the was itsecondfirst = new Node();firstsecondfirstfirst8Stack: Linked List Implementationpublic class StringStack { private Node first = null; private class Node { String item; Node next; } public boolean isEmpty() { return first == null; } public void push(String item) { Node second = first; first = new Node(); first.item = item; first.next = second; } public String pop() { String item = first.item; first = first.next; return item; } }"inner class"9Stack: Array ImplementationArray implementation of a stack.! Use array s[] to store N items on stack.! push() add new item at s[N].! pop() remove item from s[N-1].it was the best0 1 2 3 4 5 6 7 8 9s[]N10Stack: Array Implementationpublic class StringStack { private String[] s; private int N = 0; public StringStack(int capacity) { s = new String[capacity]; } public boolean isEmpty() { return N == 0; } public void push(String item) { s[N++] = item; } public String pop() { String item = s[N-1]; s[N-1] = null; N--; return item; } }garbage collector only reclaims memoryif no outstanding references11Stack Array Implementation: ResizingHow to resize array? Increase size of s[] by one if the array is full.Thrashing.! Increasing the size of an array involves copying all of the elementsto a new array.! Inserting N elements: time proportional to 1 + 2 + … + N " N2/2.N = 1 million ! infeasible.12How to resize array? Use repeated doubling: if s[] not big enough,create a new array of twice the size, and copy items.Consequence. Inserting N items takes time proportional to N (not N2). public StringStack() { this(8); } public void push(String item) { if (N >= s.length) resize(); s[N++] = item; } private void resize() { String[] dup = new String[2*N]; for (int i = 0; i < N; i++) dup[i] = s[i]; s = dup; }Stack Array Implementation: Dynamic Resizingno-argument constructordouble the size ofthe array13Stack Implementations: Array vs. Linked ListStack implementation tradeoffs. Can implement with either array orlinked list, and client can use interchangeably. Which is better?Array.! Most operations take constant time.! Expensive re-doubling operation every once in a while.! Any sequence of N operations (starting from empty stack)takes time proportional to N.Linked list.! Grows and shrinks gracefully.! Every operation takes constant time.! Uses extra space and time to deal with references."amortized" bound14QueueQueue operations.! enqueue() Insert a new item onto queue.! dequeue() Delete and return the item least recently added.! isEmpty() Is the queue empty?public static void main(String[] args) { StringQueue q = new StringQueue(); q.enqueue("Vertigo"); q.enqueue("Just Lose It"); q.enqueue("Pieces of Me"); q.enqueue("Pieces of Me"); System.out.println(q.dequeue()); q.enqueue("Drop It Like It's Hot"); while(!q.isEmpty()) System.out.println(q.dequeue());}15Dequeue: Linked List Implementationwas the best ofwas the best offirst = first.next;was the best ofreturn item;firstfirstfirstit item = first.item;lastlastlast16Enqueue: Linked List Implementationx = new Node();x.item = item;x.next = null;last = x;last.next = x;firstit was the bestxoflastfirstit was the bestlastit was the bestofit was the bestofxfirstlastxfirstlast17 Queue: Linked List Implementationpublic class StringQueue { private Node first; private Node last; private class Node { String item; Node next; } public boolean isEmpty() { return first == null; } public void enqueue(String item) { Node x = new Node(); x.item = item; x.next = null; if (isEmpty()) { first = x; last = x; } else { last.next = x; last = x; } } public String dequeue() { String item = first.item; first = first.next; return item; }} 18Queue: Array ImplementationArray implementation of a queue.! Use array q[] to store items on queue.! enqueue(): add new object at q[tail].! dequeue(): remove object from q[head].! Update head and tail modulo the capacity.the best of times0 1 2 3 4 5 6 7 8 9q[]headtailcapacity = 10Robert Sedgewick and Kevin Wayne • Copyright © 2005 • http://www.Princeton.EDU/~cos226Parameterized Data Types20Parameterized Data TypesWe implemented: StringStack, StringQueue.We also want: URLStack, CustomerQueue, etc?Attempt 1. Implement a separate stack class for each type.! Rewriting code is tedious and error-prone.! Maintaining
View Full Document
Unlocking...