CompSci 100E9.1Stack: What problems does it solve?ÿ Stacks are used to avoid recursion, a stack can replace the implicit/actual stack of functions called recursivelyÿ Stacks are used to evaluate arithmetic expressions, to implement compilers, to implement interpreters The Java Virtual Machine (JVM) is a stack-based machine Postscript is a stack-based language Stacks are used to evaluate arithmetic expressions in many languagesÿ Small set of operations: LIFO or last in is first out access Operations: push, pop, top, create, clear, size More in postscript, e.g., swap, dup, rotate, …CompSci 100E9.2Simple stack exampleÿ Stack is part of java.util.Collections hierarchy It's an OO abomination, extends Vector (like ArrayList)o Should be implemented using Vectoro Doesn't model "is-a" inheritance what does pop do? What does push do?Stack s = new Stack();s.push("panda");s.push("grizzly");s.push("brown");System.out.println("size = "+s.size());System.out.println(s.peek());Object o = s.pop();System.out.println(s.peek());System.out.println(s.pop());CompSci 100E9.3Implementation is very simpleÿ Extends Vector, so simply wraps Vector/ArrayList methods in better names push==add, pop==remove Note: code below for ArrayList, Vector is actually used.public Object push(Object o){add(o);return o;}public Object pop(Object o){return remove(size()-1);}CompSci 100E9.4Uses rather than "is-a"ÿ Suppose there's a private ArrayList, myStorage Doesn't extend Vector, simply uses Vector/ArrayList Disadvantages of this approach?o Synchronization issuespublic Object push(Object o){myStorage.add(o);return o;}public Object pop(Object o){return myStorage.remove(size()-1);}CompSci 100E9.5Postfix, prefix, and infix notationÿ Postfix notation used in some HP calculators No parentheses needed, precedence rules still respected35+ 42*7+3- 97+* Read expressiono For number/operand: pusho For operator: pop, pop, operate, pushÿ See Postfix.java for example code, key ideas: Use StringTokenizer, handy tool for parsing Note: Exceptions thrown, what are these? ÿ What about prefix and infix notations, advantages?CompSci 100E9.6Exceptionsÿ Exceptions are raised or thrown in exceptional cases Bad indexes, null pointers, illegal arguments, … File not found, URL malformed, …ÿ Runtime exceptions aren't meant to be handled or caught Bad index in array, don't try to handle this in code Null pointer stops your program, don't code that way!ÿ Other exceptions must be caught or rethrown See FileNotFoundException and IOException in Scanner class implementationÿ RuntimeException extends Exception, catch not requiredCompSci 100E9.7Prefix notation in actionÿ Scheme/LISP and other functional languages tend to use a prefix notation(define (square x) (* x x))(define (expt b n)(if (= n 0)1(* b (expt b (- n 1)))))CompSci 100E9.8Postfixnotationinactionÿ Practical example of use of stack abstractionÿ Put operator after operands in expression Use stack to evaluateo operand: push onto stacko operator: pop operands push resultÿ PostScript is a stack language mostly used for printing drawing an X with two equivalent sets of code%!200 200 moveto100 100 rlineto200 300 moveto100 –100 rlinetostroke showpage%!100 –100 200 300 100 100 200 200moveto rlineto moveto rlinetostroke showpageCompSci 100E9.9Queue: another linear ADTÿ FIFO: first in, first out, used in many applications Scheduling jobs/processes on a computer Tenting policy? Computer simulationsÿ Common operations Add to back, remove from front, peek at fronto No standard java.util.Queue, instead java.util.LinkedListo addLast(), getFirst(), removeFirst, size()o Can use add() rather than addLast();ÿ Downside of using LinkedList as queue Can access middle elements, remove last, etc. why?CompSci 100E9.10Stack and Queue implementationsÿ Different implementations of queue (and stack) aren’t really interesting from an algorithmic standpoint Complexity is the same, performance may change (why?) Use ArrayList, growable array, Vector, linked list, …o Any sequential structureÿ As we'll see java.util.LinkedList is good basis for all In Java 5, LinkedList implements the new Queue interfaceÿ ArrayList for queue is tricky, ring buffer implementation, add but wrap-around if possible before growing Tricky to get right (exercise left to reader)CompSci 100E9.11Using linear data structuresÿ We’ve studied arrays, stacks, queues, which to use? It depends on the application ArrayList is multipurpose, why not always use it?o Make it clear to programmer what’s being doneo Other reasons?ÿ Other linear ADTs exist List: add-to-front, add-to-back, insert anywhere, iterateo Alternative: create, head, tail, Lisp or o Linked-list nodes are concrete implementation Deque: add-to-front, add-to-back, random accesso Why is this “better” than an ArrayList?o How to implement?CompSci 100E9.12Jaron Lanier (http://www.advanced.org/jaron)Jaron Lanier is a computer scientist, composer, visual artist, and author. He coined the term ‘Virtual Reality’ … he co-developed the first implementations of virtual reality applications in surgical simulation, vehicle interior prototyping, virtual sets for television production, and assorted other areas"What's the difference between a bug and a variation or an imperfection? If you think about it, if you make a small change to a program, it can result in an enormous change in what the program does. If nature worked that way, the universe would crash all the time."Lanier has no academic
View Full Document
Unlocking...