Skip to main content
Talentd

Implement Stack using Queues - Solution & Explanation

EasyStackDesignQueue20 min readAsked at: Amazon, Microsoft, Apple +6
Practice this problem

Problem Statement

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.

The solution involves implementing two queues using arrays with helper functions for queue operations. We use these queues to implement stack operations where push is done by rotating elements between two queues, ensuring the stack order.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: push - O(n), pop, top, and empty - O(1).
Space Complexity: O(n) for two queues storing up to all stack elements at once.

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

This approach takes advantage of a single queue, rotating the elements until the newly pushed element reaches the front. This ensures it behaves as the top of the stack.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: push - O(n), pop, top, and empty - O(1).
Space Complexity: O(n), as we use only one queue to hold stack data.

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Double Queue with Rearranging Elements

Time Complexity: push - O(n), pop, top, and empty - O(1).
Space Complexity: O(n) for two queues storing up to all stack elements at once.

Single Queue with Rotation

Time Complexity: push - O(n), pop, top, and empty - O(1).
Space Complexity: O(n), as we use only one queue to hold stack data.

Two Queues—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Double Queue with Rearranging ElementsPush: O(n), Pop: O(1)O(n)When clarity matters and you want a straightforward simulation using two queues
Single Queue with RotationPush: O(n), Pop: O(1)O(n)Preferred interview solution with minimal data structures

Video Solution

Implement Stack using Queues - Leetcode 225 - Python • NeetCode • 103,863 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Implement Stack using Queues with our built-in code editor and test cases.

Practice on FleetCode
Previous

Implement Queue using Stacks