## Two Stacks Make A Queue

### November 8, 2013

In the previous exercise we used two queues to make a stack. In today’s exercise, we do the opposite: use two stacks to make a queue. This is exercise 10.1-6 from CLRS. In addition to solving the exercise, you should also create functions to implement a stack.

Show how to implement a queue using two stacks. Analyze the running time of the queue operations.

Your task is to write functions that use two stacks to implement a queue. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 2 Responses to “Two Stacks Make A Queue”

1. Implementation in Racket.

```#lang racket

(define empty-stack null)

(define (push stack x)
(cons x stack))

(define (pop stack)
(values (car stack) (cdr stack)))

(define empty-stack? null?)

(define (transfer src dst)
(cond [(empty-stack? src) dst]
[else
(define-values (x xs) (pop src))
(transfer xs (push dst x))]))

(define empty-queue (cons empty-stack empty-stack))

(define (enqueue queue x)
(match-define (cons xs ys) queue)
(cons (push xs x) ys))

(define (dequeue queue)
(match-define (cons xs ys) queue)
(cond [(empty-stack? ys)
(dequeue (cons empty-stack (transfer xs ys)))]
[else
(define-values (v q) (pop ys))
(values v (cons xs q))]))

(define (queue-empty? queue)
(and (null? (car queue))
(null? (cdr queue))))
```
2. svenningsson said

``type Queue a = ([a],[a])``
``````enqueue :: a -> Queue a -> Queue a