Quiz 3
======

Here are some exercises that you may work with in order to prepare for the
third and the final quiz in the course. 

Jalal

---------------------------------------------------------------------

Exercise 3.16

---------------------------------------------------------------------

Exercise 3.17

---------------------------------------------------------------------

Exerecise 3.20

---------------------------------------------------------------------

Study the representation of a queue on pages 261-265 of the course
book and solve the following exercises: 

Exercise 3.21

Exercise 3.22

---------------------------------------------------------------------

In the following piece of code, the data structure stack is
implemented as a procedure with local state. The procedure make-stack
creates a stack whose local state consists of a list of the items on
the stack. A stack accepts requests to push an item onto the stack, to
pop the top item off the stack and return it, and to initialize the
stack to empty.

Create a few stacks in DrScheme and test the PUSH and POP operations
on them so that you get a good understanding of how stack works.

(define (make-stack)
  (let ((s '()))
    (define (push x)
      (set! s (cons x s)))
    (define (pop)
      (if (null? s)
          (error "Empty stack -- POP")
          (let ((top (car s)))
            (set! s (cdr s))
            top)))
    (define (initialize)
      (set! s '())
      'done)
    (define (dispatch message)
      (cond ((eq? message 'push) push)
            ((eq? message 'pop) (pop))
            ((eq? message 'initialize) (initialize))
            (else (error "Unknown request -- STACK"
                         message))))
    dispatch))

This is how we will use the stack:

   (define s (make-stack))
   ((s 'push) 1)         ; push 1 into the stack
   ((s 'push) 3)         ; push 3 into the stack
   (s 'pop)              ; remove 3 from the stack

Now that you know how this structure works, implement the following:

1) Add the method empty? to this stack implementation so that we can
   test whether the stack is empty or not. This is how we expect it to
   work:

   (s 'empty?)  will return #t if the stack is empty otherwise #f

2) Write the procedure stack->list that will take a stack as argument
   and return a list containing the elements of that stack. This will
   be done by iteratively popping elements from the stack until it
   is empty.

   > (define s (make-stack))
   > ((s 'push) 1)    
   > ((s 'push) 3)
   > ((s 'push) 'x)

   > (s 'pop)
   x

   > ((s 'push) 'g)

   > (stack->list s)  
   (g 3 1)
--------------------------------------------------------------------

Explain what the result of the following sequence of definitions and
set-statements is.

  (define x 10)
  (define y 20)
  (set! x (+ x y))
  (set! y (- x y))
  (set! x (- x y))