Implement a Queue using Stack Data Structure

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


 

We know that queue is a First-In-First-Out (FIFO) data structure in which elements are removed in the same order in which they were added to the queue. In enqueue operation, we add items to the rear of the queue while in dequeue operation, we remove items from the front of the queue.

There are several ways to implement a queue using one or two stacks by tweaking their push and pop operations.

 

1. Using two stacks

The idea is to implement enqueue operation of queue in such a way that the first entered element always ends up at the top of the stack. To achieve this, we need an additional stack.

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

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

C++

Download   Run Code

Java

Download   Run Code

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

  1. To enqueue an item to the queue, we push the item into the first stack.
     
  2. To dequeue an item from the queue, we move elements from first stack to second stack if it is empty, and then return the top item from the second stack.
     

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

C++

Download   Run Code

Java

Download   Run Code

 

2. Using one stack with recursive call stack

We can also use an implicit stack (recursive call stack) along with an actual stack for constructing a queue. The dequeue operation pops all elements from the stack and store them in the call stack. When the stack is left with a single item, we remove and return that item. Finally, we push all elements back to the stack from the call stack when recursion unfolds.

C++

Download   Run Code

Java

Download   Run Code

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Anshul
Guest
Anshul

great article