Algorithms, 4th Edition·Robert Sedgewick and Kevin Wayne·Copyright © 2002–2012·February 12, 2012 12:33:20 PMAlgorithmsFOUR T H EDIT IONR O B E R T S EDG EWICK K EVIN W A Y N E1.3 BAGS, QUEUES, AND STACKS‣stacks‣resizing arrays‣queues‣generics‣iterators‣applicationsFundamental data types.•Value: collection of objects.•Operations: insert, remove, iterate, test if empty.•Intent is clear when we insert.•Which item do we remove?Stack. Examine the item most recently added. Queue. Examine the item least recently added. 2Stacks and queuesFIFO = "first in first out"LIFO = "last in first out"enqueuedequeuepoppushstackqueue3Client, implementation, interfaceSeparate interface and implementation.Ex: stack, queue, bag, 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‣resizing arrays‣queues‣generics‣iterators‣applicationsWarmup API. Stack of strings data type.Warmup client. Reverse sequence of strings from standard input.5Stack APIpoppush public class StackOfStrings public class StackOfStringsStackOfStrings()create an empty stackvoidpush(String s)insert a new item onto stackStringpop()remove and return the itemmost recently addedbooleanisEmpty()is the stack empty?intsize()number of items on the stackRead strings from standard input.•If string equals "-", pop string from stack and print.•Otherwise, push string onto stack.6Stack test clientpublic 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 bepoppushto 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---isistonulltonulltonulltonullbetonullTrace of Stack development clientMaintain pointer to first node in a linked list; insert/remove from front.7Stack: linked-list representationfirstinsert at frontof linked listremove from frontof linked list8Stack pop: linked-list implementation to beorfirstfirst = first.next; tobeorfirstnullnullRemoving the first node in a linked listString item = first.item;save item to returndelete first nodereturn item;return saved iteminner classprivate class Node{ String item; Node next;}9Stack push: linked-list implementation to beInserting a new node at the beginning of a linked listfirst = new Node();Node oldfirst = first;orfirst to beoroldfirstoldfirst firstsave a link to the listcreate a new node for the beginningset the instance variables in the new nodefirst.item = "not";first.next = oldfirst; tobeor notfirstnullnullnullinner classprivate class Node{ String item; Node next;}10Stack: linked-list implementation in Javapublic class LinkedStackOfStrings{ 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() { String item = first.item; first = first.next; return item; }}inner class11Proposition. Every operation takes constant time in the worst case.Proposition. A stack with N items uses ~ 40 N bytes.Remark. Analysis includes memory for the stack(but not the strings themselves, which the client owns).Stack: linked-list implementation performance8 bytes (reference to String)8 bytes (reference to Node)16 bytes (object overhead)40 bytes per stack nodepublic class Node{ String item; Node next;...}node object (inner class)40 bytesreferencesobjectoverheadextraoverheaditemnext8 bytes (inner class extra overhead)inner classprivate class Node{ String item; Node next;}12Stack: 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].Defect. Stack overflows when N exceeds capacity. [stay tuned]s[]Ncapacity = 10tobeornottobenullnullnullnull0123456789public class FixedCapacityStackOfStrings{ private String[] s; private int N = 0; public FixedCapacityStackOfStrings(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]; }}13Stack: array implementationdecrement N;then use to index into arraya cheat(stay tuned)use to index into array;then increment N14Overflow and underflow.•Underflow: throw exception if pop from an empty stack.•Overflow: use resizing array for array implementation. [stay tuned]Loitering. Holding a reference to an object when it is no longer needed. Null items. We allow null items to be inserted.Stack considerationsthis version avoids "loitering": garbage collector can reclaim memoryonly if no outstanding referencespublic String pop(){ String item = s[--N]; s[N] = null; return item;} loiteringpublic String pop(){ return s[--N]; }15‣stacks‣resizing arrays‣queues‣generics‣iterators‣applications16Stack: resizing-array implementationProblem. Requiring client to provide capacity does not implement API! Q. How to grow and shrink array? First try. •push(): increase size of array s[] by 1. •pop(): decrease size of array 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 ~ N 2 / 2.Challenge. Ensure that array resizing happens infrequently.infeasible for large N17Q. 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 N 2 ).Stack: resizing-array
View Full Document
Unlocking...