Author at SyntaxFlow
If you are diving into the world of Data Structures and Algorithms (DSA), you have likely encountered two of the most fundamental data structures: Stacks and Queues.
To put it simply, a Queue is a linear data structure that models a real-world line of people waiting for a service. It follows the FIFO (First In, First Out) principle. The first person to join the line is the first person to be served and leave.
Conversely, a Stack follows the LIFO (Last In, First Out) principle. Think of it like a stack of plates in a cafeteria; the last plate you put on top is the first one you pick up.
Why is implementing one using the other a popular interview question? Because it forces you to think outside the box. Interviewers at top tech companies love this question because it tests your fundamental understanding of how data flows. You cannot rely on built-in queue libraries; you have to engineer a FIFO behavior using LIFO tools. It also opens the door to a deeper discussion about time complexity and amortized analysis—a favorite topic in system design and optimization.
The problem is straightforward: You need to design a custom Queue data structure using only two standard Stacks.
Your custom queue must support the following standard queue operations:
push(x): Pushes element x to the back of the queue.pop(): Removes the element from the front of the queue and returns it.peek(): Returns the element at the front of the queue without removing it.empty(): Returns true if the queue is empty, false otherwise.Note: You are only allowed to use standard stack operations. This means you can only usepush to top,peek/pop from top,size, andis empty.
When tackling an interview problem, it is perfectly fine (and often encouraged) to state the brute force solution first. It shows you can solve the problem before optimizing it.
A stack natively gives us the newest element when we pop. But a queue requires the oldest element. If we want to get to the oldest element (which is trapped at the very bottom of the stack), we have to move all the elements sitting on top of it out of the way.
Whenever a pop or peek is needed, we can transfer all elements from our main stack to a second temporary stack. This essentially reverses their order, bringing the oldest element to the top! Once we retrieve or remove that oldest element, we must transfer all the remaining elements back to the main stack so that the original order is restored for future push operations.
Let's call our stacks mainStack and tempStack.
mainStack.mainStack to tempStack one by one.tempStack is now our front queue element. Save this value.tempStack to mainStack.mainStack to tempStack.tempStack (this removes the oldest element). Save this value.tempStack to mainStack.mainStack is empty.Let's execute the following operations: push(1), push(2), push(3), peek(), pop(), push(4), pop()
1. push(1)
mainStack: [1]tempStack: (empty)2. push(2)
mainStack: [1, 2] (top is 2)tempStack: (empty)3. push(3)
mainStack: [1, 2, 3] (top is 3)tempStack: (empty)4. peek()
mainStack becomes (empty), tempStack becomes [3, 2, 1] (top is 1).mainStack becomes [1, 2, 3], tempStack becomes (empty).5. pop()
mainStack becomes (empty), tempStack becomes [3, 2, 1].mainStack becomes [2, 3], tempStack becomes (empty).6. push(4)
mainStack: [2, 3, 4] (top is 4)tempStack: (empty)7. pop()
mainStack becomes (empty), tempStack becomes [4, 3, 2].mainStack becomes [3, 4], tempStack becomes (empty).#include <stack>
class MyQueueBruteForce {
private:
std::stack<int> mainStack;
std::stack<int> tempStack;
public:
MyQueueBruteForce() {}
void push(int x) {
mainStack.push(x);
}
int pop() {
// Transfer all to tempStack
while (!mainStack.empty()) {
tempStack.push(mainStack.top());
mainStack.pop();
}
// The oldest element is now at the top
int frontElement = tempStack.top();
tempStack.pop();
// Transfer everything back to mainStack
while (!tempStack.empty()) {
mainStack.push(tempStack.top());
tempStack.pop();
}
return frontElement;
}
int peek() {
// Transfer all to tempStack
while (!mainStack.empty()) {
tempStack.push(mainStack.top());
mainStack.pop();
}
// The oldest element is now at the top
int frontElement = tempStack.top();
// Transfer everything back to mainStack
while (!tempStack.empty()) {
mainStack.push(tempStack.top());
tempStack.pop();
}
return frontElement;
}
bool empty() {
return mainStack.empty();
}
};The brute force approach does a lot of redundant work. Why are we moving elements back to the main stack immediately?
Let's rethink our strategy:
inputStack) will solely be responsible for taking in newly inserted elements.outputStack) will be used solely for pop and peek operations.inputStack to outputStack when outputStack is completely empty.When we pour elements from inputStack into outputStack, they are reversed. The oldest element is now perfectly sitting at the top of outputStack, ready to be popped. But here is the magic: the second oldest element is right beneath it!
We do not need to transfer the elements back. We can just leave them in outputStack. Future pop and peek operations can just read directly from outputStack in O(1) time. We only need to do another bulk transfer when outputStack eventually runs empty. Every element moves between stacks exactly once in its lifetime.
inputStack.outputStack is empty, move all elements one-by-one from inputStack to outputStack.outputStack.peek() to ensure outputStack has elements (this handles the transfer if needed).outputStack and return it.inputStack and outputStack are empty.Let's trace a few operations to see the lazy transfer in action.
Let's execute: push(1), push(2), push(3), peek(), pop(), push(4), peek(), pop(), pop()
inputStack = [1], outputStack = []inputStack = [1, 2], outputStack = []inputStack = [1, 2, 3], outputStack = []outputStack is empty. Transfer inputStack to outputStack.inputStack = []outputStack = [3, 2, 1] (top is 1). Returns 1.outputStack is NOT empty. Just pop from it!outputStack = [3, 2] (top is 2). Returns 1.inputStack.inputStack = [4], outputStack = [3, 2].outputStack is NOT empty. Just read top.outputStack is NOT empty. Just pop from it!outputStack = [3]. Returns 2.outputStack is NOT empty. Just pop from it!outputStack = []. inputStack = [4]. Returns 3. (Next time we pop, 4 will transfer over).Notice how much faster this is? We only did one transfer step the entire time!
#include <stack>
using namespace std;
class MyQueue {
private:
stack<int> inputStack; // Stack used for enqueue (push) operations
stack<int> outputStack; // Stack used for dequeue (pop/peek) operations
public:
MyQueue() {} // Constructor initializes empty stacks
// Push element x to the back of the queue
void push(int x) {
inputStack.push(x); // Always push new elements onto inputStack
}
// Removes the element from the front of the queue and returns it
int pop() {
// Ensure outputStack has the current front element
peek();
int frontElement = outputStack.top(); // Get the front element
outputStack.pop(); // Remove it from outputStack
return frontElement; // Return the removed element
}
// Get the front element without removing it
int peek() {
// If outputStack is empty, transfer all elements from inputStack
// This reverses the order so the oldest element ends up on top
if (outputStack.empty()) {
while (!inputStack.empty()) {
outputStack.push(inputStack.top());
inputStack.pop();
}
}
return outputStack.top(); // The front of the queue
}
// Returns true if the queue is empty
bool empty() {
// Queue is empty only if BOTH stacks are empty
return inputStack.empty() && outputStack.empty();
}
};
outputStack is empty, pop or peek takes O(N) time because it has to move N elements from inputStack.inputStack once, moved to outputStack once, and popped once, the total time across a series of operations is proportional to the number of operations. Therefore, the average time per operation is O(1).Let's intuitively break down why this is so much better than brute force.
Imagine you have a stack of blocks. You want the bottom block.
Input Stack
Top
3
2
1
BottomIf you move them to another pile (the Output Stack), they reverse order:
Output Stack
Top
1
2
3
BottomNow block 1 is on top. You take it. What is beneath it? Block 2. That is the exact next block you will need! Because the Output Stack holds the remaining elements in the perfect FIFO order, you don't need to move them back. You can just leave them there.
Any new elements arriving (like block 4 or 5) just wait patiently in the Input Stack. They don't need to be touched until the Output Stack is completely empty. This proves that every element is moved exactly once from input to output, making the heavy-lifting sparse and the overall algorithm incredibly efficient.
To make the differences crystal clear for an interview, here is a direct comparison:
Why is the Optimal approach preferred? In software engineering, we care about the overall performance of a system over time. The brute force method causes severe lag every single time a user tries to retrieve data. The lazy transfer method guarantees that retrieval is blazing fast almost every time, with only occasional, predictable cleanup work.
A flawless interview response always accounts for edge cases:
pop() or peek() on an empty queue. (In LeetCode, it is guaranteed that all calls to pop and peek are valid, but in a real-world scenario, you should throw an exception).peek() ten times in a row. The brute force would do O(N) work ten times. The optimal approach does O(N) work once, and O(1) work nine times.push, pop, push, pop. In this specific scenario, the optimal approach still takes O(1) time for each operation because the outputStack empties immediately, meaning only one element transfers at a time.Watch out for these frequent pitfalls when writing this code:
inputStack directly without moving things to outputStack will result in LIFO behavior, failing the problem.if (outputStack.empty()) before transferring.outputStack.top(), never inputStack.top().empty() function must check if both stacks are empty, not just one. return inputStack.empty() && outputStack.empty();push, pop, top).Why do interviewers ask this problem? It checks if you understand the conceptual difference between LIFO and FIFO. It also acts as a gateway to test your knowledge of Amortized Analysis.
1. Can a queue be implemented using one stack? Technically yes, if you use the implicit call stack via recursion. But it still requires O(N) extra space and is essentially using "two stacks" under the hood. Standard iterative implementations require two stacks.
2. Why are two stacks needed? A single stack enforces LIFO. To get FIFO, the data order must be completely reversed. You need a second stack to hold the reversed data.
3. Why is pop() O(1) amortized? Because the costly O(N) transfer only happens when the outputStack is empty. The cost of that transfer is "paid for" by the O(1) pops that follow. Over a long sequence of operations, the average cost per operation averages out to O(1).
4. What is amortized analysis? It is a method of analyzing algorithms where the cost of an occasional expensive operation is distributed over multiple cheap operations, giving a true picture of the algorithm's average performance over time.
5. Why isn't every pop O(N)? Because we use Lazy Transfer. We leave the elements in the outputStack after the first transfer, so subsequent pops just read directly from the top in O(1) time.
6. What happens if both stacks are empty? The empty() method will return true. If you try to pop or peek, standard stack implementations will throw a runtime error (Segmentation fault in C++).
7. Is this problem actually asked in interviews? Yes, frequently. It is highly popular in screening rounds for Amazon, Microsoft, and Bloomberg.
8. Can a deque replace stacks here? A deque (Double Ended Queue) can behave like a stack, but using a deque to solve this problem defeats the purpose, as a deque is a queue. The restriction is to strictly use stack mechanics.
9. Which approach is preferred by interviewers? Approach 2 (Lazy Transfer) is the expected, optimal solution.
10. What are similar interview questions? "Implement Stack using Queues" (LeetCode 225) is the sister problem to this one. Other similar logic puzzles include the "Min Stack" problem.
pop or peek, leading to O(N) time complexity for those operations.empty() function checks the status of both stacks.video reference:
code link:
https://leetcode.com/problems/implement-queue-using-stacks/description/