Implement Queue Using Stacks — Problem Statement & Solution Guide
Problem Description
Implement a queue using two stacks. The queue should support the standard queue operations: enqueue and dequeue. The input will be a sequence of enqueue and dequeue operations.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Implement Queue Using Stacks"
WHY DOES IT MATTER?
The two‑stack pattern demonstrates how to transform a LIFO structure into a FIFO one while maintaining efficient operations, a concept that appears in many interview questions and real systems. It teaches amortized analysis and the power of auxiliary data structures.
OPTIMIZATION CHALLENGE
The key insight is that each element only needs to be moved once between the two stacks. By deferring the reversal until a dequeue is necessary, we avoid repeated O(n) operations and achieve constant amortized time.
REAL-WORLD CONNECTION
In distributed message queues like Kafka or RabbitMQ, messages are often buffered in stacks or buffers before being served to consumers. The two‑stack approach mirrors the idea of a write buffer and a read buffer, ensuring that consumers see messages in the order they were produced.
When explaining this in an interview, emphasize the amortized analysis and show a simple example with a few operations to illustrate how the cost is distributed.
COMPLEXITY AT A GLANCE
O(1) amortized per operationO(n)Core Theory — Why This Approach?
Implementing a queue with two stacks leverages the LIFO nature of stacks to achieve FIFO behavior. The key idea is to use one stack (inStack) for enqueue operations and another stack (outStack) for dequeue operations. When a dequeue is requested and outStack is empty, all elements from inStack are popped and pushed onto outStack, reversing their order so that the oldest element ends up on top of outStack. Each element is moved at most once between stacks, giving an amortized O(1) time per operation. Naive approaches, such as using a single stack or a linked list with head/tail pointers, either incur O(n) time for dequeue (when using a single stack) or require more complex pointer manipulation. The two‑stack paradigm is optimal because it balances simplicity with constant amortized performance, making it ideal for interview settings and real‑world systems where queues are a core primitive.
In large inputs, the naive stack‑only approach would repeatedly pop and push elements for each dequeue, leading to quadratic time complexity. By contrast, the two‑stack method ensures that each element is moved only once, regardless of how many operations follow, which is crucial for scalability. The algorithm also uses only O(n) additional space, where n is the number of elements in the queue, matching the space required by a conventional queue implementation.
The underlying theory is a classic example of the "amortized analysis" technique, where expensive operations are spread out over many cheap ones. This pattern is widely used in data structures like dynamic arrays, hash tables, and string builders, illustrating its importance beyond the specific problem of queue implementation.
Interview Questions on This Problem
Q1How would you implement a queue using two stacks in a language that only provides stack operations?
Use one stack for enqueues and another for dequeues. On enqueue, push onto inStack. On dequeue, if outStack is empty, pop all elements from inStack and push them onto outStack, then pop from outStack. This ensures FIFO order with amortized O(1) per operation.
Q2What is the time complexity of enqueue and dequeue operations in the two‑stack queue implementation?
Both enqueue and dequeue have O(1) amortized time. Dequeue may take O(n) in the worst case when outStack is empty, but each element is moved at most once, so the average cost per operation remains constant.
Q3Can you modify the two‑stack queue to support a peek operation efficiently?
Yes, after ensuring outStack is not empty (by moving elements if necessary), simply return the top of outStack without popping it. This gives O(1) amortized peek as well.
Examples
Input
["enqueue", 1], ["enqueue", 2], ["dequeue"]
Output
1
Explanation: Step-by-step: with input ["enqueue", 1], we add 1 to the queue. Then with ["enqueue", 2], we add 2 to the queue. Finally, with ["dequeue"], we remove the front element (1) from the queue, giving output 1.
Input
["enqueue", 3], ["enqueue", 4], ["dequeue"], ["dequeue"]
Output
3, then 4
Explanation: Step-by-step: with input ["enqueue", 3], we add 3 to the queue. Then with ["enqueue", 4], we add 4 to the queue. With the first ["dequeue"], we remove the front element (3) from the queue, giving output 3. With the second ["dequeue"], we remove the front element (4) from the queue, giving output 4.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
Optimal Approach & Strategy
Maintain two stacks: inStack for enqueues and outStack for dequeues. When outStack is empty, transfer all elements from inStack to outStack, then pop from outStack. Each element moves only once, giving amortized O(1).
Brute Force Approach
Use a single stack and, for each dequeue, pop all elements, store them temporarily, pop the last one, then push the others back. This is O(n) per dequeue.
Verified Code Solutions
function QueueUsingStacks() { let stackNewestOnTop = [], stackOldestOnTop = []; this.enqueue = function(value) { stackNewestOnTop.push(value); }; this.dequeue = function() { if (stackOldestOnTop.length === 0) { while (stackNewestOnTop.length > 0) { stackOldestOnTop.push(stackNewestOnTop.pop()); } } return stackOldestOnTop.pop(); }; }class QueueUsingStacks { private: std::stack<int> stackNewestOnTop; std::stack<int> stackOldestOnTop; public: void enqueue(int value) { stackNewestOnTop.push(value); } int dequeue() { if (stackOldestOnTop.empty()) { while (!stackNewestOnTop.empty()) { stackOldestOnTop.push(stackNewestOnTop.top()); stackNewestOnTop.pop(); } } int value = stackOldestOnTop.top(); stackOldestOnTop.pop(); return value; } }import java.util.Stack; class QueueUsingStacks { private Stack<Integer> stackNewestOnTop; private Stack<Integer> stackOldestOnTop; public QueueUsingStacks() { stackNewestOnTop = new Stack<>(); stackOldestOnTop = new Stack<>(); } public void enqueue(int value) { stackNewestOnTop.push(value); } public int dequeue() { if (stackOldestOnTop.isEmpty()) { while (!stackNewestOnTop.isEmpty()) { stackOldestOnTop.push(stackNewestOnTop.pop()); } } return stackOldestOnTop.pop(); } }class QueueUsingStacks: def __init__(self): self.stack_newest_on_top = []; self.stack_oldest_on_top = []; def enqueue(self, value): self.stack_newest_on_top.append(value); def dequeue(self): if not self.stack_oldest_on_top: while self.stack_newest_on_top: self.stack_oldest_on_top.append(self.stack_newest_on_top.pop()); return self.stack_oldest_on_top.pop() if self.stack_oldest_on_top else Nonefunction QueueUsingStacks() { let stackNewestOnTop = [], stackOldestOnTop = []; this.enqueue = function(value) { stackNewestOnTop.push(value); }; this.dequeue = function() { if (stackOldestOnTop.length === 0) { while (stackNewestOnTop.length > 0) { stackOldestOnTop.push(stackNewestOnTop.pop()); } } return stackOldestOnTop.pop(); }; }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.