Last Updated: 20 Oct, 2020
Queue Using Stack
Moderate
Asked in companies
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.
4. For every query of type:
a. 1, you do not need to return anything.
b. 2, return the integer being deQueued from the queue.
c. 3, return the integer present in the front of the queue.
d. 4, return “true” if the queue is empty, “false” otherwise.
Example
Operations:
1 5
1 10
2
3
4
Enqueue operation 1 5: We insert 5 at the back of the queue.
Queue: [5]
Enqueue operation 1 10: We insert 10 at the back of the queue.
Queue: [5, 10]
Dequeue operation 2: We remove the element from the front of the queue, which is 5, and print it.
Output: 5
Queue: [10]
Peek operation 3: We return the element present at the front of the queue, which is 10, without removing it.
Output: 10
Queue: [10]
IsEmpty operation 4: We check if the queue is empty.
Output: False
Queue: [10]
Input Format:
The first line contains an integer 'Q’, which denotes the number of queries that will be run against the implemented queue.
Then 'Q' 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, nothing is printed.
For Query-2, the integer returned from deQueue() is printed.
For Query-3, the integer returned from peek() is printed.
For Query-4, if isEmpty() returns true then “true” is printed, “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.
Approaches
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.
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'.
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.