Laboratory: Stacks, Queues, and
Priority Queues
Exercise 1: Exploring Linear Structures
The mass of code that you just loaded includes a procedure called
collection.test0. Look at the code for that
procedure and explain what it does.
a. If you have not modified the code you copied and pasted, stacks
are currently set as the default collection (that is, what
we use when we call collection.____). What
output do you expect to get when you run
collection.test0?
b. Check your answer experimentally.
> (collection.test0)
c. Comment out the lines that tell DrFu to use the stack procedures
as the collection procedures and then uncomment the lines that tell
DrFu to use the queue procedures.
d. What output do you expect to get when you run
collection.test0?
e. Check your answer experimentally.
f. Comment out the lines that tell DrFu to use the queue procedures
as the collection procedures and then uncomment the lines that tell
DrFu to use the priority queue procedures.
g. What output do you expect to get when you run
collection.test0?
h. Check your answer experimentally.
Exercise 2: Exploring Linear Structures, Revisited
The code also includes a procedure named
collection.test1 that tests not just what happens
when you add a bunch of values and then remove them, but also what
happens when you alternately add and remove values. Read that procedure
and make sure that you understand what it does.
a. What output do you expect collection.test1 to
have if we use stacks to implement collections?
b. Check your answer experimentally.
> (collection.test1)
c. What output do you expect collection.test1 to
have if we use queues to implement collections?
d. Check your answer experimentally.
e. What output do you expect collection.test1 to
have if we use priority queues to implement collections?
f. Check your answer experimentally.
Exercise 3: Simple Fractal Rectangles
Review the code to the new version of the simple-fractal-rectangle! procedure.
a. Uncomment the lines that tell DrFu to use queues as the mechanism for
implementing collections.
b. How do you expect simple-fractal-rectangle! to
draw a level-2 fractal rectangle? (That is, in what order will it draw
rectangles?)
c. Check your answer experimentally.
> (simple-fractal-rectangle! canvas color.red 0 0 199 199 2)
d. Suppose we tell DrFu to use priority queues as the mechanism for
implementing collections. In what order will it draw the rectangles
in a level-2 fractal rectangle?
e. Check your answer experimentally.
f. Uncomment the line in simple-fractal-rectangle!
that prints out the current collection of remaining tasks. Rerun
the command to print out a level-2 fractal rectangle. Explain the
results you get.
g. Re-comment that line.
Exercise 4: Randomizing Drawing Order
For this exercise, keep priority queues as your implementation of
collections.
Update simple-fractal-rectangle! so that it
chooses a random priority for each sub-rectangle rather than a priority
of 0.
a. What effect do you have this to happen when we draw a level-3 fractal
rectangle?
b. Check your answer experimentally.
> (simple-fractal-rectangle! canvas color.blue 0 0 199 199 3)
Exercise 5: Simulating Deep Recursion with Stacks
As you may have observed, neither queues nor priority queues give the
same behavior as the original recursive procedure. Why? Because
Scheme completely finishes one call (e.g., to draw a single rectangle
by drawing all of its sub-rectangles). As the reading suggested, this
behavior is much more stack-like than queue-like.
For this exercise, make stacks the default implementation of collections.
a. How do you expect simple-fractal-rectangle! to
draw a level-2 fractal rectangle? (That is, in what order will it draw
rectangles?)
b. Check your answer experimentally.
> (simple-fractal-rectangle! canvas color.red 0 0 199 199 2)
c. As you may have observed, the behavior is similar to that of the
original fractal rectangle procedure (that is, we completely finish
one rectangle before going on to the next), with one important
difference: Instead of starting in the upper-left corner, it starts
in the lower-right. Let's figure out why. First, uncomment the
line that prints the collection. Next, draw a level 1 rectangle.
What do you notice about the structure of the stack?
d. Using what you've just learned (ask a teacher or TA if you didn't
figure it out), rewrite simple-fractal-rectangle!
so that it draws the rectangles in the “correct” order.
e. What effect do you expect this rewriting to have on the
behavior of simple-fractal-rectangle!
if we use queues or priority queues?
; +--------+----------------------------------------------------------
; | Stacks |
; +--------+
(define stack.new
(lambda ()
null))
(define stack.get
(lambda (stuff)
(if (null? stuff)
(throw "Cannot get values from empty stacks.")
(car stuff))))
(define stack.drop
(lambda (stuff)
(if (null? stuff)
(throw "Cannot remove values from empty stacks.")
(cdr stuff))))
(define stack.add
(lambda (stuff val prio)
(cons val stuff)))
(define stack.empty?
(lambda (stuff)
(null? stuff)))
; +--------+----------------------------------------------------------
; | Queues |
; +--------+
; Queues are implemented as a vector of two lists, front and back. We remove
; elements from front and add elements to back. Here's the trick: When we
; run out of elements in front, we move the elements in back to front,
; reversing their order.
(define queue.new
(lambda ()
(vector null null)))
(define queue.get
(lambda (stuff)
(cond
((queue.empty? stuff)
(throw "Cannot get values from an empty collection."))
((null? (vector-ref stuff 0))
(car (reverse (vector-ref stuff 1))))
(else
(car (vector-ref stuff 0))))))
(define queue.drop
(lambda (stuff)
(cond
((queue.empty? stuff)
(throw "Cannot drop values from an empty collection."))
((null? (vector-ref stuff 0))
(vector (cdr (reverse (vector-ref stuff 1))) null))
(else
(vector (cdr (vector-ref stuff 0)) (vector-ref stuff 1))))))
(define queue.add
(lambda (stuff val prio)
(vector (vector-ref stuff 0) (cons val (vector-ref stuff 1)))))
(define queue.empty?
(lambda (stuff)
(and (null? (vector-ref stuff 0))
(null? (vector-ref stuff 1)))))
; +-----------------+-------------------------------------------------
; | Priority Queues |
; +-----------------+
; A priority queue is a list of (value . priority) pairs, kept in order by
; priority. We use techniques similar to those for insertion sort to keep
; the queue in order.
(define priority-queue.new
(lambda ()
null))
(define priority-queue.get
(lambda (stuff)
(if (null? stuff)
(throw "Cannot get a value from an empty collection.")
(car (car stuff)))))
(define priority-queue.drop
(lambda (stuff)
(if (null? stuff)
(throw "Cannot drop a value from an empty collection.")
(cdr stuff))))
(define priority-queue.add
(lambda (stuff val prio)
(cond
((null? stuff)
(list (cons val prio)))
((< prio (cdr (car stuff)))
(cons (cons val prio) stuff))
(else
(cons (car stuff) (priority-queue.add (cdr stuff) val prio))))))
(define priority-queue.empty?
(lambda (stuff)
(null? stuff)))
; +----------------------------+--------------------------------------
; | Choosing Linear Structures |
; +----------------------------+
(define collection.new stack.new)
(define collection.get stack.get)
(define collection.drop stack.drop)
(define collection.add stack.add)
(define collection.empty? stack.empty?)
;(define collection.new queue.new)
;(define collection.get queue.get)
;(define collection.drop queue.drop)
;(define collection.add queue.add)
;(define collection.empty? queue.empty?)
;(define collection.new priority-queue.new)
;(define collection.get priority-queue.get)
;(define collection.drop priority-queue.drop)
;(define collection.add priority-queue.add)
;(define collection.empty? priority-queue.empty?)
; +---------+---------------------------------------------------------
; | Testing |
; +---------+
(define collection.test0
(letrec ((get-print-drop
(lambda (stuff)
(display "Removing: ")
(display (collection.get stuff))
(newline)
(collection.drop stuff)))
(dump
(lambda (stuff)
(if (not (collection.empty? stuff))
(dump (get-print-drop stuff))))))
(lambda ()
(let* ((c0 (collection.new))
(c1 (collection.add c0 "a" 5))
(c2 (collection.add c1 "b" 2))
(c3 (collection.add c2 "c" 3))
(c4 (collection.add c3 "d" 6)))
(dump c4)))))
(define collection.test1
(letrec ((get-print-drop
(lambda (stuff)
(display "Removing: ")
(display (collection.get stuff))
(newline)
(collection.drop stuff)))
(dump
(lambda (stuff)
(if (not (collection.empty? stuff))
(dump (get-print-drop stuff))))))
(lambda ()
(let* ((c0 (collection.new))
(c1 (collection.add c0 "a" 5))
(c2 (collection.add c1 "b" 2))
(c3 (collection.add c2 "c" 3))
(c4 (collection.add c3 "d" 6))
(c5 (get-print-drop c4))
(c6 (get-print-drop c5))
(c7 (collection.add c6 "e" 1))
(c8 (collection.add c7 "f" 7))
(c9 (collection.add c8 "g" 2))
(c10 (get-print-drop c9))
(c11 (collection.add c10 "h" 5)))
(dump c11)))))
; +-------------------+-----------------------------------------------
; | Fun With Fractals |
; +-------------------+
(define simple-fractal-rectangle!
(lambda (image color left top right bottom level)
(letrec
; Process the task at the front of the collection,
; returning the modified collection.
((process-rect
(lambda (rect remaining-tasks)
; Note: Each task is a vector of the form
; #(color left top right bottom level)
(let ((color (vector-ref rect 0))
(left (vector-ref rect 1))
(top (vector-ref rect 2))
(right (vector-ref rect 3))
(bottom (vector-ref rect 4))
(level (vector-ref rect 5)))
; Draw the rectangle (we may draw over it)
(envt.set-fgcolor! color)
(image.select-rectangle! image selection.replace
left top
(- right left)
(- bottom top))
(image.fill! image)
(image.select-nothing! image)
(envt.update-displays!)
(cond
; Base case: We're done, so return the remaining tasks
((= level 0)
remaining-tasks)
; Otherwise, add the remaining tasks.
(else
(let ((midcol (round (* 0.5 (+ left right))))
(midrow (round (* 0.5 (+ bottom top))))
(nextlevel (- level 1)))
(display (list 'midcol midcol 'midrow midrow)) (newline)
(let* ((rect1 (vector (rgb.lighter color)
left top midcol midrow (- level 1)))
(rect2 (vector (rgb.darker color)
midcol top right midrow (- level 1)))
(rect3 (vector (rgb.darker color)
left midrow midcol bottom (- level 1)))
(rect4 (vector color
midcol midrow right bottom (- level 1)))
(c1 (collection.add remaining-tasks rect1 0))
(c2 (collection.add c1 rect2 0))
(c3 (collection.add c2 rect3 0))
(c4 (collection.add c3 rect4 0)))
c4)))))))
(kernel
(lambda (tasks)
; Uncomment the following line to keep track of the tasks
; left to do.
;(display tasks) (newline)
(if (collection.empty? tasks)
'Success
(kernel (process-rect (collection.get tasks)
(collection.drop tasks)))))))
(kernel (collection.add (collection.new)
(vector color left top right bottom level)
0)))))
