Question? Leave a message!




BAGS, QUEUES, AND STACKS

BAGS, QUEUES, AND STACKS
Dr.AlexanderTyler Profile Pic
Dr.AlexanderTyler,India,Teacher
Published Date:21-07-2017
Website URL
Comment
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, 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. 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 singly-linked list. top of stack it was the best of B. null top of stack C. of best the was it null 6Stack: linked-list implementation Maintain pointer first to first node in a singly-linked list. Push new item before first. Pop item from first. top of stack of best the was it null first 7Stack pop: linked-list 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: linked-list 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: linked-list 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: linked-list 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 fixed-capacity 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 12Fixed-capacity stack: array implementation Use array s to store N items on stack. push(): add new item at sN. pop(): remove item from sN-1. 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 13Fixed-capacity 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: resizing-array 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: resizing-array 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: resizing-array 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 one-half full. Too expensive in worst case. Consider push-pop-push-pop-… 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: resizing-array 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 one-quarter 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. 20
sharer
Presentations
Free