225. Implement Stack using Queues Solution

Q: Is Implement Stack using Queues easy or hard?

LeetCode classifies this problem as Easy because it mainly tests understanding of stack and queue behavior rather than complex algorithms. The key idea is reversing element order using queue operations to maintain LIFO semantics.

Q: Implement Stack using Queues Python/Java solution

In Python or Java, the queue can be implemented using collections like deque in Python or LinkedList/ArrayDeque in Java. After each push, rotate the queue elements so the most recently added value moves to the front, allowing pop and top to run in constant time.

Q: How to solve Implement Stack using Queues in O(n)?

Insert the new element into a queue and then rotate the queue so that the newly added element moves to the front. This requires moving the previous elements to the back one by one. After rotation, the queue front always represents the stack top, enabling constant-time pop operations.

Q: What is the best approach for Implement Stack using Queues?

The single queue rotation approach is generally considered the best solution. After pushing an element into the queue, rotate the queue by moving the previous elements behind it so the newest element becomes the front. This keeps pop() and top() operations O(1) while push() takes O(n).

Q: Is Implement Stack using Queues asked at Google/Amazon/Meta?

Stack and queue design problems frequently appear in interviews at companies like Amazon, Google, and Meta. This specific question tests understanding of data structure behavior and the ability to simulate one structure using another with constrained operations.

Q: What data structure is used in Implement Stack using Queues?

The implementation uses one or two queues to simulate stack behavior. Queue operations such as enqueue, dequeue, and front access are used to reorder elements so the newest element behaves like the top of a stack.

Q: What is the time complexity of Implement Stack using Queues?

Most implementations achieve push in O(n) time and pop in O(1) time. The push operation requires rearranging or rotating elements to maintain stack order. Space complexity is O(n) because all elements are stored inside one or two queues.

The problem

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

void push(int x) Pushes element x to the top of the stack.
int pop() Removes the element on the top of the stack and returns it.
int top() Returns the element on the top of the stack.
boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations.

Example 1:

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

Constraints:

1 <= x <= 9
At most 100 calls will be made to push, pop, top, and empty.
All the calls to pop and top are valid.

Follow-up: Can you implement the stack using only one queue?

Approach overview

Problem Overview: Design a stack using standard queue operations only. The stack must support push, pop, top, and empty while maintaining LIFO behavior even though queues naturally operate in FIFO order.

The challenge is reversing the order of elements so the most recently pushed item always appears at the front when removing or peeking. Since queues only allow insertion at the back and removal from the front, the solution relies on rearranging elements during push or pop operations. Understanding the behavior of both stack and queue data structures is key.

Approach 1: Double Queue with Rearranging Elements (Push: O(n), Pop: O(1), Space: O(n))

This approach maintains two queues. When you perform push(x), insert the element into the second queue and then move every element from the first queue into it. This reorders the queue so the newest element always ends up at the front. After rearranging, swap the two queues so the main queue always stores elements in stack order.

Because the newest element stays at the front, both pop() and top() become simple queue front operations with constant time complexity. The tradeoff is that every push operation must iterate through all existing elements to maintain order. This design clearly demonstrates how queue operations can simulate stack behavior and is often the first approach candidates think of during interviews.

Approach 2: Single Queue with Rotation (Push: O(n), Pop: O(1), Space: O(n))

This optimized design uses only one queue. After inserting the new element at the back of the queue, rotate the queue so that the newly added element moves to the front. The rotation is done by repeatedly removing the front element and pushing it to the back for size - 1 iterations.

For example, after pushing a new element, cycle the previous elements behind it. This effectively reverses the queue order relative to insertion time, making the front of the queue behave like the top of a stack. As a result, pop() and top() simply read from the queue front in constant time.

This approach is cleaner because it eliminates the second queue while keeping the same complexity characteristics. It is commonly considered the optimal implementation for this problem and demonstrates strong understanding of queue manipulation and data structure design.

Recommended for interviews: The single queue rotation approach is usually preferred because it minimizes auxiliary data structures while preserving clear logic. Explaining the two-queue method first shows you understand the stack ordering problem, but implementing the single-queue rotation demonstrates stronger design skills and deeper mastery of queue operations.

Approach 1: Double Queue with Rearranging Elements

This approach involves using two queues to simulate the operations of a stack. Whenever we push an element onto the stack, we move all elements from the first queue to the second queue, enqueue the new element into the first queue, and then move all elements back from the second queue to the first one. This ensures that the newest element is always at the front of the queue, allowing us to use single dequeue operations for pop() and top(), thus mimicking a stack's LIFO behavior.

Python

from collections import deque

class MyStack:
    def __init__(self):
        self.q1 = deque()
        self.q2 = deque()

    def push(self, x: int) -> None:
        self.q2.append(x)
        while self.q1:
            self.q2.append(self.q1.popleft())
        self.q1, self.q2 = self.q2, self.q1

    def pop(self) -> int:
        return self.q1.popleft()

    def top(self) -> int:
        return self.q1[0]

    def empty(self) -> bool:
        return not self.q1

Java

import java.util.LinkedList;
import java.util.Queue;

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.remove());
        }
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
    }

    public int pop() {
        return q1.remove();
    }

    public int top() {
        return q1.peek();
    }

    public boolean empty() {
        return q1.isEmpty();
    }
}

C++

#include <queue>

class MyStack {
    std::queue<int> q1, q2;
public:
    MyStack() {}

    void push(int x) {
        q2.push(x);
        while (!q1.empty()) {
            q2.push(q1.front());
            q1.pop();
        }
        std::swap(q1, q2);
    }

    int pop() {
        int top = q1.front();
        q1.pop();
        return top;
    }

    int top() {
        return q1.front();
    }

    bool empty() {
        return q1.empty();
    }
};

JavaScript

class MyStack {
    constructor() {
        this.q1 = [];
        this.q2 = [];
    }

    push(x) {
        this.q2.push(x);
        while (this.q1.length) {
            this.q2.push(this.q1.shift());
        }
        [this.q1, this.q2] = [this.q2, this.q1];
    }

    pop() {
        return this.q1.shift();
    }

    top() {
        return this.q1[0];
    }

    empty() {
        return this.q1.length === 0;
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
    int size;
} Queue;

Queue* createQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = 0;
    q->rear = -1;
    q->size = 0;
    return q;
}

bool isEmpty(Queue* q) {
    return q->size == 0;
}

void enqueue(Queue* q, int x) {
    if (q->size < MAX_SIZE) {
        q->rear = (q->rear + 1) % MAX_SIZE;
        q->data[q->rear] = x;
        q->size++;
    }
}

int dequeue(Queue* q) {
    int item = -1;
    if (!isEmpty(q)) {
        item = q->data[q->front];
        q->front = (q->front + 1) % MAX_SIZE;
        q->size--;
    }
    return item;
}

int front(Queue* q) {
    return q->data[q->front];
}

typedef struct {
    Queue* q1;
    Queue* q2;
} MyStack;

MyStack* myStackCreate() {
    MyStack* stack = (MyStack*)malloc(sizeof(MyStack));
    stack->q1 = createQueue();
    stack->q2 = createQueue();
    return stack;
}

void myStackPush(MyStack* obj, int x) {
    enqueue(obj->q2, x);
    while (!isEmpty(obj->q1)) {
        enqueue(obj->q2, dequeue(obj->q1));
    }
    Queue* temp = obj->q1;
    obj->q1 = obj->q2;
    obj->q2 = temp;
}

int myStackPop(MyStack* obj) {
    return dequeue(obj->q1);
}

int myStackTop(MyStack* obj) {
    return front(obj->q1);
}

bool myStackEmpty(MyStack* obj) {
    return isEmpty(obj->q1);
}

void myStackFree(MyStack* obj) {
    free(obj->q1);
    free(obj->q2);
    free(obj);
}

using System.Collections.Generic;

public class MyStack {
    private Queue<int> q1 = new Queue<int>();
    private Queue<int> q2 = new Queue<int>();

    public void Push(int x) {
        q2.Enqueue(x);
        while (q1.Count > 0) {
            q2.Enqueue(q1.Dequeue());
        }
        var temp = q1;
        q1 = q2;
        q2 = temp;
    }

    public int Pop() {
        return q1.Dequeue();
    }

    public int Top() {
        return q1.Peek();
    }

    public bool Empty() {
        return q1.Count == 0;
    }
}

This Python implementation uses deque for efficient queue operations. push operations transfer elements between two deques, utilizing the front element of a deque as the stack's top.

Complexity

Time Complexity: push - O(n), pop, top, and empty - O(1).
Space Complexity: O(n) utilizing two deques.

Try this approach in the editor

Approach 2: Single Queue with Rotation

This approach only uses one queue to implement the stack. When pushing an element, we enqueue the element and then rotate the queue such that the newly added element reaches the front. The queue thus behaves like a stack with respect to push, pop, top

Python

from collections import deque

class MyStack:
    def __init__(self):
        self.q1 = deque()

    def push(self, x: int) -> None:
        self.q1.append(x)
        for _ in range(len(self.q1) - 1):
            self.q1.append(self.q1.popleft())

    def pop(self) -> int:
        return self.q1.popleft()

    def top(self) -> int:
        return self.q1[0]

    def empty(self) -> bool:
        return not self.q1

Java

import java.util.LinkedList;
import java.util.Queue;

class MyStack {
    Queue<Integer> q1;

    public MyStack() {
        q1 = new LinkedList<>();
    }

    public void push(int x) {
        q1.add(x);
        int size = q1.size();
        while (size > 1) {
            q1.add(q1.remove());
            size--;
        }
    }

    public int pop() {
        return q1.remove();
    }

    public int top() {
        return q1.peek();
    }

    public boolean empty() {
        return q1.isEmpty();
    }
}

C++

#include <queue>

class MyStack {
    std::queue<int> q1;
public:
    MyStack() {}

    void push(int x) {
        q1.push(x);
        int size = q1.size();
        while (size > 1) {
            q1.push(q1.front());
            q1.pop();
            size--;
        }
    }

    int pop() {
        int top = q1.front();
        q1.pop();
        return top;
    }

    int top() {
        return q1.front();
    }

    bool empty() {
        return q1.empty();
    }
};

JavaScript

class MyStack {
    constructor() {
        this.q1 = [];
    }

    push(x) {
        this.q1.push(x);
        let size = this.q1.length;
        while (size > 1) {
            this.q1.push(this.q1.shift());
            size--;
        }
    }

    pop() {
        return this.q1.shift();
    }

    top() {
        return this.q1[0];
    }

    empty() {
        return this.q1.length === 0;
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_SIZE 101

typedef struct {
    int data[MAX_SIZE];
    int front;
    int size;
} Queue;

Queue* createQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = 0;
    q->size = 0;
    return q;
}

bool isEmpty(Queue* q) {
    return q->size == 0;
}

void enqueue(Queue* q, int x) {
    int index = (q->front + q->size) % MAX_SIZE;
    q->data[index] = x;
    q->size++;
}

int dequeue(Queue* q) {
    int item = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    q->size--;
    return item;
}

int front(Queue* q) {
    return q->data[q->front];
}

typedef struct {
    Queue* q1;
} MyStack;

MyStack* myStackCreate() {
    MyStack* stack = (MyStack*)malloc(sizeof(MyStack));
    stack->q1 = createQueue();
    return stack;
}

void myStackPush(MyStack* obj, int x) {
    enqueue(obj->q1, x);
    int count = obj->q1->size;
    while (count > 1) {
        enqueue(obj->q1, dequeue(obj->q1));
        count--;
    }
}

int myStackPop(MyStack* obj) {
    return dequeue(obj->q1);
}

int myStackTop(MyStack* obj) {
    return front(obj->q1);
}

bool myStackEmpty(MyStack* obj) {
    return isEmpty(obj->q1);
}

void myStackFree(MyStack* obj) {
    free(obj->q1);
    free(obj);
}

using System.Collections.Generic;

public class MyStack {
    private Queue<int> q1;

    public MyStack() {
        q1 = new Queue<int>();
    }

    public void Push(int x) {
        q1.Enqueue(x);
        int count = q1.Count;
        while (count > 1) {
            q1.Enqueue(q1.Dequeue());
            count--;
        }
    }

    public int Pop() {
        return q1.Dequeue();
    }

    public int Top() {
        return q1.Peek();
    }

    public bool Empty() {
        return q1.Count == 0;
    }
}

In Python, a single deque is manipulated to current element to the front within the push operation. Other operations remain direct, simulating stack functions through queue operations.

Complexity

Time Complexity: push - O(n), pop, top, and empty - O(1).
Space Complexity: O(n) without extra queues due to focus on a lone deque.

Try this approach in the editor

Approach 3: Two Queues

We use two queues q_1 and q_2, where q_1 is used to store the elements in the stack, and q_2 is used to assist in implementing the stack operations.

push operation: Push the element into q_2, then pop the elements in q_1 one by one and push them into q_2, finally swap the references of q_1 and q_2. The time complexity is O(n).
pop operation: Directly pop the front element of q_1. The time complexity is O(1).
top operation: Directly return the front element of q_1. The time complexity is O(1).
empty operation: Check whether q_1 is empty. The time complexity is O(1).

The space complexity is O(n), where n is the number of elements in the stack.

TypeScript

class MyStack {
    q1: number[] = [];
    q2: number[] = [];

    constructor() {}

    push(x: number): void {
        this.q2.push(x);
        while (this.q1.length) {
            this.q2.push(this.q1.shift()!);
        }
        [this.q1, this.q2] = [this.q2, this.q1];
    }

    pop(): number {
        return this.q1.shift()!;
    }

    top(): number {
        return this.q1[0];
    }

    empty(): boolean {
        return this.q1.length === 0;
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * var obj = new MyStack()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.empty()
 */

type MyStack struct {
	q1 []int
	q2 []int
}

func Constructor() MyStack {
	return MyStack{}
}

func (this *MyStack) Push(x int) {
	this.q2 = append(this.q2, x)
	for len(this.q1) > 0 {
		this.q2 = append(this.q2, this.q1[0])
		this.q1 = this.q1[1:]
	}
	this.q1, this.q2 = this.q2, this.q1
}

func (this *MyStack) Pop() int {
	x := this.q1[0]
	this.q1 = this.q1[1:]
	return x
}

func (this *MyStack) Top() int {
	return this.q1[0]
}

func (this *MyStack) Empty() bool {
	return len(this.q1) == 0
}

/**
 * Your MyStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * param_2 := obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.Empty();
 */

Rust

use std::collections::VecDeque;

struct MyStack {
    /// There could only be two status at all time
    /// 1. One contains N elements, the other is empty
    /// 2. One contains N - 1 elements, the other contains exactly 1 element
    q_1: VecDeque<i32>,
    q_2: VecDeque<i32>,
    // Either 1 or 2, originally begins from 1
    index: i32,
}

impl MyStack {
    fn new() -> Self {
        Self {
            q_1: VecDeque::new(),
            q_2: VecDeque::new(),
            index: 1,
        }
    }

    fn move_data(&mut self) {
        // Always move from q1 to q2
        assert!(self.q_2.len() == 1);
        while !self.q_1.is_empty() {
            self.q_2.push_back(self.q_1.pop_front().unwrap());
        }
        let tmp = self.q_1.clone();
        self.q_1 = self.q_2.clone();
        self.q_2 = tmp;
    }

    fn push(&mut self, x: i32) {
        self.q_2.push_back(x);
        self.move_data();
    }

    fn pop(&mut self) -> i32 {
        self.q_1.pop_front().unwrap()
    }

    fn top(&mut self) -> i32 {
        *self.q_1.front().unwrap()
    }

    fn empty(&self) -> bool {
        self.q_1.is_empty()
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Double Queue with Rearranging Elements	Time Complexity: `push` - O(n), `pop`, `top`, and `empty` - O(1). Space Complexity: O(n) utilizing two deques.
Single Queue with Rotation	Time Complexity: `push` - O(n), `pop`, `top`, and `empty` - O(1). Space Complexity: O(n) without extra queues due to focus on a lone `deque`.
Two Queues	–

Complexity analysis

Approach	Time	Space	When to Use
Double Queue with Rearranging Elements	Push: O(n), Pop: O(1)	O(n)	When clarity matters and you want a straightforward simulation using two queues
Single Queue with Rotation	Push: O(n), Pop: O(1)	O(n)	Preferred interview solution with minimal data structures

Frequently asked questions

Is Implement Stack using Queues easy or hard?

LeetCode classifies this problem as Easy because it mainly tests understanding of stack and queue behavior rather than complex algorithms. The key idea is reversing element order using queue operations to maintain LIFO semantics.

Implement Stack using Queues Python/Java solution

In Python or Java, the queue can be implemented using collections like deque in Python or LinkedList/ArrayDeque in Java. After each push, rotate the queue elements so the most recently added value moves to the front, allowing pop and top to run in constant time.

How to solve Implement Stack using Queues in O(n)?

Insert the new element into a queue and then rotate the queue so that the newly added element moves to the front. This requires moving the previous elements to the back one by one. After rotation, the queue front always represents the stack top, enabling constant-time pop operations.

What is the best approach for Implement Stack using Queues?

The single queue rotation approach is generally considered the best solution. After pushing an element into the queue, rotate the queue by moving the previous elements behind it so the newest element becomes the front. This keeps pop() and top() operations O(1) while push() takes O(n).

Is Implement Stack using Queues asked at Google/Amazon/Meta?

Stack and queue design problems frequently appear in interviews at companies like Amazon, Google, and Meta. This specific question tests understanding of data structure behavior and the ability to simulate one structure using another with constrained operations.

What data structure is used in Implement Stack using Queues?

The implementation uses one or two queues to simulate stack behavior. Queue operations such as enqueue, dequeue, and front access are used to reorder elements so the newest element behaves like the top of a stack.

What is the time complexity of Implement Stack using Queues?

Most implementations achieve push in O(n) time and pop in O(1) time. The push operation requires rearranging or rotating elements to maintain stack order. Space complexity is O(n) because all elements are stored inside one or two queues.

Implement Stack using Queues solution and explanation

The problem

Approach overview

Approach 1: Double Queue with Rearranging Elements

Approach 2: Single Queue with Rotation

Approach 3: Two Queues

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Implement Stack using Queues solution and explanation

The problem

Approach overview

Approach 1: Double Queue with Rearranging Elements

Approach 2: Single Queue with Rotation

Approach 3: Two Queues

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems