Code Logo

Implement Stack Using Queues

Published at23 Jul 2026
Created by
Easy 2 views
Like0

Implement a stack using only two queues. You may only use standard queue operations: enqueue (push to back), dequeue (pop from front), peek (front), and empty check. The stack must support push(x), pop(), top(), and empty(). The key insight: a stack is LIFO while a queue is FIFO. By using an auxiliary queue and moving elements around, the newest element can be kept at the front of the main queue. This teaches how data structures can implement each other and reveals the fundamental relationship between LIFO and FIFO.

The key insight is that a stack reverses order (LIFO) while a queue preserves order (FIFO). To make a queue behave like a stack, you need to reverse the order of elements each time a new element is pushed. This can be done by pushing the new element into an empty auxiliary queue, then moving all elements from the main queue to the auxiliary queue, and finally swapping the two queues. This puts the newest element at the front of the main queue, ready to be popped first.

An alternative approach is to make the push operation O(1) and the pop operation O(n), by pushing directly and rotating elements when popping. Both are valid.

Example Input & Output

Example 1
Input
"push(1), push(2), top(), pop(), empty()"
Output
"2, 2, false"
Explanation

Push 1,2. Top is 2. Pop 2. Not empty.

Example 2
Input
"push(1), pop(), empty()"
Output
"1, true"
Explanation

Push 1, pop 1. Empty.

Algorithm Flow

Recommendation Algorithm Flow for Implement Stack Using Queues

Solution Approach

Implement a stack using two queues. The stack must support push, pop, top, and empty operations. Use one queue as the primary storage and the other as temporary space. On push, add the element to the back of the primary queue. On pop/top, rotate all elements except the last from the primary queue to the temporary queue, then process the last element and swap the queue roles.

function MyStack() {
  this.q1 = []; this.q2 = [];
}
MyStack.prototype.push = function(x) { this.q1.push(x); };
MyStack.prototype.pop = function() {
  while (this.q1.length > 1) this.q2.push(this.q1.shift());
  var val = this.q1.shift();
  var t = this.q1; this.q1 = this.q2; this.q2 = t;
  return val;
};
MyStack.prototype.top = function() {
  while (this.q1.length > 1) this.q2.push(this.q1.shift());
  var val = this.q1[0];
  this.q2.push(this.q1.shift());
  var t = this.q1; this.q1 = this.q2; this.q2 = t;
  return val;
};
MyStack.prototype.empty = function() { return this.q1.length === 0; };

Transferring n-1 elements to the other queue leaves the last element at the front for O(n) pop/top. The queue that holds the actual elements alternates between q1 and q2 after each operation.

Time complexity is O(1) for push, O(n) for pop/top, space is O(n).

Best Answers

java
import java.util.*;
class MyStack {
    Queue<Integer> q1 = new LinkedList<>();
    Queue<Integer> q2 = new LinkedList<>();
    public void push(int x) {
        q2.add(x);
        while (!q1.isEmpty()) q2.add(q1.poll());
        Queue<Integer> t = q1; q1 = q2; q2 = t;
    }
    public int pop() { return q1.poll(); }
    public int top() { return q1.peek(); }
    public boolean empty() { return q1.isEmpty(); }
}