Question? Leave a message!




Stacks and Queues

Stacks and Queues
4.3 Stacks and Queues Introduction to Programming in Java: An Interdisciplinary Approach · Robert Sedgewick and Kevin Wayne · Copyright © 2002–2010 · 6/26/10 8:10 AM Data Types and Data Structures Data types.   Set of values.   Set of operations on those values.   Some are built in to Java: int, double, char, . . .   Most are not: Complex, Picture, Stack, Queue, Graph, … this lecture Data structures.   Represent data or relationships among data.   Some are built into Java: arrays, String,…   Most are not: linked list, circular list, tree, sparse array, graph, . . . this lecture TSP assignment next lecture 2 Collections Fundamental data types.   Set of operations (add, remove, test if empty) on generic data.   Intent is clear when we insert.   Which item do we remove this lecture Stack. LIFO = last in first out   Remove the item most recently added.   Ex: cafeteria trays, Web surfing. Queue. FIFO = first in, first out   Remove the item least recently added.   Ex: Registrar's line. next lecture Symbol table.   Remove the item with a given key.   Ex: Phone book. 3 Stacks 4 Stack API push pop public class Reverse public static void main(String args) StackOfStrings stack = new StackOfStrings(); while (StdIn.isEmpty()) stack.push(StdIn.readString()); while (stack.isEmpty()) StdOut.println(stack.pop()); 5 Stack Client Example 1: Reverse public class Reverse public static void main(String args) StackOfStrings stack = new StackOfStrings(); while (StdIn.isEmpty()) String s = StdIn.readString(); stack.push(s); while (stack.isEmpty()) String s = stack.pop (); StdOut.println(s); more tiny.txt it was the best of times java Reverse tiny.txt times of best the was it stack contents when standard input is empty 6 Stack Client Example 2: Test Client public static void main(String args) StackOfStrings stack = new StackOfStrings(); while (StdIn.isEmpty()) String s = StdIn.readString(); if (s.equals("")) StdOut.println(stack.pop()); else stack.push(s); more test.txt to be or not to – be that is java StackOfStrings test.txt to be not that or be stack contents just before first pop operation 7 Stack: Array Implementation how big to make array stay tuned Array implementation of a stack.   Use array a to store N items on stack.   push() add new item at aN. stack and array contents th   pop() remove item from aN1. after 4 push operation to be or not a 0 1 2 3 4 5 6 7 8 9 N public class ArrayStackOfStrings private String a; temporary solution: make client provide capacity private int N = 0; public ArrayStackOfStrings(int max) a = new Stringmax; public boolean isEmpty() return (N == 0); public void push(String item) aN++ = item; public String pop() return aN; 8 Array Stack: Test Client Trace push pop 9 Array Stack: Performance Running time. Push and pop take constant time. Memory. Proportional to clientsupplied capacity, not number of items. Problem.   API does not call for capacity (bad to change API).   Client might use multiple stacks.   Client might not know what capacity to use. Challenge. Stack implementation where size is not fixed ahead of time. 10 Linked Lists 11 Sequential vs. Linked Allocation Sequential allocation. Put object one after another.   TOY: consecutive memory cells.   Java: array of objects. Linked allocation. Include in each object a link to the next one.   TOY: link is memory address of next object. addr value addr value   Java: link is reference to next object. C0 "Alice" C0 "Carol" C1 "Bob" C1 null C2 "Carol" C2 C3 C3 th get i element Key distinctions. C4 C4 "Alice" C5 C5 CA   Array: random access, fixed size. C6 C6   Linked list: sequential access, variable size. C7 C7 C8 C8 get next element C9 C9 CA CA "Bob" CB CB C0 linked list array 12 Linked Lists Linked list.   A recursive data structure.   An item plus a pointer to another linked list (or empty list).   Unwind recursion: linked list is a sequence of items. public class Node Node data type. private String item;   A reference to a String. private Node next;   A reference to another Node. first Alice Bob Carol null item next special pointer value null terminates list 15 Building a Linked List addr Value Node third = new Node(); C0 "Carol" third.item = "Carol"; third.next = null; C1 null C2 Node second = new Node(); second.item = "Bob"; C3 second.next = third; first C4 C4 "Alice" Node first = new Node(); second CA C5 CA first.item = "Alice"; third C0 C6 first.next = second; C7 C8 C9 CA "Bob" CB C0 CC first second third CD CE Alice Bob Carol null CF item next main memory 16 Stack Push: Linked List Implementation first best the was it first second best the was it Node second = first; second first best the was it first = new Node(); second first first.item = "of"; of best the was it first.next = second; 17 Stack Pop: Linked List Implementation "of" first of best the was it String item = first.item; first of best the was it first = first.next; garbagecollected first best the was it return item; 18 Stack: Linked List Implementation public class LinkedStackOfStrings private Node first = null; private class Node private String item; private Node next; "inner class" public boolean isEmpty() return first == null; public void push(String item) Node second = first; first = new Node(); first.item = item; stack and linked list contents first.next = second; th after 4 push operation public String pop() String item = first.item; first = first.next; return item; 19 Linked List Stack: Test Client Trace push pop 20 Linked List Stack: Performance Running time. Push and pop take constant time. Memory. Proportional to number of items in stack. 21 Stack Data Structures: Tradeoffs Two data structures to implement Stack data type. Array.   Every push/pop operation take constant time.   But… must fix maximum capacity of stack ahead of time. Linked list.   Every push/pop operation takes constant time.   But… uses extra space and time to deal with references. 22 List Processing Challenge 1 Q. What does the following code fragment do for (Node x = first; x = null; x = x.next) StdOut.println(x.item); first Alice Bob Carol null item next 23 List Processing Challenge 2 Q. What does the following code fragment do Node last = new Node(); last.item = StdIn.readString(); last.next = null; Node first = last; while (StdIn.isEmpty()) last.next = new Node(); last = last.next; last.item = StdIn.readString(); last.next = null; last first Alice Bob Carol null item next 24 Parameterized Data Types 25 Parameterized Data Types We implemented: StackOfStrings. We also want: StackOfURLs, StackOfInts, … Strawman. Implement a separate stack class for each type.   Rewriting code is tedious and errorprone.   Maintaining cutandpasted code is tedious and errorprone. 26 Generics Generics. Parameterize stack by a single type. “stack of apples” parameterized type StackApple stack = new StackApple(); Apple a = new Apple(); Orange b = new Orange(); stack.push(a); stack.push(b); // compiletime error a = stack.pop(); sample client can’t push an orange onto a stack of apples 27 Generic Stack: Linked List Implementation public class StackItem private Node first = null; parameterized type name private class Node (chosen by programmer) private Item item; private Node next; public boolean isEmpty() return first == null; public void push(Item item) Node second = first; first = new Node(); first.item = item; first.next = second; public Item pop() Item item = first.item; first = first.next; return item; 28 Autoboxing Generic stack implementation. Only permits reference types. Wrapper type.   Each primitive type has a wrapper reference type.   Ex: Integer is wrapper type for int. Autoboxing. Automatic cast from primitive type to wrapper type. Autounboxing. Automatic cast from wrapper type to primitive type. StackInteger stack = new StackInteger(); stack.push(17); // autobox (int Integer) int a = stack.pop(); // autounbox (Integer int) 29 Stack Applications Real world 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. 30 Function Calls How a compiler implements functions.   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) if (q == 0) return p; else return gcd(q, p q); gcd (192, 24) p = 216, q = 192 static int gcd(int p, int q) if (q == 0) return p; else return gcd(q, p q); gcd (24, 0) p = 192, q = 24 static int gcd(int p, int q) if (q == 0) return p; else return gcd(q, p q); p = 24, q = 0 31 Arithmetic Expression Evaluation value stack operator stack Goal. Evaluate infix expressions. operator operand Two stack algorithm. E. W. Dijkstra   Value: push onto the value stack.   Operator: push onto the operator stack.   Left parens: ignore.   Right parens: pop operator and two values; push the result of applying that operator to those values onto the operand stack. Context. An interpreter 32 Arithmetic 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 33 Correctness Why correct When algorithm encounters an operator surrounded by two values within parentheses, it leaves the result on the value stack. ( 1 + ( ( 2 + 3 ) ( 4 5 ) ) ) So it's 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, whitespace. 1 + (2 3 4) 5 sqrt(66 + 77) 34 StackBased Programming Languages Observation 1. Remarkably, the 2stack 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, … 35 Queues 36 Queue API return an iterator over the keys IteratorKey iterator() enqueue dequeue public static void main(String args) QueueString q = new QueueString(); q.enqueue("Vertigo"); q.enqueue("Just Lose It"); q.enqueue("Pieces of Me"); q.enqueue("Pieces of Me"); while(q.isEmpty()) StdOut.println(q.dequeue()); 37 Enqueue: Linked List Implementation first last it was the best oldlast first last it was the best Node oldlast = last; first oldlast last last = new Node(); of it was the best last.item = "of"; last.next = null; first oldlast last it was the best of oldlast.next = last; 38 Dequeue: Linked List Implementation first last was the best of it String item = first.item; first last it was the best of first = first.next; garbagecollected first last was the best of return item; 39 Queue: Linked List Implementation public class QueueItem private Node first, last; private class Node Item item; Node next; public boolean isEmpty() return first == null; public void enqueue(Item item) Node oldlast = last; last = new Node(); last.item = item; last.next = null; if (isEmpty()) first = last; else oldlast.next = last; public Item dequeue() Item item = first.item; first = first.next; if (isEmpty()) last = null; return item; 40 Queue Applications Some applications.   iTunes playlist.   Data buffers (iPod, TiVo).   Asynchronous data transfer (file IO, pipes, sockets).   Dispensing requests on a shared resource (printer, processor). Simulations of the real world.   Guitar string.   Traffic analysis.   Waiting times of customers at call center.   Determining number of cashiers to have at a supermarket. 41 M/D/1 Queuing Mode l M/D/1 queue.   Customers are serviced at fixed rate of µ per minute.   Customers arrive according to Poisson process at rate of λ per minute. interarrival time has exponential distribution −λx PrX≤ x = 1−e € Arrival rate λ Departure rate µ Infinite queue Server Q. What is average wait time W of a customer Q. What is average number of customers L in system 42 43 EventBased Simulation public class MD1Queue public static void main(String args) double lambda = Double.parseDouble(args0); double mu = Double.parseDouble(args1); QueueDouble q = new QueueDouble(); double nextArrival = StdRandom.exp(lambda); double nextService = nextArrival + 1/mu; while(true) if (nextArrival nextService) arrival q.enqueue(nextArrival); nextArrival += StdRandom.exp(lambda); else service double wait = nextService q.dequeue(); // add waiting time to histogram if (q.isEmpty()) nextService = nextArrival + 1/mu; else nextService = nextService + 1/mu; 44 M/D/1 Queue Analysis Observation. As service rate approaches arrival rate, service goes to h. λλ = = .2 .2,, µµ = = .2 .25 1 see ORFE 309 λ 1 W = + , L = λ W Queueing theory. 2µ (µ−λ) µ Little's law 45 € Summary Stacks and queues are fundamental ADTs.   Array implementation.   Linked list implementation.   Different performance characteristics. Many applications. 46
Website URL
Comment
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.BenjaminClark
User Type:
Teacher
Country:
United States
Uploaded Date:
21-07-2017