Stack Using Two Queues Java
Fast recall
Quick revision
Core answer
q2, then move everything from `q1` into `q2`, and swap names - so the newest element is always at the front. push is O(n), pop/top are O(1). (You could instead make pop costly and push O(1).)Whether you can simulate LIFO using FIFO structures and analyze the cost shift
Not committing to which operation is O(n), or losing element order during the transfer
State the tradeoff: make push O(n) for O(1) pop, or the reverse, and that a single queue can also work
Interview-ready guide
Interview answer
The challenge here is that a queue is first-in first-out, but a stack is last-in first-out, so I have to arrange for the most recently pushed element to be the first one out.
The clean approach uses two queues, and I'll make push the expensive operation so that pop and top are constant time. I keep a main queue, q1, and a helper, q2. When I push a new element, I first enqueue it into the empty helper queue q2.
Then I move every element from q1 over to q2, one by one, so they line up behind the new element. Now q2 has the newest element at its front, followed by all the older ones in the right order.
Finally I swap the references so q1 becomes the queue with the newest element at the front. Because of that arrangement, popping or peeking is just taking from the front of q1, which is O of one. The whole cost lives in push, which is O of n because I move every existing element each time.
I'd explicitly state that this is a tradeoff: I chose to make push O of n and pop O of one, but you can flip it and make push O of one and pop O of n by doing the transfer at pop time instead.
The detail that's easy to get wrong is the ordering during the transfer, I have to enqueue the new element first and then move the old queue behind it, and I must remember to swap the two queue references at the end. I'd also mention you can actually do this with a single queue by rotating it after each push.
For example, after push(1), the main queue is [1]. For push(2), put 2 in the helper, move 1 behind it, and swap: the main queue is [2, 1], so pop() correctly returns 2.
Stack Using Two Queues Java
Direct Answer
Implement a stack (LIFO) using two queues (FIFO). The clean push-costly approach: on push, enqueue the new element into the empty q2, then move everything from q1 into q2, and swap names - so the newest element is always at the front. push is O(n), pop/top are O(1). (You could instead make pop costly and push O(1).)
Deep Dive & Architecture
A queue exposes its oldest element, while a stack must expose its newest. Two queues can reverse which item reaches the front by moving existing elements around a newly pushed value.
Push-costly worked example
After push(1), the main queue is [1]. To push(2), add 2 to the empty helper queue, move 1 behind it, then swap the queue references. The main queue becomes [2, 1]. Repeating this for 3 produces [3, 2, 1], so pop() removes 3 immediately.
This version makes push O(n), while pop and top are O(1). A second valid design leaves pushes as normal O(1) queue additions and, during pop, moves all but the last element into the helper. That makes pop O(n). State which operation is costly; mixing the two designs is a common source of errors.
At all times, only one queue should hold the complete stack order after an operation. Empty checks must happen before pop or top, according to the chosen API contract.
The structure stores n items across the queues, so it uses O(n) space. The exercise demonstrates adapting one access rule to another; in real Java code, ArrayDeque is the direct stack implementation.
Code Example
class MyStack {
Queue<Integer> q1 = new ArrayDeque<>(), q2 = new ArrayDeque<>();
void push(int x) {
q2.offer(x); // new element first
while (!q1.isEmpty()) q2.offer(q1.poll()); // move the rest behind it
Queue<Integer> t = q1; q1 = q2; q2 = t; // swap
}
int pop() { return q1.poll(); } // O(1)
int top() { return q1.peek(); } // O(1)
boolean empty() { return q1.isEmpty(); }
}
// push1 -> q1:[1]; push2 -> q2:[2], move 1 -> [2,1], swap -> q1:[2,1]
// pop -> 2 (newest, LIFO correct)
Common Mistakes & Pitfalls
- Undecided cost: pick a design - push-costly (O(n) push, O(1) pop) or pop-costly.
- Order lost in transfer: enqueue the new element first, then move the old queue behind it.
- Forgetting the swap: without swapping,
q1/q2roles drift and ordering breaks. - Using legacy classes: use
ArrayDequeas the underlying queue.
Check your understanding
Answer these without looking back at the article.
- What is a stack and what are its core operations?
- What is a queue and how does it differ from a stack?
- How do you check for balanced parentheses using a stack?
Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.