This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Queue using Stacks”.
1. You are asked to perform a queue operation using a stack. Assume the size of the stack is some value ‘n’ and there are ‘m’ number of variables in this stack. The time complexity of performing deQueue operation is (Using only stack operations like push and pop)(Tightly bound).
D) Data is insufficient
Explanation: You must pop each element from the first stack and push it into the second stack to perform the deQueue process. In this scenario, you must pop ‘m’ times and execute ‘m’ times of push operations. Then you pop the first element from the second stack (at a constant rate) and move all of the elements to the first stack (as before) (‘m-1′ times). As a result, the time complexity is O. (m).
2. Consider you have a stack whose elements in it are as follows.
5 4 3 2 << top
Where the top element is 2.
You need to get the following stack
6 5 4 3 2 << top
The operations that needed to be performed are (You can perform only push and pop):
A) Push(pop()), push(6), push(pop())
B) Push(pop()), push(6)
C) Push(pop()), push(pop()), push(6)
Explanation: 2 3 4 5 top is obtained by executing push(pop()) on all elements on the current stack to the next stack. You’ll get 6 5 4 3 2 top if you push(6) and then push(pop()). You’ve simply used push and pop to conduct an enQueue process.
3. Why is implementation of stack operations on queues not feasible for a large dataset (Asssume the number of elements in the stack to be n)?
A) Because of its time complexity O(n)
b) Because of its time complexity O(log(n))
c) Extra memory is not required
d) There are no problems
Explanation: To perform Queue operations such as enQueue and deQueue there is a need of emptying all the elements of a current stack and pushing elements into the next stack and vice versa. Therfore it has a time complexity of O(n) and the need of extra stack as well, may not be feasible for a large dataset.
4. You have two jars, one jar which has 10 rings and the other has none. They are placed one above the other. You want to remove the last ring in the jar. And the second jar is weak and cannot be used to store rings for a long time.
A) Empty the first jar by removing it one by one from the first jar and placing it into the second jar
B) Empty the first jar by removing it one by one from the first jar and placing it into the second jar and empty the second jar by placing all the rings into the first jar one by one
C) There exists no possible way to do this
D) Break the jar and remove the last one
Explanation: This is equivalent to just using push and pop to execute a dequeue process. The contents of the first jar are passed to the second jar. Remove all of the elements from the second jar and put them in the first jar after removing the last element from the first jar.
5. Given an array of size n, let’s assume an element is ‘touched’ if and only if some operation is performed on it(for example, for performing a pop operation the top element is ‘touched’). Now you need to perform Dequeue operation. Each element in the array is touched atleast?
D) Four times
Explanation: Each element from the first stack is popped, then pushed into the second stack; a dequeue operation is then performed on the top of the stack; and finally, each element from the second stack is popped, then pushed into the first stack. As a consequence, each aspect is treated four times.
6. Given only a single array of size 10 and no other memory is available. Which of the following operation is not feasible to implement (Given only push and pop operation)?
Explanation: Another array of the same size is needed to perform Enqueue using only push and pop operations. However, since there is no additional memory available, the provided operation is not possible.
7. Consider yourself to be in a planet where the computational power of chips to be slow. You have an array of size 10.You want to perform enqueue some element into this array. But you can perform only push and pop operations .Push and pop operation both take 1 sec respectively. The total time required to perform enQueue operation is?
Explanation: To begin, empty all of the current stack’s elements into the temporary stack, then push the necessary element and empty the temporary stack’s elements into the original stack. As a result, it takes 10+10+1+11+11=43 seconds.
8. A double-ended queue supports operations like adding and removing items from both the sides of the queue. They support four operations like addFront(adding item to top of the queue), addRear(adding item to the bottom of the queue), removeFront(removing item from the top of the queue) and removeRear(removing item from the bottom of the queue). You are given only stacks to implement this data structure. You can implement only push and pop operations. What’s the time complexity of performing addFront and addRear? (Assume ‘m’ to be the size of the stack and ‘n’ to be the number of elements)
A) O(m) and O(n)
B) O(1) and O(n)
C) O(n) and O(1)
D) O(n) and O(m)
Explanation: addFront is nothing more than a standard push process. The operation of pushing is of O. (1). AddRear, on the other hand, is O(n) because it requires two push(pop()) operations on all stack elements.
9. Consider you have an array of some random size. You need to perform dequeue operation. You can perform it using stack operation (push and pop) or using queue operations itself (enQueue and Dequeue). The output is guaranteed to be same. Find some differences?
a) They will have different time complexities
b) The memory used will not be different
c) There are chances that output might be different
d) No differences
Explanation: To perform operations like Dequeue using stack operations, you must empty all of the elements from the current stack and transfer them into the next stack, resulting in an O(number of elements) complexity, while the time complexity of the dequeue operation is O(number of elements) (1). There is also a need for an additional stack. As a result, more memory is needed.
10. A Double-ended queue supports operations such as adding and removing items from both the sides of the queue. They support four operations like addFront(adding item to top of the queue), addRear(adding item to the bottom of the queue), removeFront(removing item from the top of the queue) and removeRear(removing item from the bottom of the queue). You are given only stacks to implement this data structure. You can implement only push and pop operations. What are the total number of stacks required for this operation?(you can reuse the stack)
Explanation: Push and pop (adding and removing elements from the top of the stack) are supported in the addFront and removeFront operations, but to perform addRear and removeRear, you must first pop each element from the current stack and push it into another stack, then push or pop the element as per the asked operation from this stack, and finally pop elements from this stack to the top of the stack.
The task is to implement a queue using instances of the stack data structure and operations on them, given a stack data structure with push and pop operations. Two stacks can be used to build a queue. Let’s name the queue to be implemented q, and the stacks that will be used to implement it stack1 and stack2. Stacks of them. Queues are inevitable. The LIFO principle governs stacks, which means that the element inserted last is the first to emerge from the list. Queues work on the first-in, first-out (FIFO) principle, which means that the element added first is the first to be removed from the queue.