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

Posted by programmingpraxis
Filed in Exercises
2 Comments »

2 Responses to “Two Stacks Make A Queue”

  1. Adolfo Pérez Álvarez (@xardon) said
    November 9, 2013 at 11:47 PM

    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
    November 10, 2013 at 1:35 PM

    Haskell solution:

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

dequeue :: Queue a -> Maybe (a,Queue a)
dequeue ([],[]) = Nothing
dequeue (l,[]) = dequeue ([],reverse l)
dequeue (l,a:r) = Just (a,(l,r))

empty :: Queue a -> Bool
empty (l,r) = null l && null r

Leave a comment