Queue Using Two Stacks

Easy
0/40
Average time to solve is 15m
profile
Contributed by
25 upvotes
Asked in companies
AmazonGoogleMicrosoft

Problem statement

You will be given ‘Q’ queries. You need to implement a queue using two stacks according to those queries. Each query will belong to one of these three types:

1 ‘X’: Enqueue element ‘X’  into the end of the nth queue. Returns true after the element is enqueued.

2: Dequeue the element at the front of the nth queue. Returns -1 if the queue is empty, otherwise, returns the dequeued element.
Note: 
Enqueue means adding an element to the end of the queue, while Dequeue means removing the element from the front of the queue.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer ‘Q’ denoting the number of queries. 

The next ‘Q’ lines specify the type of operation/query to be performed on the data structure.

Each query contains an integer ‘P’ denoting the type of query.

For query of type 1, the integer ‘P’ is equal to 1 and it is followed by one integer ‘X’ denoting the element on which operation is to be performed.

For query of type 2, the integer ‘P’ is equal to 2 which dequeues the element.
Output Format: 
For each query, return the output returned after performing the corresponding operation on the data structure.
Note: 
You don’t need to print anything. It has already been taken care of. Just implement the given functions.
Constraints: 
1 <= Q <= 10^5 
1 <= P <= 2
1 <= X <= 10^5

Time limit: 1 sec
Sample Input 1:
7
1 2 
1 3 
2 
1 4 
1 6 
1 7 
2
Sample Output 1:
True 
True
2
True
True
True
3
Explanation of Sample Output 1:
For this input, we have the number of queries, 'Q' = 7.

Operations performed on the queue are as follows:

push(2): Push element ‘2’ into the queue. This returns true.
push(3): Push element ‘3’ into the queue. This returns true.
pop(): Pop the top element from the queue. This returns 2.
push(4): Push element ‘4’ into the queue. This returns true.
push(6): Push element ‘6’ into the queue. This returns true.
push(7): Push element ‘7’ into the queue. This returns true.
pop(): Pop the top element from the queue. This returns 3.
Sample Input 2:
7
1 11 
1 51 
1 26 
2 
1 6
2
2
Sample Output 2:
True
True
True
11
True
51
26
Explanation for Sample Output 2:
For this input, we have the number of queries, Q = 7.

Operations performed on the queue are as follows:

push(11): Push element ‘11’ into the queue. This returns true.
push(51): Push element ‘51’ into the queue. This returns true.
push(26): Push element ‘26’ into the queue. This returns true.
pop(): Pop the top element from the queue. This returns 11.
push(6): Push element ‘6’ into the queue. This returns true.
pop(): Pop the top element from the queue. This returns 51.
pop(): Pop the top element from the queue. This returns 26.
Hint

Can you think of making the enqueue operation costly?

Approaches (2)
Making the Enqueue operation costly

In this approach, we make sure that the oldest element added to the queue stays at the top of the stack, the second oldest below it and so on. To achieve this, we will need two stacks. 

 

First stack('STK1') is the main stack being used to store the data, while the second stack('STK2') is to assist and store data temporarily during various operations.

 

Following steps will be involved while enqueuing a new element to the queue:

 

  1. If the queue is empty(means 'STK1' is empty), directly push the first element onto the stack 'STK1'.
  2. If the queue is not empty:
    • move all the elements present in the first stack('STK1') to the second stack('STK1'), one by one.
    • Then add the new element to the first stack, then move back all the elements from the second stack back to the first stack.
  3. Doing so will always maintain the right order of the elements in the stack, with the 1st data element staying always at the top, with the 2nd data element right below it and the new data element will be added to the bottom.

 

This makes removing an element from the queue very simple, all we have to do is call the pop() method for stack 'STK1'.

Time Complexity

O(N), Where ‘N’ is the size of the queue.

 

Push operation: O(N)

 

Since we have to empty the whole elements of ‘STK1’ into ‘STK2’ and back again to ‘STK1’, it takes O(N) time.

 

Pop operation: O(1)

 

Since we just need to pop the top element of the stack which takes O(1) time.

Space Complexity

O(N), Where ‘N’ is the size of the queue.

 

Since we are using two stacks where each stack stores at max ‘N’ elements, so the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Queue Using Two Stacks
Full screen
Console