Programming Praxis

Stacks are particularly easy in Scheme, because they can be implemented using lists:

(define sEmpty (list))
(define (sPush s x) (cons x s))
(define (sHead s) (if (null? s) (error 'sHead "oops") (car s)))
(define (sTail s) (if (null? s) (error 'sTail "oops") (cdr s)))
(define (sEmpty? s) (null? s))

There are basically two ways to implement the queue, similar to the two ways to implement the stack of the previous exercise; one way favors the enqueue operation and the other way favors the dequeue operation. Unlike the previous exercise, however, the two methods do not have equivalent run time. Here are the methods:

Costly dequeue: To enqueue, push x on S1. To dequeue, if S2 is empty, pop all elements of S1 and push them on S2, then pop the head of S2 and return it.

Costly enqueue: To enqueue, pop everything from S1 and push it on S2, push x on S1, then pop everything from S2 and push it on S1. To dequeue, pop an item from S1 and return it.

The costly-dequeue method is clearly better than the costly-enqueue method; it requires only one pass over the items in the queue rather than two. So that is what we will implement; a queue will be represented as a pair of stacks:

(define qEmpty
  (let ((s1 sEmpty) (s2 sEmpty))
    (cons s1 s2)))

(define (enQueue q x)
  (let ((s1 (car q)) (s2 (cdr q)))
    (cons (sPush s1 x) s2)))

(define (qHead q)
  (let ((s1 (car q)) (s2 (cdr q)))
    (cond ((and (sEmpty? s1) (sEmpty? s2))
            (error 'qHead "oops"))
          ((sEmpty? s2)
            (let loop ((s1 s1) (s2 s2))
              (if (sEmpty? s1)
                  (sHead s2)
                  (loop (sTail s1) (sPush s2 (sHead s1))))))
          (else (sHead s2)))))

(define (qTail q)
  (let ((s1 (car q)) (s2 (cdr q)))
    (cond ((and (sEmpty? s1) (sEmpty? s2))
            (error 'qHead "oops"))
          ((sEmpty? s2)
            (let loop ((s1 s1) (s2 s2))
              (if (sEmpty? s1)
                  (cons s1 (sTail s2))
                  (loop (sTail s1) (sPush s2 (sHead s1))))))
          (else (cons s1 (sTail s2))))))

(define (qEmpty? q)
  (let ((s1 (car q)) (s2 (cdr q)))
    (and (null? s1) (null? s2))))

With this definition, enQueue is O(1) and the two deQueue operations are both O(n). Here are some examples:

> (define q qEmpty)
> (set! q (enQueue q 1))
> (set! q (enQueue q 2))
> (qHead q)
1
> (set! q (qTail q))
> (set! q (enQueue q 3))
> (qHead q)
2
> (qEmpty? q)
#f
> (set! q (qTail q))
> (qHead q)
3
> (set! q (qTail q))
> (qEmpty? q)
#t

You can run the program at http://programmingpraxis.codepad.org/dKk6lzAj.

Pages: 1 2