Exercise:

In the same style as the queues of section 3.3.2, we are to create a stack
data type. It should be implemented as a list and should have:

* a constructor:
  (make-stack)
  returns an empty stack (a stack containing no items)

* two selectors:
  (empty-stack? <stack>)
  tests if the stack is empty.

  (peek <stack>)
  returns the object on the top of the stack, signaling an error if the
  stack is empty; it does not modify the stack.

* two mutators:
  (push! <stack> <item>)
  adds the item to the top of the stack and returns the modified stack as
  its value.

  (pop! <stack>)
  returns the object on the top of the stack and removes it, signaling an
  error if the stack is already empty.



PART I

Louis Reasoner says, "Implementing a stack isn't so hard!  We only need to
modify the queue ADT slightly to remove items from the rear instead of from
the front."

Oski M. Wizard comments, "That could work, but that implementation would be
horribly inefficient when popping items off the stack."

Explain what Oski means.



PART II

Louis Reasoner responds, "In that case, instead of implementing a stack by
adding and removing items from the end of a list, we can add and remove
items from the beginning." Louis writes the following code:

   (define (make-stack) '())

   (define (empty-stack? stack) (null? stack))

   (define (peek stack) (car stack))

   (define (push! stack item)
     (set! stack (cons item stack))
     stack)

   (define (pop! stack)
     (if (empty-stack? stack)
         (error "POP! called with an empty stack" stack)
         (let ((item (car stack)))
           (set! stack (cdr stack))
           item) ))

Oski M. Wizard interjects, "Well, now it won't work at all!"

What did Louis do wrong this time?



PART III

Implement the stack data type efficiently and correctly.  All operations
should be performed in Theta(1) time with respect to the size of the stack.