CSC151 2007S, Class 53: Restricted-Access Collections: Stacks, Queues, and Priority Queues Admin: * Exam 3 returned today. Notes to be distributed later. * I do expect attendance in tomorrow's and Thursday's classes. * Although the syllabus has an assignment due Friday, that assignment is cancelled. * Grades to be distributed at the end of class on Thursday. Overview: * Keeping track of computing tasks. * Restricted-access collections: A general structure. * Stacks: FIFO collections. * Queues: LIFO collections. * Priority queues: Prioritized collections. Traditi9onally, when we recurse over trees, our code looks something like (define proc (lambda (tree) (if (pair? tree) (combine (proc (car tree)) (proc (cdr tree))) (base-computation tree) Two definitions of sum (define sum (lambda (lst) (if (null? lst) 0 (+ (car lst) (sum (cdr lst)))))) (define sum (lambda (lst) (letrec ((kernel (lambda (lst stuff) (if (null? lst) stuff (kernel (cdr lst) (+ stuff (car lst))))))) (kernel lst 0)))) In the first variation, it's a bit hard to keep track of what's going on because there's a hidden (+ _ (+ _ (+ _ ...)))a In the second variation, we could always see the status (display (list 'kernel lst stuff)) (newline) Can we make the implicit delayed computations explicit? * Mostly Question revisited: In the fractal rectangle, can *we* keep track of which rectangles are left to be drawn? Yes: Two parts to the solution * Need a way to represent a rectangle to be drawn (left top width height level) * Need a way to represent *all* the rectangles to be drawn * Something that supports: add, delete, and get (plus a few more operations) Question: How do you decide what to grab? * Grab things in the order they were added: Queue * Grab things in order of import: Priority Queue * Grab things in the reverse order in which they were added: Stack * Grab things random9ly