## Two Stacks Make A Queue

### November 8, 2013

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

Implementation in Racket.

Haskell solution: