Implement Stack using Queue Data Structure

In this post, we will see how to implement a stack data structure using queue in C++ and Java. In other words, design a stack that supports push and pop operations using standard enqueue and dequeue operations of the queue.


 

A stack is a Last-In-First-Out (LIFO) data structure in which elements are inserted and removed from one end of the stack known as top of the stack. It has two major operations: The push operation which adds an element to the stack, and pop operation, which removes the most recently added element from the stack which is not yet removed.

There are several ways to implement a stack using one or two queues by tweaking their enqueue and dequeue operations.

 

1. Using two queues:

The idea is to implement push operation of queue in such a way that the last entered item always ends up at the front of the queue. To achieve this, we need an additional queue.

  1. To push an item in the stack, we first move all elements from the first queue to the second queue, then push new item into the first queue, and finally move all elements back to the first queue. This ensures that the new item lies at front of the queue and hence would be the first one to be removed.
     
  2. To pop an item from the stack, we simply return the front item from the first queue.
     

Below is C++ and Java implementation of the idea:

C++

Download   Run Code

Output:

5
4
3
2
1
Underflow!!

Java

Download   Run Code

Output:

5
4
3
2
1
Underflow!!

 
Note that the elements are exchanged between the queue twice for every push operation. This can impact performance if push operations are frequent. Here’s an alternative approach which effects time complexity of the pop operation instead of push operation.

  1. To push an item to the stack, we add the item into the first queue.
     
  2. To pop an item from the stack, we move all elements from first queue to second queue except the last element, and then return the last element after moving all elements back to the first queue.
     

Below is C++ and Java implementation of the idea:

C++

Download   Run Code

Output:

5
4
3
2
1
Stack Underflow!!

Java

Download   Run Code

Output:

5
4
3
2
1
Stack Underflow!!

 

2. Using one queue with recursive call stack

We can also use an implicit stack (recursive call stack) along with a queue to construct a stack as shown below in C++ and Java:

C++

Download   Run Code

Output:

5
4
3
2
1
Underflow!!

Java

Download   Run Code

Output:

5
4
3
2
1
Underflow!!

 
1 Star2 Stars3 Stars4 Stars5 Stars (5 votes, average: 4.80 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of