New update is available. Click here to update.

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