Algorithms in Java, 4th Edition·Robert Sedgewick and Kevin Wayne·Copyright © 2008·February 11, 2008 1:54:15 PMStacks and Queues‣stacks‣dynamic resizing‣queues‣generics‣iterators‣applicationsReference: Algorithms in Java, Chapter 3, 42Stacks 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 so as to:•Build layers of abstraction.•Reuse software.•Ex: stack, queue, symbol table, union-find, ....Client: program using operations defined in interface.Implementation: actual code implementing operations.Interface: description of data type, basic 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, 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.5‣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?6Stackspoppushpublic 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 be7Stack pop: linked-list implementationbest the was itbest the was itfirst = first.next;best the was itreturn item;firstfirstfirstofString item = first.item;8Stack push: linked-list implementationbest the was itoldfirstbest the was itbest the was itfirstofNode oldfirst = first;first.item = "of";first.next = oldfirst;best the was itoldfirstNode first = new Node();firstoldfirstfirstfirst9Stack: 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"10Stack: 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 AM11Stack: 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]; }}12Stack: array implementationthis version avoids "loitering" garbage collector only reclaims memoryif no outstanding referencespublic String pop(){ String item = s[--N]; s[N] = null; return item;}13‣stacks‣dynamic resizing‣queues‣generics‣iterators‣applications14Stack: dynamic array implementationQ. How to grow array? Q. How to 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 N items takes time proportional to 1 + 2 + … + N ~ N2/2.Goal. Ensure that array resizing happens infrequently.infeasible for large N15Q. How to grow array?A. If array is full, create a new array of twice the size, and copy items.Consequence. Inserting 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[1]; } 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; }16Q. 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.•Time proportional to N per operation.Stack: dynamic array implementation"thrashing"itwasthebestofnullnullnullitwasthebestitwasthebestofnullnullnullitwasthebestN = 5N = 4N = 5N = 417Q. 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. Consequence. Starting from empty data structure, any sequence of M ops takes time proportional to M.Stack: dynamic array implementation public String pop() { String item = s[N-1]; s[N-1] = null; N--; if (N == s.length/4) resize(s.length / 2); s[N++] = item; return item; }"amortized" bound18Stack: 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
View Full Document
Unlocking...