Question? Leave a message!




BAGS, QUEUES, AND STACKS

BAGS, QUEUES, AND STACKS
ROBERT SEDGEWICK KEVIN WAYNE Algorithms 1.3 BAGS, QUEUES, AND STACKS stacks ‣ resizing arrays ‣ queues ‣ Algorithms FOUR TH EDITION generics ‣ iterators ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu applications ‣Stacks and queues Fundamental 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 push pop queue enqueue dequeue LIFO = "last in first out" Stack. Examine the item most recently added. FIFO = "first in first out" Queue. Examine the item least recently added. 2Client, implementation, interface Separate interface and implementation. Ex: stack, queue, bag, priority queue, symbol table, unionfind, .… 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 reuse 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. 31.3 BAGS, QUEUES, AND STACKS stacks ‣ resizing arrays ‣ queues ‣ Algorithms generics ‣ iterators ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu applications ‣Stack API Warmup API. Stack of strings data type. pop push public class StackOfStrings public class StackOfStrings public class StackOfStrings StackOfStrings() create an empty stack void push(String item) insert a new string onto stack remove and return the string String pop() most recently added boolean isEmpty() is the stack empty int size() number of strings on the stack Warmup client. Reverse sequence of strings from standard input. 5How to implement a stack with a linked list A. Can't be done efficiently with a singlylinked list. top of stack it was the best of B. null top of stack C. of best the was it null 6Stack: linkedlist implementation Maintain pointer first to first node in a singlylinked list. Push new item before first. Pop item from first. top of stack of best the was it null first 7Stack pop: linkedlist implementation save item to return String item = first.item; delete fi rst node inner class first = first.next; private class Node first or be to String item; null Node next; first or be to null return saved item return item; Removing the fi rst node in a linked list 8Stack push: linkedlist implementation save a link to the list Node oldfirst = first; oldfirst first or be to null create a new node for the beginning inner class first = new Node(); private class Node oldfirst String item; first or Node next; be to null set the instance variables in the new node first.item = "not"; first.next = oldfirst; first not or be to null Inserting a new node at the beginning of a linked list 9Stack: linkedlist implementation in Java public class LinkedStackOfStrings private Node first = null; private class Node private inner class String item; (access modifiers for instance Node next; variables don't matter) 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; 10Stack: linkedlist implementation performance Proposition. Every operation takes constant time in the worst case. Proposition. A stack with N items uses 40 N bytes. 40 bytes node object (inner class) public class Node object String item; 16 bytes (object overhead) inner class overhead Node next; ... private class Node extra 8 bytes (inner class extra overhead) overhead String item; 8 bytes (reference to String) item Node next; references 8 bytes (reference to Node) next 40 bytes per stack node Remark. This accounts for the memory for the stack (but not the memory for strings themselves, which the client owns). 11How to implement a fixedcapacity stack with an array A. Can't be done efficiently with an array. top of stack it was the best of times null null null null B. 0 1 2 3 4 5 6 7 8 9 top of stack times of best the was it null null null null C. 0 1 2 3 4 5 6 7 8 9 12Fixedcapacity stack: array implementation Use array s to store N items on stack. push(): add new item at sN. pop(): remove item from sN1. top of stack it was the best of times null null null null s 0 1 2 3 4 5 6 7 8 9 capacity = 10 N Defect. Stack overflows when N exceeds capacity. stay tuned 13Fixedcapacity stack: array implementation public class FixedCapacityStackOfStrings a cheat private String s; (stay tuned) private int N = 0; public FixedCapacityStackOfStrings(int capacity) s = new Stringcapacity; public boolean isEmpty() return N == 0; public void push(String item) sN++ = item; public String pop() use to index into array; return sN; then increment N decrement N; then use to index into array 14Stack considerations Overflow and underflow. Underflow: throw exception if pop from an empty stack. Overflow: use resizing array for array implementation. stay tuned Null items. We allow null items to be inserted. Loitering. Holding a reference to an object when it is no longer needed. public String pop() public String pop() return sN; String item = sN; loitering sN = null; return item; this version avoids "loitering": garbage collector can reclaim memory for an object only if no outstanding references 151.3 BAGS, QUEUES, AND STACKS stacks ‣ resizing arrays ‣ queues ‣ Algorithms generics ‣ iterators ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu applications ‣Stack: resizingarray implementation Problem. 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. infeasible for large N Too expensive. Need to copy all items to a new array, for each operation. 2 Array accesses to insert first N items = N + (2 + 4 + … + 2(N – 1)) N . 1 array access 2(k–1) array accesses to expand to size k per push (ignoring cost to create new array) Challenge. Ensure that array resizing happens infrequently. 17Stack: resizingarray implementation "repeated doubling" Q. How to grow array A. If array is full, create a new array of twice the size, and copy items. public ResizingArrayStackOfStrings() s = new String1; public void push(String item) if (N == s.length) resize(2 s.length); sN++ = item; private void resize(int capacity) String copy = new Stringcapacity; for (int i = 0; i N; i++) copyi = si; s = copy; i Array accesses to insert first N = 2 items. N + (2 + 4 + 8 + … + N) 3N. 1 array access k array accesses to double to size k per push (ignoring cost to create new array) 18Stack: resizingarray implementation Q. How to shrink array First try. push(): double size of array s when array is full. pop(): halve size of array s when array is onehalf full. Too expensive in worst case. Consider pushpoppushpop… sequence when array is full. Each operation takes time proportional to N. N = 5 to be or not to null null null N = 4 to be or not N = 5 to be or not to null null null N = 4 to be or not 19Stack: resizingarray implementation Q. How to shrink array Efficient solution. push(): double size of array s when array is full. pop(): halve size of array s when array is onequarter full. public String pop() String item = sN; sN = null; if (N 0 N == s.length/4) resize(s.length/2); return item; Invariant. Array is between 25 and 100 full. 20Stack resizingarray implementation: performance Amortized analysis. Starting from an empty data structure, average running time per operation over a worstcase sequence of operations. Proposition. Starting from an empty stack, any sequence of M push and pop operations takes time proportional to M. best worst amortized construct 1 1 1 push 1 N 1 pop 1 N 1 doubling and halving operations size 1 1 1 order of growth of running time for resizing stack with N items 21Stack resizingarray implementation: memory usage Proposition. Uses between 8 N and 32 N bytes to represent a stack with N items. 8 N when full. 32 N when onequarter full. public class ResizingArrayStackOfStrings 8 bytes × array size private String s; private int N = 0; … Remark. This accounts for the memory for the stack (but not the memory for strings themselves, which the client owns). 22Stack implementations: resizing array vs. linked list Tradeoffs. Can implement a stack with either resizing array or linked list; save a link to the list client can use interchangeably. Which one is better Node oldfirst = first; oldfirst Linkedlist implementation. first or be to Every operation takes constant time in the worst case. null Uses extra time and space to deal with the links. create a new node for the beginning first = new Node(); Resizingarray implementation. oldfirst Every operation takes constant amortized time. first or be to Less wasted space. null set the instance variables in the new node N = 4 to be or not null null null null first.item = "not"; first.next = oldfirst; first not or be to null 23 Inserting a new node at the beginning of a linked list1.3 BAGS, QUEUES, AND STACKS stacks ‣ resizing arrays ‣ queues ‣ Algorithms generics ‣ iterators ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu applications ‣Queue API enqueue public class QueueOfStrings public class QueueOfStrings public class QueueOfStrings QueueOfStrings() create an empty queue void enqueue(String item) insert a new string onto queue remove and return the string String dequeue() least recently added boolean isEmpty() is the queue empty int size() number of strings on the queue dequeue 25How to implement a queue with a linked list A. Can't be done efficiently with a singlylinked list. back of queue front of queue B. times of best the was it null front of queue back of queue C. it was the best of times null 26Queue: linkedlist implementation Maintain one pointer first to first node in a singlylinked list. Maintain another pointer last to last node. Dequeue from first. Enqueue after last. front of queue back of queue it was the best of times null first last 27Queue dequeue: linkedlist implementation save item to return String item = first.item; delete fi rst node first = first.next; inner class last first to be private class Node or null String item; last first Node next; to be or null return saved item return item; Removing the fi rst node in a linked list Remark. Identical code to linkedlist stack pop(). 28Queue enqueue: linkedlist implementation save a link to the last node Node oldlast = last; oldlast last first to be or null create a new node for the end inner class last = new Node(); private class Node last.item = "not"; oldlast String item; last first to be Node next; or not null null link the new node to the end of the list oldlast.next = last; oldlast last first to be or not null Inserting a new node at the end of a linked list 29 Queue: linkedlist implementation in Java public class LinkedQueueOfStrings private Node first, last; private class Node / same as in LinkedStackOfStrings / public boolean isEmpty() return first == null; public void enqueue(String item) Node oldlast = last; last = new Node(); last.item = item; last.next = null; special cases for if (isEmpty()) first = last; empty queue else oldlast.next = last; public String dequeue() String item = first.item; first = first.next; if (isEmpty()) last = null; return item; 30How to implement a fixedcapacity queue with an array A. Can't be done efficiently with an array. front of queue back of queue it was the best of times null null null null B. 0 1 2 3 4 5 6 7 8 9 back of queue front of queue times of best the was it null null null null C. 0 1 2 3 4 5 6 7 8 9 31Queue: resizingarray implementation Use array q to store items in queue. enqueue(): add new item at qtail. dequeue(): remove item from qhead. Update head and tail modulo the capacity. Add resizing array. front of queue back of queue q the best of times null null null null null null 0 1 2 3 4 5 6 7 8 9 capacity = 10 head tail Q. How to resize 321.3 BAGS, QUEUES, AND STACKS stacks ‣ resizing arrays ‣ queues ‣ Algorithms generics ‣ iterators ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu applications ‣Parameterized stack We implemented: StackOfStrings. We also want: StackOfURLs, StackOfInts, StackOfVans, …. Attempt 1. Implement a separate stack class for each type. Rewriting code is tedious and errorprone. Maintaining cutandpasted code is tedious and errorprone. most reasonable approach until Java 1.5. 34Parameterized stack We implemented: StackOfStrings. We also want: StackOfURLs, StackOfInts, StackOfVans, …. Attempt 2. Implement a stack with items of type Object. Casting is required in client. Casting is errorprone: runtime error if types mismatch. StackOfObjects s = new StackOfObjects(); Apple a = new Apple(); Orange b = new Orange(); s.push(a); s.push(b); a = (Apple) (s.pop()); runtime error 35Parameterized stack We implemented: StackOfStrings. We also want: StackOfURLs, StackOfInts, StackOfVans, …. Attempt 3. Java generics. Avoid casting in client. Discover type mismatch errors at compiletime instead of runtime. type parameter StackApple s = new StackApple(); Apple a = new Apple(); Orange b = new Orange(); s.push(a); compiletime error s.push(b); a = s.pop(); Guiding principles. Welcome compiletime errors; avoid runtime errors. 36Generic stack: linkedlist implementation public class LinkedStackOfStrings public class StackItem private Node first = null; private Node first = null; private class Node private class Node generic type name String item; Item item; Node next; Node next; public boolean isEmpty() public boolean isEmpty() return first == null; return first == null; public void push(String item) public void push(Item item) Node oldfirst = first; Node oldfirst = first; first = new Node(); first = new Node(); first.item = item; first.item = item; first.next = oldfirst; first.next = oldfirst; public String pop() public Item pop() String item = first.item; Item item = first.item; first = first.next; first = first.next; return item; return item; 37Generic stack: array implementation the way it should be public class FixedCapacityStackOfStrings public class FixedCapacityStackItem private String s; private Item s; private int N = 0; private int N = 0; public ..StackOfStrings(int capacity) public FixedCapacityStack(int capacity) s = new Stringcapacity; s = new Itemcapacity; public boolean isEmpty() public boolean isEmpty() return N == 0; return N == 0; public void push(String item) public void push(Item item) sN++ = item; sN++ = item; public String pop() public Item pop() return sN; return sN; generic array creation not allowed in Java 38Generic stack: array implementation the way it is public class FixedCapacityStackOfStrings public class FixedCapacityStackItem private String s; private Item s; private int N = 0; private int N = 0; public ..StackOfStrings(int capacity) public FixedCapacityStack(int capacity) s = new Stringcapacity; s = (Item) new Objectcapacity; public boolean isEmpty() public boolean isEmpty() return N == 0; return N == 0; public void push(String item) public void push(Item item) sN++ = item; sN++ = item; public String pop() public Item pop() return sN; return sN; the ugly cast 39Unchecked cast javac FixedCapacityStack.java Note: FixedCapacityStack.java uses unchecked or unsafe operations. Note: Recompile with Xlint:unchecked for details. javac Xlint:unchecked FixedCapacityStack.java FixedCapacityStack.java:26: warning: unchecked unchecked cast found : java.lang.Object required: Item a = (Item) new Objectcapacity; 1 warning Q. Why does Java make me cast (or use reflection) Short answer. Backward compatibility. Long answer. Need to learn about type erasure and covariant arrays. 40Generic data types: autoboxing Q. What to do about primitive types Wrapper type. Each primitive type has a wrapper object type. Ex: Integer is wrapper type for int. Autoboxing. Automatic cast between a primitive type and its wrapper. StackInteger s = new StackInteger(); s.push(17); // s.push(Integer.valueOf(17)); int a = s.pop(); // int a = s.pop().intValue(); Bottom line. Client code can use generic stack for any type of data. 411.3 BAGS, QUEUES, AND STACKS stacks ‣ resizing arrays ‣ queues ‣ Algorithms generics ‣ iterators ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu applications ‣Iteration Design challenge. Support iteration over stack items by client, without revealing the internal representation of the stack. i N s it was the best of times null null null null 0 1 2 3 4 5 6 7 8 9 first current times of best the was it null Java solution. Make stack implement the java.lang.Iterable interface. 43Iterators java.lang.Iterable interface Q. What is an Iterable public interface IterableItem A. Has a method that returns an Iterator. IteratorItem iterator(); Q. What is an Iterator java.util.Iterator interface A. Has methods hasNext() and next(). public interface IteratorItem boolean hasNext(); Item next(); optional; use Q. Why make data structures Iterable void remove(); at your own risk A. Java supports elegant client code. “foreach” statement (shorthand) equivalent code (longhand) for (String s : stack) IteratorString i = stack.iterator(); StdOut.println(s); while (i.hasNext()) String s = i.next(); StdOut.println(s); 44Stack iterator: linkedlist implementation import java.util.Iterator; public class StackItem implements IterableItem ... public IteratorItem iterator() return new ListIterator(); private class ListIterator implements IteratorItem private Node current = first; public boolean hasNext() return current = null; public void remove() / not supported / public Item next() throw UnsupportedOperationException Item item = current.item; throw NoSuchElementException if no more items in iteration current = current.next; return item; first current times of best the was it null 45Stack iterator: array implementation import java.util.Iterator; public class StackItem implements IterableItem … public IteratorItem iterator() return new ReverseArrayIterator(); private class ReverseArrayIterator implements IteratorItem private int i = N; public boolean hasNext() return i 0; public void remove() / not supported / public Item next() return si; i N it was the best of times s null null null null 0 1 2 3 4 5 6 7 8 9 46Iteration: concurrent modification Q. What if client modifies the data structure while iterating A. A failfast iterator throws a java.util.ConcurrentModificationException. concurrent modification for (String s : stack) stack.push(s); Q. How to detect A. Count total number of push() and pop() operations in Stack. Save counts in Iterator subclass upon creation. If, when calling next() and hasNext(), the current counts do not equal the saved counts, throw exception. 471.3 BAGS, QUEUES, AND STACKS stacks ‣ resizing arrays ‣ queues ‣ Algorithms generics ‣ iterators ‣ ROBERT SEDGEWICK KEVIN WAYNE http://algs4.cs.princeton.edu applications ‣Java collections library List interface. java.util.List is API for an sequence of items. public interface ListItem implements IterableItem public interface ListItem implements IterableItem public interface ListItem implements IterableItem List() create an empty list boolean isEmpty() is the list empty int size() number of items void add(Item item) append item to the end Item get(int index) return item at given index Item remove(int index) return and delete item at given index boolean contains(Item item) does the list contain the given item IteratorItem iterator() iterator over all items in the list ... Implementations. java.util.ArrayList uses resizing array; java.util.LinkedList uses linked list. caveat: only some operations are efficient 49Java collections library java.util.Stack. Supports push(), pop(), and iteration. Extends java.util.Vector, which implements java.util.List interface from previous slide, including get() and remove(). Bloated and poorlydesigned API (why) Java 1.3 bug report (June 27, 2001) The iterator method on java.util.Stack iterates through a Stack from the bottom up. One would think that it should iterate as if it were popping off the top of the Stack. status (closed, will not fix) It was an incorrect design decision to have Stack extend Vector ("isa" rather than "hasa"). We sympathize with the submitter but cannot fix this because of compatibility. 50Java collections library java.util.Stack. Supports push(), pop(), and iteration. Extends java.util.Vector, which implements java.util.List interface from previous slide, including get() and remove(). Bloated and poorlydesigned API (why) java.util.Queue. An interface, not an implementation of a queue. Best practices. Use our implementations of Stack, Queue, and Bag. 51War story (from Assignment 1) Generate random open sites in an NbyN percolation system. does not percolate percolates blocked Jenny: pick (i, j) at random; if already open, repeat. site 2 Takes c N seconds. 1 2 Kenny: create a java.util.ArrayList of N closed sites. Pick an index at random and delete. open site 4 Takes c N seconds. 2 open site connected to top no open site connected to top Why is my program so slow Kenny Lesson. Don't use a library until you understand its API This course. Can't use a library until we've implemented it in class. 52Stack applications Parsing in a compiler. Java virtual machine. Undo in a word processor. Back button in a Web browser. PostScript language for printers. Implementing function calls in a compiler. ... 53Function calls How a compiler implements a function. Function call: push local environment and return address. Return: pop return address and local environment. Recursive function. Function that calls itself. Note. Can always use an explicit stack to remove recursion. gcd (216, 192) static int gcd(int p, int q) p = 216, q = 192 if (q == 0) return p; gcd (192, 24) else return gcd(q, p q); static int gcd(int p, int q) p = 192, q = 24 if (q == 0) return p; gcd (24, 0) else return gcd(q, p q); static int gcd(int p, int q) if (q == 0) return p; p = 24, q = 0 else return gcd(q, p q); 544.3 Stacks and Queues 573 it is easy to convince yourself that it computes the proper value: any time the algo rithm encounters a subexpression consisting of two operands separated by an op Arithmetic expression evaluation erator, all surrounded by parentheses, it leaves the result of performing that opera tion on those operands on the operand stack. The result is the same as if that value had appeared in the input instead of the sub expression, so we can think of replavalue stack cing the Goal. Evaluate infix expressions. ( 1 + ( ( 2 + 3 ) ( 4 5 ) ) ) subexpression by the value to get an expression operator stack that would yield the same result. We can apply 1 + ( ( 2 + 3 ) ( 4 5 ) ) ) this argument again and again until we get a ( 1 + ( ( 2 + 3 ) ( 4 5 ) ) ) single value. For example, the algorithm com 1 ( ( 2 + 3 ) ( 4 5 ) ) ) putes the same value of all of these expres + sions: 1 2 operand operator + 3 ) ( 4 5 ) ) ) + ( 1 + ( ( 2 + 3 ) ( 4 5 ) ) ) ( 1 + ( 5 ( 4 5 ) ) ) 1 2 ( 1 + ( 5 20 ) ) 3 ) ( 4 5 ) ) ) + + ( 1 + 100 ) 1 2 3 101 ) ( 4 5 ) ) ) Twostack algorithm. E. W. Dijkstra + + Evaluate (PROGRAM 4.3.5) is an implemen 1 5 Value: push onto the value stack. tation of this method. This code is a simple ( 4 5 ) ) ) + example of an interpreter : a program that in 1 5 Operator: push onto the operator stack. terprets the computation specified by a given ( 4 5 ) ) ) + string and performs the computation to ar 1 5 4 Left parenthesis: ignore. rive at the result. A compiler is a program that 5 ) ) ) + converts the string into code on a lowerlevel Right parenthesis: pop operator and two values; 1 5 4 machine that can do the job. This conversion 5 ) ) ) + is a more complicated process than the step push the result of applying that operator 1 5 4 5 bystep conversion used by an interpreter, but ) ) ) + it is based on the same underlying mechanism. to those values onto the operand stack. 1 5 20 Initially, Java was based on using an interpret ) ) + er. Now, however, the Java system includes a 1 100 compiler that converts arithmetic expressions ) + (and, more generally, Java programs) into code 101 for the Java virtual machine, an imaginary ma Context. An interpreter chine that is easy to simulate on an actual com puter. Trace of expression evaluation (Program 4.3.5) 55 introJava.indb 573 1/3/08 4:16:56 PMDijkstra's twostack algorithm demo value stack operator stack infix expression (fully parenthesized) ( 1 + ( ( 2 + 3 ) ( 4 5 ) ) ) ( 1 + ( ( 2 + 3 ) ( 4 5 ) ) ) operator operand 56Arithmetic expression evaluation public class Evaluate public static void main(String args) StackString ops = new StackString(); StackDouble vals = new StackDouble(); while (StdIn.isEmpty()) String s = StdIn.readString(); if (s.equals("(")) ; else if (s.equals("+")) ops.push(s); else if (s.equals("")) ops.push(s); else if (s.equals(")")) String op = ops.pop(); if (op.equals("+")) vals.push(vals.pop() + vals.pop()); else if (op.equals("")) vals.push(vals.pop() vals.pop()); else vals.push(Double.parseDouble(s)); StdOut.println(vals.pop()); java Evaluate ( 1 + ( ( 2 + 3 ) ( 4 5 ) ) ) 101.0 57Correctness Q. Why correct A. When algorithm encounters an operator surrounded by two values within parentheses, it leaves the result on the value stack. ( 1 + ( ( 2 + 3 ) ( 4 5 ) ) ) as if the original input were: ( 1 + ( 5 ( 4 5 ) ) ) Repeating the argument: ( 1 + ( 5 20 ) ) ( 1 + 100 ) 101 Extensions. More ops, precedence order, associativity. 58Stackbased programming languages Observation 1. Dijkstra's twostack algorithm computes the same value if the operator occurs after the two values. ( 1 ( ( 2 3 + ) ( 4 5 ) ) + ) Observation 2. All of the parentheses are redundant 1 2 3 + 4 5 + Jan Lukasiewicz Bottom line. Postfix or "reverse Polish" notation. Applications. Postscript, Forth, calculators, Java virtual machine, … 59
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.AlexanderTyler
User Type:
Teacher
Country:
India
Uploaded Date:
21-07-2017