Stack using Queue
A Stack is a Last In First Out(LIFO) structure, i.e, the element that is added last in the stack is taken out first. Our goal is to implement a Stack using Queue for which will be using two queues and design them in such a way that pop operation is same as dequeue but the push operation will be a little complex and more expensive too.
Implementation of Stack using Queue
Assuming we already have a class implemented for Queue, we first design the class for Stack. It will have the methods
pop() and two queues.
// two queue
Queue Q1, Q2;
// push method to add data element
// pop method to remove data element
Inserting Data in Stack
Since we are using Queue which is First In First Out(FIFO) structure , i.e, the element which is added first is taken out first, so we will implement the push operation in such a way that whenever there is a pop operation, the stack always pops out the last element added.
In order to do so, we will require two queues,
Q2. Whenever the push operation is invoked, we will enqueue(move in this case) all the elements of
Q2 and then enqueue the new element to
Q1. After this we will enqueue(move in this case) all the elements from
Q2 back to
So let's implement this in our code,
void Stack :: push(int x)
// move all elements in Q1 to Q2
int temp = Q1.deque();
// add the element which is pushed into Stack
// move back all elements back to Q1 from Q2
int temp = Q2.deque();
It must be clear to you now, why we are using two queues. Actually the queue
Q2 is just for the purpose of keeping the data temporarily while operations are executed.
In this way we can ensure that whenever the pop operation is invoked, the stack always pops out the last element added in
Removing Data from Stack
Like we have discussed above, we just need to use the dequeue operation on our queue
Q1. This will give us the last element added in Stack.
int Stack :: pop()
Time Complexity Analysis
When we implement Stack using a Queue the push operation becomes expensive.
- Push operation: O(n)
- Pop operation: O(1)
When we say "implementing Stack using Queue", we mean how we can make a Queue behave like a Stack, after all they are all logical entities. So for any data structure to act as a Stack, it should have
push() method to add data on top and
pop() method to remove data from top. Which is exactly what we did and hence accomplished to make a Queue(in this case two Queues) behave as a Stack.