CSC 151-02, Fall 2006 : Schedule : Lab 39

Lab 39: Queues

Summary: In this lab, you will investigate some aspects of our implementation of the Queue ADT. You will also compare how an algorithm differs depending on whether it uses queues or stacks.

Contents:

• Preparation
• Exercises
  • Exercise 1: Comparing Stacks and Queues
  • Exercise 2: Observing the Implementation
  • Exercise 3: Printing Symbol Trees
  • Exercise 4: An Alternate Technique for Printing Trees

Preparation

Create a new file that contains the implementation of stacks from the reading on stacks and the implementation of queues from the reading on queues.

Exercises

Exercise 1: Comparing Stacks and Queues

Consider the following set of operations:

• add "Aardvark"
• add "Baboon"
• add "Civet"
• get and print a value
• add "Dingo"
• get and print a value
• get and print a value
• add "Emu"
• add "Frog"
• get and print any remaining values, one at a time
• add "Gnu"
• add "Hippo"
• get and print a value

a. What do you expect to happen if the add is treated as a stack-based push and the get as a stack-based pop? For example,

> (define s (make-stack))
> (s ':push! "Aardvark")
> (s ':push! "Baboon")
> (s ':push! "Civet")
> (s ':pop!)
...

b. Check your answer experimentally.

c. What do you expect to happen if the add is treated as a queue-based enqueue and the get as a queue-based dequeue? For example,

> (define q (make-queue))
> (q ':enqueue! "Aardvark")
> (q ':enqueue! "Baboon")
> (q ':enqueue! "Civet")
> (q ':dequeue!)
...

d. Check your answer experimentally.

Exercise 2: Observing the Implementation

While we want to limit information about the implementation to client programmers, it is often convenient when designing or debugging an object to add (temporary) methods that let us look more closely at that implementation.

a. Add a dump message to the queue implementation. When the queue receives this message, it should display both lists in whatever way you find most useful. For example

> (myqueue ':dump)

Front: (b c)
Back: (f e d)

b. Redo the enqueue and dequeue operations given in the previous exercise, observing the state of the queue after each step.

c. What, if anything, do your results tell you about our implementation?

Exercise 3: Printing Symbol Trees

As you may recall, a symbol tree is either (1) a symbol or (2) a pair of two symbol trees. Here's one technique for printing all the symbols in a tree, based on the concept fo deep recursion:

(define print-symbols
  (lambda (tree)
    (if (pair? tree)
        (begin
          (print-symbols (car tree))
          (print-symbols (cdr tree)))
        (begin
          (display tree)
          (newline)))))

a. What do you expect the output to be for the following tree?

(define animals
  (cons 
    (cons 
      (cons "Aardvark" "Baboon")
            "Chimp")
    (cons 
      "Dingo"
      (cons
        (cons "Emu" "Frog")
        (cons "Gnu" "Hippo")))))

b. Confirm your results experimentally.

c. It is also possible to write a flat-recursive procedure to print the tree by storing the subtrees to print in a queue. At each step, you get something from the queue. If it's a pair, you enqueue both subtrees. Otherwise, you print it out. You stop when the queue is empty. Here's a skeleton for such a procedure:

(define new-print-symbols
  (let ((queue (make-queue)))
    (letrec ((kernel
               (lambda ()
                 (if (queue ':empty?)
                     (newline)
                     (let ((subtree (queue ':dequeue!)))
                       (if (pair? subtree)
                           (begin
                            ...)
                           (begin
                            ...))
                       (kernel))))))
      (lambda (tree)
        (queue ':enqueue! tree)
        (kernel)))))

Finish implementing this procedure, enqueueing the left subtree before the right.

d. What do you expect the output to be given the tree above?

e. Check your results experimentally.

f. What do you expect to happen if you enqueue the right subtree before the left?

g. Check your results experimentally.

Exercise 4: An Alternate Technique for Printing Trees

a. Instead of using a queue for the procedure in the previous exercise, you could use a stack. Create a variant of that procedure that uses stacks instead of queues and that pushes the left subtree before the right.

b. What do you expect the output of your procedure to be given the tree above?

c. Check your results experimentally.

d. What do you expect the output to be if you push the right subtree before the left?

e. Check your results experimentally.

f. Of the four implementations, which is most like the original, deep recursive procedure?