CompSci 100E11.1Prefix 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 100E11.2Postfixnotationinactionÿ 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 100E11.3Postfixnotationinactionÿ For arithmetic expressions, is there more than one Postfix representation?A+B–C/D*EA*B*C/D*ECompSci 100E11.4Parentheses Matching Problemÿ How can we use a stack to check the syntactic correctness of expressions involving parentheses?if (msg.equals(txt.substring(3,n–2+txt.length())) Is there a simple solution not using stacks?ÿ What about including braces, brackets, angle-brackets, etc.?x = m[k] + w[msg.indexOf(s[n]]);CompSci 100E11.5Queue: 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 100E11.6Stack 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 100E11.7Using 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
View Full Document
Unlocking...