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.

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 612 other followers

%d bloggers like this: