9.
MathWorks technical mcq question, verified with a worked answer. Free to practise - no sign-up.
(Prog. Concept Question) Queue Data Structure**
What is the time complexity to dequeue and enqueue an element from a queue which is implemented using minimum number of stack(s). n is the number of elements already in queue.
Pick ONE option
Show answer & explanation
A queue implemented using the minimum number of stacks (one stack) requires O(n) time for dequeue operations because all elements must be popped and transferred to extract the front element, then transferred back. Enqueue is O(1) since you simply push onto the stack. With two stacks, dequeue becomes amortized O(1), but the question specifies the minimum number of stacks.
Step-by-step Derivation:
Queue (FIFO) vs Stack (LIFO) behavior:
Minimum Stack Implementation (1 stack):
- Enqueue: Push onto stack → O(1)
- Dequeue: Pop all n elements, extract the bottom one, push n-1 back → O(n)
Why O(n) for dequeue with 1 stack:
Since a stack is LIFO and queue is FIFO, to get the first-in element (front of queue), you must pop all n elements. This requires n pop operations = O(n).
Verification with 2-stack approach (not minimum):
With 2 stacks, dequeue becomes amortized O(1), but the question asks for minimum stacks.
Therefore: Dequeue = O(n), Enqueue = O(1) → Answer is B.