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.

About these ads

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

    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 Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 627 other followers

%d bloggers like this: