Stack Exercise Solutions:

PART I

What's wrong with removing items from the rear of a queue?

To remove the last pair in a queue, we need to go to the previous pair,
set its cdr to be the empty list, and set the rear pointer appropriately.

Unfortunately, even though the queue stores a rear pointer, it's impossible
to get to the previous pair without first starting at the front and cdr'ing
through all the elements.  We'd like to be able to start at the rear and to
traverse the list backwards, but we can't.

Therefore, though Louis's implementation of a stack would have a push!
operation that's Theta(1), its pop! operation would be Theta(n), where n is
the number of items on the stack.

We can do better.



PART II

Here is a classic example of why using set! on (temporary) local variables
is a bad idea.  Think about the environment diagrams for this!

Let's look at using push!:

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

    > (define st (make-stack))
    > (push! st 1)

What is st now?  Has it changed at all?  When push! assigns a new value to
stack, it is changing the value of its LOCAL VARIABLE.  Thus, st remains
unchanged; it is bound to the same data structure as it was before.  In this
incorrect implementation, push! does NOT mutate the stack structure.



PART III

Louis has the right idea; we can make push! and pop! have Theta(1) running
time by cons'ing an item onto the front of a list and by removing the first
item with cdr.  The problem with his implementation is that it doesn't
mutate a data structure; we need to use set-car! or set-cdr!.

For mutation to work in this case, we'll need to use a dummy header. (If
you don't see why this is true, think about how you would represent an
empty stack, how you would add an item to it, and how you would remove this
solitary item.  Also see "Implementation: Why Dummy Headers?" in my Week 9
notes.)

    (define (make-stack) (list '*stack*))

    (define (contents tagged-list) (cdr tagged-list))

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

    (define (peek stack) (car (contents stack)))

    (define (push! stack item)
      (set-cdr! stack (cons item (contents stack)))
      stack)

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