Queue Using Stack

Posted: 20 Oct, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

Implement a queue data structure which follows FIFO(First In First Out) property, using only the instances of the stack data structure.

Note:
1. To implement means you need to complete some predefined functions, which are supported by a normal queue such that it can efficiently handle the given input queries which are defined below.

2. The implemented queue must support the following operations of a normal queue: 

a. enQueue(data): This function should take one argument of type integer and place the integer to the back of the queue.
b. deQueue(): This function should remove an integer from the front of the queue and also return that integer. If the queue is empty, it should return -1.
c. peek(): This function returns the element present in the front of the queue. If the queue is empty, it should return -1.
d. isEmpty(): This function should return true if the queue is empty and false otherwise.

3. You will be given q queries of 4 types:

a. 1 val - For this type of query, you need to insert the integer val to the back of the queue.
b. 2 - For this type of query, you need to remove the element from the front of the queue, and also return it.
c. 3 - For this type of query, you need to return the element present at the front of the queue(No need to remove it from the queue).
d. 4 - For this type of query, you need to return true if the queue is empty and false otherwise.
Input Format:
The first line contains an integer 'T’, which denotes the number of queries that will be run against the implemented queue.

Then 'T' lines follow. The i-th line contains the i-th query in the format as in the problem statement.

For the enQueue operation, the input line will contain two integers separated by a single space, representing the type of the operation in integer and the integer data being pushed into the queue.

For the rest of the queries, the input line will contain only one integer value, representing the query being performed.
Output Format:
For Query-1, you do not need to return anything.

For Query-2, return the integer being deQueued from the queue.

For Query-3, return the integer present in the front of the queue

For Query-4, return “true” if the queue is empty, “false” otherwise.
Note:
1. You are not required to print the output, It has already been taken care of. Just implement the given function.

2. You can only use the instances of the stack data structure i.e you can use the standard stack operations such as push to the top, pop the element from the top, etc.

3. You can also use the inbuilt stack data structure in some languages such as  C++, Java.

4. You can assume that the maximum capacity of the queue may be infinite.
Constraints:
1 <= T <= 1000
1 <= type <= 4
1<= data <= 10^9 

Where 'type' represents the type of query and 'data' represents the integer to be enQueued. 

Time limit: 1 sec
Approach 1

We can make the enQueue operation costly, and perform the deQueue and all other operations in constant time. 

 

We use two instances of the stack. Whenever we need to insert an element in the queue, we transfer all elements from stack 1 to stack 2, push the element in stack 1, and then again push all elements from stack 2 to stack 1. As the latest entered element is supposed to be at the back of the queue, this method ensures that this element is at the bottom of the stack.

 

The above strategy ensures that the oldest entered element will always remain at the top of stack 1 so that to perform the deQueue or the peek operation, we simply return the top element of stack 1.

Try Problem