Two Queues Make A Stack

November 5, 2013

In the previous exercise we implemented queues. Today’s exercise will use those queues to solve exercise 10.1-7 from CLRS:

Show how to implement a stack using two queues. Analyze the running time of the stack operations.

You may assume that the queue operations enqueue, dequeue, and isEmpty are provided. You should provide the stack operations push, pop and isEmpty.

Your task is to implement stacks using two queues, as directed above. When you are finished, you are welcome to read 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
8 Comments »

8 Responses to “Two Queues Make A Stack”

  1. Jussi Piitulainen said
    November 5, 2013 at 10:14 AM

    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
    November 5, 2013 at 7:32 PM

    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. Adolfo Pérez Álvarez (@xardon) said
    November 7, 2013 at 3:55 PM

    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
    November 19, 2013 at 1:50 PM

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

  5. bob said
    November 19, 2013 at 1:55 PM

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

  8. Lal said
    July 2, 2014 at 1:04 PM

    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 comment