Implementing a Queue using two Stacks
September 17, 2013
Maximum distance with 50 bikes each having fuel capacity of 100 kms
September 18, 2013

Implement Stack using two Queues

We have seen the code to implement a Queue using two stacks. This question is opposite of that. Use only Queue data structure to implement a Stack.
The solution to this is similar to the previous post. We will use two Queues, Insertion into Stack (push operation) will insert element in one Queue and Pop operation (removing element from Stack) will remove the data from another Queue. Lets name the Queues as Queue1 and Queue2.
Ideally both push and pop operations should be constant time operations (O(1)). But that is the case when Stack is implemented using either Array or LinkedList data structure.
But if we are implementing Stack using Queue data structure, then both the operations cannot be constant time operations. At least one of the operations has to be expensive.
It assumes the Queue to be implemented as shown in this post
The class definition will look something like below:

class SpecialStack
{
public:
    void push (int data);
    int pop();
private:
    Queue queue1;
    Queue queue1;
};

Ideally such classes should be templates because we don’t want our Stack or Queue to be erstricted to store int data types only. so the production code generally is like:

template  class Stack
{
public:
    void push (T data);
    T pop();
private:
    Queue queue1;
    Queue queue1;
};

But we will stick to the previous definition only for sake of simplicity.
Method-1: Push is constant time but Pop operation is O(n) time

void SpecialStack::push(int data){
    queue1.enqueue(data)
}
int SpecialStack::pop(){
    int returnValue =-1; // indicate Stack Empty.
    while(!queue1.isEmpty())
    {
        returnValue = queue1.dequeue();
        // If it was last element of queue1. return it.
        if(queue1.isEmpty())
            break;
        else
            queue2.enqueue(returnValue);
    }
    // swap the names of queue1 and queue2.
    // If swapping is not possible then we will have to move all the elements from queue2 to queue1
    // or have another flag to indicate the active queue.
    Node * temp = queue1;
    queue1 = queue2;
    queue2 = temp;
    return returnValue;
}

Method-2: Pop is constant time but Push operation is O(n) time

void SpecialStack::push(int data){
    queue2.enqueue(data);
    while(!queue1.isEmpty()){
        queue2.enqueue(queue1.dequeue());
    }
    // swap the names of queue1 and queue2.
    // If swapping is not possible then we will have to move all the elements from queue2 to queue1
    // or have another flag to indicate the active queue.
    Node * temp = queue1;
    queue1 = queue2;
    queue2 = temp;
}
// Put proper check to see if no element in Queues
int SpecialStack::pop(){
  return queue.dequeue();
}

 

1 Comment

Leave a Reply to Anonymous Cancel reply

Your email address will not be published. Required fields are marked *