Implement Queue Using stack

Problem Statement

The problem statement here is to implement queue using stack. Queue is a linear data structure which follows First In First Out (FIFO) principle. This means that the element which is inserted first will be the one that will be removed first.

Stack is also a linear data structure which follows Last In First Out (LIFO) principle, means that the element inserted last in the stack will be the one to be removed first from the stack and vice versa.

By implementing queue using stack, we should be able to use the First In First Out functionality of the implmented queue with the help of push() and pop() functions. The implemented queue should be able to perform enqueue(insertion) and dequeue(removal) operations.

Example

Input:

queue = []

Operations = [ Push(1), Push(2), Push(3), Pop(), Pop() ]

Output:

For every operations queue will be upldated like: [ [1], [1, 2], [1, 2, 3], [2, 3], [3] ]

Explanation: The queue is using stack operations to implement FIFO functionality, so till the data is pushed to the queue, it will be [1, 2, 3] and for the first Pop() function the firstly entered element will be removed from the queue, so the queue will be [2, 3]. Now for the next Pop() operation, the element 2 will be removed from the queue as it is the most oldest element in the queue, now the queue is [3].

Constraints

$1 <= queue.length <= 1000$
$0 <= queue[i] <= 1000$

Approach 1: Making a dequeue operation costly

As we know that a queue follows FIFO functionality, so to implement queue using stack, we will have to make it in a way that the element entering first in the queue will be the first to be removed. This can be done by using two stacks. By using 2 stacks at a time, we can simply push the element in stack 1 and will pop the first occuring element by pushing all the elements of stack 1 to stack 2 and popping out the top element of stack 2.

In this approach to implement queue using stack, we are making the dequeue operation of one stack costly for reaching the functionality of a queue.

Algorithm: We can implement queue using stack using the below algorithm

Initialize 2 empty stacks s1 and s2

• For enqueue operation
  • push the element to the top of the stack s1.
• For deque operation
  • if s1 and s2 is empty, return -1 as the is no element to remove.
  • If s2 is empty, push all the elements of stack from s1 to s2.
  • remove the top element of the stack s2.

Complexity Analysis

Time Complexity:

• push operation: O(1) It is same as the push operation in the stack.
• pop operation: O(N). In the worst case we have empty whole of stack 1 into stack 2.

Space Complexity: O(N) => N space for storing N elements in the stacks.

C++ Implementation

Java Implementation

Python Implementation

Approach 2: Making a enqueue operation costly

In this approach to implement queue using stack, we are making use of 2 stacks for the opertions by making the enqueue operation of one stack costly for reaching the functionality of a queue.

Algorithm: We can implement queue using stack using the below algorithm

Initialize 2 empty stacks s1 and s2

• For enqueue operation
  • while the stack s1 is empty, push the element to stack s2.
  • else, push all the elements from stack s1 to stack s2, and push the element to the top of the stack s1.
  • Now, Push all the elements from stack s2 to stack s1.
• For deque operation
  • if the stack is empty, return -1.
  • Otherwise, pop and return the top element of the stack s1.

Complexity Analysis

Time Complexity:

• push operation: O(N) In the worst case we have empty whole of stack 1 into stack 2 and vice versa.
• pop operation: O(1). It is same as the pop operation in the stack.

Space Complexity: O(N) => N space for storing N elements in the stacks.

C++ Implementation

Java Implementation

Python Implementation