Queue Using Stack

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.

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]

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.

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.

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.

Here we have seven queries in total. Query 1: Insert 1 to the back of the queue. The queue: 1 Query 2: Insert 2 to the back of the queue. The queue: 1 2 Query 3: Insert 3 to the back of the queue. The queue: 1 2 3 Query 4: Remove element from the front: The queue: 2 3 Query 5: Remove the element from the front: The queue: 2 Query 6: Remove the element from the front: The queue : Query 7: As the queue is empty, returned -1.

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.

Time Complexity

O(N * Q), where 'N' is the maximum number of elements in the stack at any time and 'Q' 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.

Space Complexity

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).

Problem statement

Sample Input 1:

Sample Output 1:

Explanation of the Sample Output 1:

Sample Input 2:

Sample Output 2:

Explanation of the Sample Output 2:

Constraints: