Queue Using Stack
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

Question

Queue Using Stack

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

Accepted Answer

Costly enQueue

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.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the maximum number of elements which are in the stack at a time.

Since a maximum of N number of elements is stored in a stack at any given time, thus the space complexity will be O(N).

Time Complexity: OtherExplanation:

O(N * T), where 'N' is the maximum number of elements in the stack at any time and 'T' is the total number of queries to be performed.

The time complexities of individual operations are:

enQueue : O(N), where ‘N’ is the number of elements in the stack.

deQueue : O(1)

peek : O(1)

isEmpty : O(1)

Thus the time complexities of the operations are as described above.

Accepted Answer

Costly deQueue

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

Use two stacks, let us say ‘s1’ and ‘s2’. To insert into the queue, simply push the element at the top of ‘s1’. Now to perform the deQueue operation, we know that if elements are inserted in the order let us say: a1 then a2 then a3, then the removal will also be in the same order i.e a1 then a2 then a3. Thus for removal operation, we push all elements of ‘s1’ to ‘s2’ (to reverse their order of removal) and pop the top element of ‘s2’.

The advantage of this approach over the first one is that we don't need to transfer all elements from ‘s1’ to ‘s2’ every time. As long as ‘s2’ is not empty we don't need to transfer the elements from 's1' to 's2'.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the maximum number of elements which are in the stack at a time.

Since a maximum of N number of elements is stored in a stack at any given time, thus the space complexity will be O(N).

Time Complexity: OtherExplanation:

O(N * T), where 'N' is the maximum number of elements in the stack at any time and 'T' is the total number of queries to be performed.

The time complexities of individual operations are:

enQueue : O(1),

deQueue : O(N), where N is the maximum number of elements in the stack at any time.

peek : O(N), where N is the maximum number of elements in the stack at any time.

isEmpty : O(1)

Thus the time complexities of different operations are as described above.

Accepted Answer

One stack

This approach is slightly better than the second approach because here we use only one user stack and one function call stack which is nothing but recursion. The logic behind this approach is very much similar to the 2nd approach, except that we use only one user stack for the deQueue operation.

Let us assume that the stack defined is ‘s1’. To enQueue, we simply push the element to the top of ‘s1'. To perform the deQueue operation, we recursively pop the element from the top of ‘s1’ while the stack is not empty, and when we reach the end of the stack we return this element, and then push all the other elements to the stack to restore them, and return the last element in each recursion.

The difference between deQueue and peek operations is that, in peek operation we do not pop the last element of the stack but simply return it. This method is slightly better than approach 2 because, after each deQueue operation, all elements are restored in a single call.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the maximum number of elements which are in the stack at a time.

Since a maximum of N number of elements is stored in a stack at any given time, thus the space complexity will be O(N).

Time Complexity: OtherExplanation:

O(N * T), where 'N' is the maximum number of elements in the stack at any time and ‘T’ is the total number of queries to be performed.

The time complexities of individual operations are:

enQueue : O(1),

deQueue : O(N), where ‘N’ is the maximum number of elements in the stack at any time.

peek : O(N), where ‘N’ is the maximum number of elements in the stack at any time.

isEmpty : O(1)

Thus above described are the time complexities of the different operations.

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

Note:

Input Format:

Output Format:

Note:

Constraints:

Top Park Plus Full Stack Developer interview questions & answers

Popular interview questions of Full Stack Developer