CSC151.02, Class 53: Stacks Admin: * About the final (Thu of finals week, 9:00 a.m.) * Readings: Stacks, Queues * Questions on the exam? Overview: * Abstract data types (ADTs) * The stack ADT * Implementing stacks as objects * Using stacks Q: Does quicksort have to work on lists with repeated elements? A: No, it does not. However, it would be nice if it did. Two points of extra credit for handling repeated elements correctly. Q: How do we merge the two lists in Quicksort? A: Using append. (append (quicksort smaller) (list pivot) (quicksort bigger)) Q: Are all parts of question one weighted equally? A: I'll decide when I grade your exam. When computer scientists design big programs, they think carefully about how they use the data. A big part of program design ends up being the design of the functions for manipulating groups of data. * It is therefore worth identifying common collections of functions and implementing them well. Today we consider a particular group of functions and their associated "abstract data type", the stack. * What did I do with papers? * added them to the pile on my desk. (more adding) * looked at the thing on top. * removed the thing on top. * created a new pile. * (used the thing that was at the top) * (put 'em somewhere else, e.g., returned to the student with a big REWRITE) Stacks provide N basic operations: * push something on top of the stack * pop something from the top of the stack (remove it) * peek at what's on top of the stack * check if the stack is empty * create a new stack Once you have decided on a set of operations, you need a way to implement them. * We can represent the stack as a list. * To push something, we can cons it on at the beginning. * peek is just the car * To pop you 'set the list to the cdr of the list' (vector-set! vec 0 (cdr (vector-ref vec 0))) * How do we change a list? * We can define a new list. * Key idea: We put the list in a vector * When we need to "change" the list that represents the stack, we set the contents of the vector to the modified list. * How can we create the original stack? * need to decide on messages ':empty? ':peek ':pop! ':push! (define make-stack (lambda () (let ((vec (make-vector 1 null))) (lambda (message) (cond ((eq? message ':empty?) ; See if the list in the vector is null (null? (vector-ref vec 0))) (else (error "Can't understand that meaningless message."))))))) See the sample code for more details. Why are stacks useful? * Strange way of representing math: Reverse Polish Notation. Popular on HP calculators and some other geek toys. * param1 param2 op * Why is this useful? Gets rid of parantheses and precedence * How to implement RPN: When you see a number, push it on the stack. When you see an operation, pop the arguments off the stack, evaluate the operation, and push the result * It's what the HTML parser does. * Open tag: Shove it on the stack * Close tag: Look at the top of the stack * Matches: Pop it and go on * Doesn't match: Report an error * A way to get rid of deep recursion * E.g., sum-of-number-tree