# Interview Questions

# Implement Stack using two Queues

- September 17, 2013
- Posted by: Kamal Rawat
- Category: Algorithms

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(); }

[…] Implement Stack using two Queues […]