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