Implementation of Queue using Stacks

Queue is a linear data structure that follows FIFO (First In First Out) principle in which insertion is performed from the rear end and the deletion is done from the front end. Stack is a linear data structure that follows LIFO (Last In First Out) principle in which both insertion and deletion are performed from the top of the stack.

Let's understand the implementation of Queue using stacks.

Suppose we have a queue shown as below:

Now we will perform three enqueue operations shown as below:

enqueue(5);

enqueue(2);

enqueue(3);

After performing the above three enqueue operations, the queue would look like:

In the above stack, we can observe that the topmost element is 3. If we perform the delete operation in the above stack, then the element 3 would be deleted from the stack. On the other hand, the deletion in Queue is performed from the front end and the front element is 5. In order to implement the Queue using Stack, we need to consider two stacks.

Suppose we have two stacks named as Stack1 and Stack2 shown as below:

As we can observe that above stacks are empty. Now, we will perform push operations on the Stack1. First, we will push 5, then 2 and finally we will push element 3 shown as below:

Now we will pop the elements from the Stack1 one by one and push them into the Stack2 as shown as below:

Once the elements are inserted into the Stack2, the topmost element is 5 so it would be popped out from the Stack 2 shown as below:

Once the topmost element is popped out from the Stack2, all the elements are moved back from Stack2 to Stack 1 shown as below:

There are two approaches to implement Queue using Stack:

• Making a dequeue operation costly
• Making a enqueue operation costly

First approach: Making a dequeue operation costly

If we implement the Queue using Stack by making a dequeue operation costly means that time complexity in enqueue operation would be O(1) and the time complexity in dequeue operation would be O(n).

In this case, when we insert the elements in the stack then the elements are added on the top of the stack so it takes O(1) time.

In case of dequeue operation, we need to consider two stacks named as Stack1 and Stack2. First, we insert the elements in the Stack1 and then we remove all the elements from the Stack1. Once all the elements are popped from the Stack1 then they are added in the Stack2. The topmost element would be popped out from the Stack2 and then all the elements from the Stack2 are moved back to Stack1. Here, dequeue operation is performed two times on the data so time complexity is O(n).

Implementation in C

Output

Second Approach: Making an enqueue operation costly.

If we implement the Queue using Stack by making a enqueue operation costly means that time complexity in enqueue operation would be O(n) and the time complexity in dequeue operation would be O(1).

First, we will consider two stacks named as stack1 and stack2. In case of enqueue operation, first all the elements will be popped from the stack1 and push it into the stack2. Once all the elements from the stack1 are pushed into the stack2, then the new element is added in the stack1. After adding the new element in the stack1, all the element are moved back from stack1 to stack2. Here, the time complexity of enqueue operation would be O(n).

In stack1, the oldest element would be at the top of the stack, so time taken to perform a dequeue operation would be O(1).

Implementation in C

Output