## Two Queues Make A Stack

### November 5, 2013

In the previous exercise we implemented queues. Today’s exercise will use those queues to solve exercise 10.1-7 from CLRS:

Show how to implement a stack using two queues. Analyze the running time of the stack operations.

You may assume that the queue operations enqueue, dequeue, and isEmpty are provided. You should provide the stack operations push, pop and isEmpty.

Your task is to implement stacks using two queues, as directed above. When you are finished, you are welcome to read a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

This uses the queues from that previous exercise. In both implementations, the stack is represented as just one queue. The auxiliary queue is made when needed.

(define (make-stack) (make-queue))

(define (push1 s x) (enqueue s x))

(define (top1 s)

(do ((q s (tail q)))

((empty? (tail q)) (head q))))

(define (pop1 s)

(do ((p (make-queue) (enqueue p (head q)))

(q s (tail q)))

((empty? (tail q)) p)))

(define (push2 s x)

(do ((p (enqueue (make-queue) x)

(enqueue p (head q)))

(q s (tail q)))

((empty? q) p)))

(define (top2 s) (head s))

`(define (pop2 s) (tail s))`

This test procedure takes the implemented operations as arguments.

(define (test make push top pop) ;expect (o x o x)

(list (top (push (make) 'o))

(top (push (push (make) 'o) 'x))

(top (pop (push (push (make) 'o) 'x)))

(if (empty? (pop (push (make) 'o))) 'x 'o)))

Best wishes.

A C++ version using the standard library queues.

Solution in SML, using the queues posted in the previous exercise.

Best wishes to you and your family.

(define (gcd m n)

(cond ((< m n) (gcd m (- n m)))

((< n m) (gcd (- m n) n))

(else m)))

(define (gcd m n)

(cond ((< m n) (gcd m (- n m)))

((< n m) (gcd (- m n) n))

(else m)))

http://codepad.org/Fpq3TtJV