
	Trending ▼ ICSE CBSE 10th ISC CBSE 12th CTET GATE UGC NET Vestibulares ResFinder

unit 1 notes

64 pages, 0 questions, 0 questions with responses, 0 total responses,

	raghucmrec	+Fave Message
	Profile Timeline Uploads

Home > raghucmrec >

Formatting page ...

Algorithms R OBERT S EDGEWICK | K EVIN W AYNE 1.3 B AGS , QUEUES, AND S TACKS stacks resizing arrays Algorithms F O U R T H E D I T I O N R OBERT S EDGEWICK | K EVIN W AYNE http://algs4.cs.princeton.edu queues generics iterators 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 Stack. Examine the item most recently added. LIFO = "last in first out" Queue. Examine the item least recently added. FIFO = "first in first out" 2 Client, 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. 3 1.3 B AGS , QUEUES, AND S TACKS stacks resizing arrays Algorithms R OBERT S EDGEWICK | K EVIN W AYNE http://algs4.cs.princeton.edu queues generics iterators applications Stack API Warmup API. Stack of strings data type. push pop public class StackOfStrings StackOfStrings() void push(String item) String pop() boolean isEmpty() int size() create an empty stack insert a new string onto stack remove and return the string most recently added is the stack empty? number of strings on the stack Warmup client. Reverse sequence of strings from standard input. 5 Stack test client Read strings from standard input. If string equals "-", pop string from stack and print. Otherwise, push string onto stack. push pop public static void main(String[] args) { StackOfStrings stack = new StackOfStrings(); while (!StdIn.isEmpty()) { String s = StdIn.readString(); if (s.equals("-")) StdOut.print(stack.pop()); else stack.push(s); } } % more tobe.txt to be or not to - be - - that - - - is % java StackOfStrings < tobe.txt to be not that or be 6 Stack: linked-list representation Maintain pointer to first node in a linked list; insert/remove from front. StdIn StdOut to null to be be insert at front of linked list first or or not not to to - remove from front of linked list to - - that not be be be not to null not be or not or not or to null be or be or be to null be to null to null be to null to null or be that or to null be to null 7 Stack pop: linked-list implementation save item to return String item = first.item; delete first node inner class private class Node { String item; Node next; } first = first.next; first or be to null first or be to null return saved item return item; Removing the first node in a linked list 8 Stack push: linked-list implementation save a link to the list Node oldfirst = first; oldfirst first inner class private class Node { String item; Node next; } or be to null create a new node for the beginning first = new Node(); oldfirst first or 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 9 Stack: linked-list implementation in Java public class LinkedStackOfStrings { private Node first = null; private class Node { String item; Node next; } public boolean isEmpty() { return first == null; private inner class (access modifiers don't matter) } 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; } } 10 Stack: linked-list implementation performance Proposition. Every operation takes constant time in the worst case. Proposition. A stack with N items uses ~ 40 N bytes. node object (inner class) public class Node { String item; inner class Node next; ... private class Node } { String item; Node next; } 40 bytes object overhead 16 bytes (object overhead) extra overhead 8 bytes (inner class extra overhead) 8 bytes (reference to String) item references next 8 bytes (reference to Node) 40 bytes per stack node Remark. Analysis includes memory for the stack (but not the strings themselves, which the client owns). 11 Stack: array implementation Array 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[] to be or not to be null null null null 0 1 2 3 4 5 6 7 8 9 N capacity = 10 Defect. Stack overflows when N exceeds capacity. [stay tuned] 12 Stack: array implementation public class FixedCapacityStackOfStrings { private String[] s; private int N = 0; a cheat (stay tuned) 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]; } use to index into array; then increment N } decrement N; then use to index into array 13 Stack 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() { return s[--N]; } loitering public String pop() { String item = s[--N]; s[N] = null; return item; } this version avoids "loitering": garbage collector can reclaim memory only if no outstanding references 14 1.3 B AGS , QUEUES, AND S TACKS stacks resizing arrays Algorithms R OBERT S EDGEWICK | K EVIN W AYNE http://algs4.cs.princeton.edu queues generics iterators applications 1.3 B AGS , QUEUES, AND S TACKS stacks resizing arrays Algorithms R OBERT S EDGEWICK | K EVIN W AYNE http://algs4.cs.princeton.edu queues generics iterators 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. Too expensive. Need to copy all items to a new array. Inserting first N items takes time proportional to 1 + 2 + + N ~ N 2 / 2. infeasible for large N Challenge. Ensure that array resizing happens infrequently. 17 Stack: resizing-array implementation Q. How to grow array? "repeated doubling" A. If array is full, create a new array of twice the size, and copy items. public ResizingArrayStackOfStrings() { 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[] copy = new String[capacity]; for (int i = 0; i < N; i++) copy[i] = s[i]; s = copy; } see next slide Consequence. Inserting first N items takes time proportional to N (not N 2 ). 18 Stack: amortized cost of adding to a stack Cost of inserting first N items. N + (2 + 4 + 8 + + N) ~ 3N. 1 array access per push k array accesses to double to size k (ignoring cost to create new array) cost (array accesses) 128 one gray dot for each operation 64 128 red dots give cumulative average 3 0 0 number of push() operations 128 Amortized cost of adding to a Stack 19 Stack: resizing-array implementation Q. How to shrink array? First try. push(): pop(): double size of array s[] when array is full. 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 N = 4 to be or not N = 5 to be or not N = 4 to be or not to null null null to null null null 20 Stack: resizing-array implementation Q. How to shrink array? Efficient solution. push(): pop(): double size of array s[] when array is full. halve size of array s[] when array is one-quarter full. public String pop() { String item = s[--N]; s[N] = null; if (N > 0 && N == s.length/4) resize(s.length/2); return item; } Invariant. Array is between 25% and 100% full. 21 Stack: resizing-array implementation trace push() pop() a[] N a.length 0 1 null to 1 1 to be 2 2 to be or 3 4 to not 4 4 to 5 0 1 2 3 4 5 6 7 be or null to be or not 8 to be or not to null null null be to 4 5 8 8 to to be be or or not not null be null null null null null null - be 4 8 to be or not null null null null - not 3 8 to be or null null null null null 4 8 to be or that null null null null null null null null that - that 3 8 to be or null - or 2 4 to be null null - be 1 2 to null 2 2 to is is Trace of array resizing during a sequence of push() and pop() operations 22 Stack resizing-array implementation: performance Amortized analysis. Average running time per operation over a worst-case 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 size 1 1 1 doubling and halving operations order of growth of running time for resizing stack with N items 23 Stack resizing-array 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 one-quarter full. public class ResizingArrayStackOfStrings { private String[] s; private int N = 0; } 8 bytes (reference to array) 24 bytes (array overhead) 8 bytes array size 4 bytes (int) 4 bytes (padding) Remark. Analysis includes memory for the stack (but not the strings themselves, which the client owns). 24 Stack 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 Node interchangeably. oldfirst = first; Which one is better? oldfirst Linked-list implementation. first or be extra time and space to deal with the links. Usescreate a new node for the beginning to Every operation takes constant time in the worst case. null first = new Node(); Resizing-array implementation. oldfirst Every operation takes constant amortized time. Less wasted space. first or be to null set the instance variables in the new node N = 4 to be or first.item = "not"; first.next = oldfirst; first not or not null be null null null to null Inserting a new node at the beginning of a linked list 25 1.3 B AGS , QUEUES, AND S TACKS stacks resizing arrays Algorithms R OBERT S EDGEWICK | K EVIN W AYNE http://algs4.cs.princeton.edu queues generics iterators applications 1.3 B AGS , QUEUES, AND S TACKS stacks resizing arrays Algorithms R OBERT S EDGEWICK | K EVIN W AYNE http://algs4.cs.princeton.edu queues generics iterators applications Queue API enqueue public class QueueOfStrings QueueOfStrings() void enqueue(String item) String dequeue() boolean isEmpty() int size() create an empty queue insert a new string onto queue remove and return the string least recently added is the queue empty? number of strings on the queue dequeue 28 Queue: linked-list representation Maintain pointer to first and last nodes in a linked list; insert/remove from opposite ends. StdIn StdOut to null to to be first or to not to to to - remove from front of linked list to - - be be be be or be null or not be be be or or not to last insert at end of linked list or null or or not not to be null not null not to null to null to be null be null 29 Queue dequeue: linked-list implementation save item to return String item = first.item; delete first node first = first.next; inner class private class Node { String item; Node next; } last first to be or null first last to be or null return saved item return item; Removing the first node in a linked list Remark. Identical code to linked-list stack pop(). 30 Queue enqueue: linked-list implementation save a link to the last node Node oldlast = last; oldlast last first inner class private class Node { String item; Node next; } to be or null create a new node for the end last = new Node(); last.item = "not"; oldlast first to be last or null not null link the new node to the end of the list oldlast.next = last; oldlast first to be last or Inserting a new node at the end of a linked list not null 31 Queue: linked-list implementation in Java public class LinkedQueueOfStrings { private Node first, last; private class Node { /* same as in StackOfStrings */ public boolean isEmpty() { return first == null; } } public void enqueue(String item) { Node oldlast = last; last = new Node(); last.item = item; last.next = null; if (isEmpty()) first = last; else oldlast.next = last; } special cases for empty queue public String dequeue() { String item = first.item; first = first.next; if (isEmpty()) last = null; return item; } } 32 Queue: resizing array implementation Array implementation of a queue. Use array q[] to store items in queue. enqueue(): add new item at q[tail]. dequeue(): remove item from q[head]. Update head and tail modulo the capacity. Add resizing array. q[] null null the best of times null null null null 0 1 2 3 4 5 6 7 8 9 head tail capacity = 10 33 1.3 B AGS , QUEUES, AND S TACKS stacks resizing arrays Algorithms R OBERT S EDGEWICK | K EVIN W AYNE http://algs4.cs.princeton.edu queues generics iterators applications 1.3 B AGS , QUEUES, AND S TACKS stacks resizing arrays Algorithms R OBERT S EDGEWICK | K EVIN W AYNE http://algs4.cs.princeton.edu queues generics iterators 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 error-prone. Maintaining cut-and-pasted code is tedious and error-prone. @#$*! most reasonable approach until Java 1.5. 36 Parameterized 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 error-prone: run-time 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()); run-time error 37 Parameterized stack We implemented: StackOfStrings. We also want: StackOfURLs, StackOfInts, StackOfVans, . Attempt 3. Java generics. Avoid casting in client. Discover type mismatch errors at compile-time instead of run-time. type parameter Stack<Apple> s = new Stack<Apple>(); Apple a = new Apple(); Orange b = new Orange(); s.push(a); s.push(b); compile-time error a = s.pop(); Guiding principles. Welcome compile-time errors; avoid run-time errors. 38 Generic stack: linked-list implementation public class LinkedStackOfStrings { private Node first = null; public class Stack<Item> { private Node first = null; private class Node { String item; Node next; } private class Node { Item item; Node next; } public boolean isEmpty() { return first == null; public boolean isEmpty() { return first == null; } generic type name } 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; } } public void push(Item item) { Node oldfirst = first; first = new Node(); first.item = item; first.next = oldfirst; } public Item pop() { Item item = first.item; first = first.next; return item; } } 39 Generic stack: array implementation the way it should be public class FixedCapacityStackOfStrings { private String[] s; private int N = 0; public class FixedCapacityStack<Item> { private Item[] s; private int N = 0; public ..StackOfStrings(int capacity) { s = new String[capacity]; } public boolean isEmpty() { return N == 0; } public boolean isEmpty() { return N == 0; } public void push(String item) { s[N++] = item; } public void push(Item item) { s[N++] = item; } public String pop() { return s[--N]; } } public FixedCapacityStack(int capacity) { s = new Item[capacity]; } public Item pop() { return s[--N]; } } @#$*! generic array creation not allowed in Java 40 Generic stack: array implementation the way it is public class FixedCapacityStackOfStrings { private String[] s; private int N = 0; public class FixedCapacityStack<Item> { private Item[] s; private int N = 0; public ..StackOfStrings(int capacity) { s = new String[capacity]; } public FixedCapacityStack(int capacity) { s = (Item[]) new Object[capacity]; } public boolean isEmpty() { return N == 0; } public boolean isEmpty() { return N == 0; } public void push(String item) { s[N++] = item; } public void push(Item item) { s[N++] = item; } public String pop() { return s[--N]; } public Item pop() { return s[--N]; } } } the ugly cast 41 Unchecked cast % javac FixedCapacityStack 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 Object[capacity]; ^ 1 warning 42 Generic 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. Stack<Integer> s = new Stack<Integer>(); 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. 43 1.3 B AGS , QUEUES, AND S TACKS stacks resizing arrays Algorithms R OBERT S EDGEWICK | K EVIN W AYNE http://algs4.cs.princeton.edu queues generics iterators applications 1.3 B AGS , QUEUES, AND S TACKS stacks resizing arrays Algorithms R OBERT S EDGEWICK | K EVIN W AYNE http://algs4.cs.princeton.edu queues generics iterators applications Iteration Design challenge. Support iteration over stack items by client, without revealing the internal representation of the stack. i s[] N it was the best of times null null null null 0 1 2 3 4 5 6 7 8 9 first times current of best the was it null Java solution. Make stack implement the java.lang.Iterable interface. 46 Iterators Iterable interface Q. What is an Iterable ? A. Has a method that returns an Iterator. Q. What is an Iterator ? public interface Iterable<Item> { Iterator<Item> iterator(); } Iterator interface A. Has methods hasNext() and next(). Q. Why make data structures Iterable ? A. Java supports elegant client code. foreach statement (shorthand) for (String s : stack) StdOut.println(s); public interface Iterator<Item> { boolean hasNext(); Item next(); optional; use void remove(); at your own risk } equivalent code (longhand) Iterator<String> i = stack.iterator(); while (i.hasNext()) { String s = i.next(); StdOut.println(s); } 47 Stack iterator: linked-list implementation import java.util.Iterator; public class Stack<Item> implements Iterable<Item> { ... public Iterator<Item> iterator() { return new ListIterator(); } private class ListIterator implements Iterator<Item> { 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 times current of best the was it null 48 Stack iterator: array implementation import java.util.Iterator; public class Stack<Item> implements Iterable<Item> { public Iterator<Item> iterator() { return new ReverseArrayIterator(); } private class ReverseArrayIterator implements Iterator<Item> { private int i = N; public boolean hasNext() { public void remove() { public Item next() { return i > 0; /* not supported */ return s[--i]; } } } } } i s[] N it was the best of times null null null null 0 1 2 3 4 5 6 7 8 9 49 Bag API Main application. Adding items to a collection and iterating (when order doesn't matter). a bag of marbles public class Bag<Item> implements Iterable<Item> Bag() create an empty bag void add(Item x) add( ) add( ) insert a new item onto bag int size() Iterable<Item> iterator() number of items in bag iterator for all items in bag for (Marble m : bag) process each marble m (in any order) Implementation. Stack (without pop) or queue (without dequeue). 50 1.3 B AGS , QUEUES, AND S TACKS stacks resizing arrays Algorithms R OBERT S EDGEWICK | K EVIN W AYNE http://algs4.cs.princeton.edu queues generics iterators applications 1.3 B AGS , QUEUES, AND S TACKS stacks resizing arrays Algorithms R OBERT S EDGEWICK | K EVIN W AYNE http://algs4.cs.princeton.edu queues generics iterators applications Java collections library List interface. java.util.List is API for an sequence of items. public interface List<Item> implements Iterable<Item> List() boolean isEmpty() int size() create an empty list is the list empty? 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) boolean contains(Item item) Iteartor<Item> iterator() return and delete item at given index does the list contain the given item? iterator over all items in the list ... Implementations. java.util.ArrayList uses resizing array; java.util.LinkedList uses linked list. 53 Java collections library java.util.Stack. Supports push(), pop(), and and iteration. Also implements java.util.List interface from previous slide, including, get(), remove(), and contains(). Bloated and poorly-designed API (why?) java.util.Queue. An interface, not an implementation of a queue. Best practices. Use our implementations of Stack, Queue, and Bag. 54 War story (from COS 226) Generate random open sites in an N-by-N percolation system. Jenny: percolates pick (i, j) at random; if already open, repeat. blocked site Takes ~ c1 N 2 seconds. Kenny: does not percolate create a java.util.ArrayList of N 2 closed sites. Pick an index at random and delete. open Takes ~ c2 N 4 seconds. site open site connected to top no open site connected to 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. 55 Stack 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. ... 56 Function 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) { if (q == 0) return p; (192, else return gcd(q,gcd p % q); 24) } static int gcd(int p, int q) { p = 192, q = 24 if (q == 0) return p; gcd else return gcd(q, p % (24, q); 0) } static int gcd(int p, int q) { if (q == 0) return p; p = 24, q = 0 else return gcd(q, p % q); } p = 216, q = 192 57 it is easy to convince yourself that it computes the proper value: any time the algorithm encounters a subexpression consisting of two operands separated by an opArithmetic expression evaluation erator, all surrounded by parentheses, it leaves the result of performing that operation on those operands on the operand stack. The result is the same as if that value had appeared in the input instead of the subexpression, so we can think of replacing valuethe stack 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 ) * ( single 4 * 5 ) ) )example, the algorithm comvalue. For 1 ((2+3)*(4*5))) putes the same value of all of these expres+ sions: 1 2 operand operator ( 1 ( 1 ( 1 ( 1 101 + + + + ( ( ( 5 ( 5 100 2 + 3 ) * ( 4 * 5 ) ) ) * ( 4 * 5 ) ) ) * 20 ) ) ) Two-stack algorithm. [E. W. Dijkstra] + +3)*(4*5))) 1 2 + + 3)*(4*5))) 1 2 3 + + )*(4*5))) (PROGRAM 4.3.5) is an implemen1 5 Value: push onto the stack. tationvalue of this method. This code is a simple *(4*5))) + example of an interpreter : a program that in1 5 Operator: push onto the stack.by a given terprets theoperator computation specified (4*5))) + * string and performs the computation to ar1 5 4 Left parenthesis: ignore. rive at the result. A compiler is a program that *5))) + * converts the string into code on a lower-level Right parenthesis: machine pop operator and two values; 1 5 4 that can do the job. This conversion 5))) + * * is a more complicated process than the steppush the result of applying that operator 1 5 4 5 by-step conversion used by an interpreter, but ))) + * * it is based the same underlying mechanism. to those values onto the on 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 maContext. An interpreter! chine that is easy to simulate on an actual computer. Trace of expression evaluation (Program 4.3.5) Evaluate 58 Dijkstra's two-stack algorithm demo value stack infix expression operator stack (fully parenthesized) ( 1 + ( ( 2 + operand 3 ) * ( 4 * 5 ) ) ) operator 59 Arithmetic expression evaluation public class Evaluate { public static void main(String[] args) { Stack<String> ops = new Stack<String>(); Stack<Double> vals = new Stack<Double>(); 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 60 Correctness 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. 61 Stack-based programming languages Observation 1. Dijkstra's two-stack 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, 62 1.3 B AGS , QUEUES, AND S TACKS stacks resizing arrays Algorithms R OBERT S EDGEWICK | K EVIN W AYNE http://algs4.cs.princeton.edu queues generics iterators applications Algorithms R OBERT S EDGEWICK | K EVIN W AYNE 1.3 B AGS , QUEUES, AND S TACKS stacks resizing arrays Algorithms F O U R T H E D I T I O N R OBERT S EDGEWICK | K EVIN W AYNE http://algs4.cs.princeton.edu queues generics iterators applications

Formatting page ...

raghucmrec chat

Horizontal lines at:
Guest Horizontal lines at:
AutoRM Data:
Box geometries: