Two Queues Make A Stack

November 5, 2013

There are basically two ways to approach the problem, one that is efficient when pushing an element and one that is efficient when popping an element. We’ll call the two queues Q1 and Q2.

Efficient pushing: To push an element, enqueue the new element to Q1. To pop an element, dequeue everything except the last element from Q1 and enqueue the elements on Q2, dequeue the last element from Q2 and save it, swap the two queues, and return the saved element.

Efficient popping: To push an element, enqueue the new element to Q2, dequeue everything from Q2 and enqueue the elements on Q1, and swap the two queues. To pop the stack, dequeue the first element of Q1 and return it.

The isEmpty operation simply checks if both queues are empty. In both cases the time complexity is constant for the efficient operation but the other operation is linear in the number of elements in the stack, because each operation has to touch each element.

I’m sorry, but I don’t have time to write the code. My mother is unwell again, in hospital. First they said she had mild heart failure — I’m not sure how the adjective mild applies in that situation. Then they said the problem was fluid in the lungs, and they gave her a diuretic. Now she is dehydrated and receiving liquids. I’m not sure I understand, but she seems to be doing okay. Anyway, you’ll have to write the code yourselves, based on the outlines given above; will somebody please be sure to write a Scheme solution? Many thanks.

About these ads

Pages: 1 2

8 Responses to “Two Queues Make A Stack”

  1. Jussi Piitulainen said

    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.

  2. Robert Fisher said

    A C++ version using the standard library queues.

    #include <iostream>
    #include <queue>
    
    template<typename T>
    struct stack {
        std::queue<T> q1;
        std::queue<T> q2;
    
        void push(T t)
        { 
            q1.push(t);
        }
    
        T pop()
        {
            T t;
            while (!q1.empty()) {
                t = q1.front();
                q1.pop();
                if (!q1.empty()) q2.push(t);
            }
            while (!q2.empty()) {
                T x = q2.front();
                q2.pop();
                q1.push(x);
            }
            return t;
        }
    
        bool empty()
        {
            return q1.empty();
        }
    };
    
    int main()
    {
        stack<int> s;
        s.push(1);
        std::cout << s.pop() << std::endl;
        s.push(1);
        s.push(2);
        std::cout << s.pop() << std::endl;
        std::cout << s.pop() << std::endl;
        s.push(1);
        s.push(2);
        s.push(3);
        std::cout << s.pop() << std::endl;
        std::cout << s.pop() << std::endl;
        std::cout << s.pop() << std::endl;
    }
    
  3. Solution in SML, using the queues posted in the previous exercise.

    signature STACK = sig
        type 'a stack
    
        exception EmptyS
        val empty: 'a stack
        val push: 'a stack -> 'a -> 'a stack
        val pop: 'a stack -> 'a * 'a stack
    end
    
    functor QStack(Q: QUEUE) :> STACK = struct
        type 'a stack = 'a Q.queue * 'a Q.queue
    
        exception EmptyS
    
        val empty = (Q.empty, Q.empty)
    
        fun push (xs, ys) x = (Q.enqueue xs x, ys)
    
        fun isEmpty (xs, ys) = Q.isEmpty xs andalso Q.isEmpty ys
    
        fun popAndSwap (xs, ys) =
            let
                val (x, xs') = Q.dequeue xs
            in
                if Q.isEmpty xs'
                then (x, (ys, xs'))
                else popAndSwap (xs', Q.enqueue ys x)
            end
    
        fun pop (s as (xs, ys)) =
            if isEmpty s then raise EmptyS else popAndSwap s
    end
    

    Best wishes to you and your family.

  4. bob said

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

  5. bob said

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

  6. Lal said

    Let the two given queues be named as queue1 and queue2. The algorithm to implement a stack by using two queues works as :

    Push : Enqueue elements to queue1.
    Pop : Dequeue all the elements except the last one from queue1 into queue2.
    Return the last element of queue1.
    Interchange the names of queue1 and queue2.

    For example and code http://www.algoqueue.com/algoqueue/default/view/7798784/stack-using-queue

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

%d bloggers like this: