Algorithms in Java, 4th Edition·Robert Sedgewick and Kevin Wayne·Copyright © 2009·February 7, 2010 10:14:00 AM1.3 Stacks and Queues‣stacks‣dynamic resizing‣queues‣generics‣iterators‣applications2Stacks and queuesFundamental data types.•Values: sets of objects•Operations: insert, remove, test if empty.•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.Ex: stack, queue, priority queue, symbol table, union-find, .…Benefits.•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, reusable libraries.•Performance: use optimized implementation where it matters.Client: program using operations defined in interface.Implementation: actual code implementing operations.Interface: description of data type, basic operations.4‣stacks‣dynamic resizing‣queues‣generics‣iterators‣applicationsStack operations.•push() Insert a new item onto stack.•pop() Remove and return the item most recently added.•isEmpty() Is the stack empty?5Stack APIpoppushpublic static void main(String[] args){ StackOfStrings stack = new StackOfStrings(); while (!StdIn.isEmpty()) { String item = StdIn.readString(); if (item.equals("-")) StdOut.print(stack.pop()); else stack.push(item); } }% more tobe.txt to be or not to - be - - that - - - is % java StackOfStrings < tobe.txt to be not that or be public class Stack public class StackStack()create an empty stackvoidpush(String s)insert a new item onto stackStringpop()remove and return the itemmost recently addedbooleanisEmpty()is the stack empty?can be any type (stay tuned)6Stack pop: linked-list implementationbest the was itbest was itfirst = first.next;best the was itreturn item;firstfirstfirstofString item = first.item;the"of""of"7Stack push: linked-list implementationbest the was itoldfirstbest the was itbest the was itfirstofNode oldfirst = first;first.item = "of";first.next = oldfirst;best the was itoldfirstfirst = new Node();firstoldfirstfirstfirst8Stack: linked-list implementationpublic class StackOfStrings{ private Node first = null; private class Node { String item; Node next; } public boolean isEmpty() { return first == null; } public void push(String item) { Node oldfirst = first; first = new Node(); first.item = item; first.next = oldfirst; } public String pop() { if (isEmpty()) throw new RuntimeException(); String item = first.item; first = first.next; return item; }}"inner class"stack underflow9Stack: linked-list trace560Algorithms and Data StructuresTrace of LinkedStackOfStrings test clientto tobe to beornullnullnull be ornotto or nottonullbe be ortonot or notbe be orbenot to benotornull be orthat to bethatornull toorbe beto totoStdIn StdOutbeornotto-be--that---isistonulltonulltonulltonullbetonullintroJava.indb 560 1/4/08 10:43:11 AM10Stack: 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].s[]Ncapacity = 10itwasthebestoftimesnullnullnullnull0123456789public class StackOfStrings{ private String[] s; private int N = 0; public StackOfStrings(int capacity) { s = new String[capacity]; } public boolean isEmpty() { return N == 0; } public void push(String item) { s[N++] = item; } public String pop() { return s[--N]; }}11Stack: array implementationthis version avoids "loitering" garbage collector only reclaims memoryif no outstanding referencespublic String pop(){ String item = s[--N]; s[N] = null; return item;} decrement N;then use to index into arraya cheat(stay tuned)12‣stacks‣dynamic resizing‣queues‣generics‣iterators‣applications13Stack: dynamic array implementationProblem. Requiring client to provide capacity does not implement API! Q. How to grow and shrink array? First try. •push(): increase size of s[] by 1. •pop(): decrease size of s[] by 1. Too expensive.•Need to copy all item to a new array.•Inserting first N items takes time proportional to 1 + 2 + … + N ~ N2/2.Goal. Ensure that array resizing happens infrequently.infeasible for large N14Q. How to grow array?A. If array is full, create a new array of twice the size, and copy items.Consequence. Inserting first N items takes time proportional to N (not N2).Stack: dynamic array implementation1 + 2 + 4 + … + N/2 + N ~ 2N"repeated doubling" public StackOfStrings() { s = new String[2]; } public void push(String item) { if (N == s.length) resize(2 * s.length); s[N++] = item; } private void resize(int capacity) { String[] dup = new String[capacity]; for (int i = 0; i < N; i++) dup[i] = s[i]; s = dup; }15Q. How to shrink array?First try.•push(): double size of s[] when array is full.•pop(): halve size of s[] when array is half full.Too expensive•Consider push-pop-push-pop-… sequence when array is full.•Takes time proportional to N per operation.Stack: dynamic array implementation"thrashing"itwasthebestofnullnullnullitwasthebestitwasthebestofnullnullnullitwasthebestN = 5N = 4N = 5N = 416Q. How to shrink array?Efficient solution.•push(): double size of s[] when array is full.•pop(): halve size of s[] when array is one-quarter full.Invariant. Array is always between 25% and 100% full. Stack: dynamic array implementation public String pop() { String item = s[--N]; s[N] = null; if (N > 0 && N == s.length/4) resize(s.length / 2); return item; }17Stack: dynamic array implementation trace564Algorithms and Data Structuresthat the appropriate test is whether the stack size is less than one-fourth the array size. Then, after the array is halved, it will be about half full and can accommodate a substantial number of push() and pop() operations before having to change the size of the array again. This characteristic is important: for example, if we were to use to policy of halving the array when the
View Full Document
Unlocking...