#232

Easy

auto_awesomeStack-based state management

LeetCode Problem Workspace

Implement Queue using Stacks

Implement a queue using two stacks, focusing on stack-based state management to achieve FIFO behavior in a queue.

Problem Statement

You are tasked with implementing a first-in, first-out (FIFO) queue using two stacks. The goal is to replicate the behavior of a normal queue with operations such as push, pop, peek, and empty. You must ensure that the queue can handle multiple operations efficiently using only stack-based operations.

The MyQueue class must support the following methods: push(x) to push an element onto the queue, pop() to remove and return the front element, peek() to return the front element without removing it, and empty() to check if the queue is empty. Implement this using two stacks, taking care to preserve the order of elements in the queue.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []] Output [null, null, null, 1, 1, false]

Explanation MyQueue myQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return false

Constraints

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

Solution Approach

Using Two Stacks

The core idea is to use two stacks to simulate the behavior of a queue. The first stack handles incoming elements with push operations, while the second stack is used for dequeueing. When popping or peeking, if the second stack is empty, transfer elements from the first stack to the second to reverse their order and achieve FIFO behavior.

Amortized Complexity Consideration

While each element may be moved between the stacks only once, the overall time complexity for a series of operations is amortized constant time. Each individual operation like push is constant time, but pop and peek operations may require transferring elements, resulting in an amortized O(1) complexity for these operations over time.

Handling Empty Queue

To check if the queue is empty, the empty() method simply checks whether both stacks are empty. This operation is efficient as it involves checking the state of two stacks, which is an O(1) operation.

Complexity Analysis

Metric	Value
Time	Amortized
Space	Depends on the final approach

Time complexity is amortized O(1) per operation, since elements are moved between the two stacks at most once. Space complexity depends on the number of elements in the queue, which in the worst case is O(n), where n is the number of elements stored in the queue at any given time.

What Interviewers Usually Probe

Candidate understands stack-based state management.
Candidate is aware of amortized time complexity in queue implementations.
Candidate can articulate how to maintain FIFO order using two stacks.

Common Pitfalls or Variants

Common pitfalls

Not handling the case where elements need to be transferred from one stack to another.
Misunderstanding the amortized time complexity, thinking that transferring elements every time leads to O(n) complexity per operation.
Overcomplicating the solution by adding unnecessary data structures or operations beyond the two stacks.

Follow-up variants

Implementing the queue using only one stack.
Designing a thread-safe queue using two stacks.
Handling dynamic resizing of stacks based on queue size.

FAQ

How does stack-based state management work in 'Implement Queue using Stacks'?

Stack-based state management uses two stacks to simulate the FIFO behavior of a queue. Elements are pushed onto the first stack, and when needed, moved to the second stack to maintain the proper order for pop and peek operations.

What is the time complexity of the pop and peek operations?

The time complexity for pop and peek is amortized O(1), as each element is only moved between stacks once.

What is the space complexity of this solution?

The space complexity is O(n), where n is the number of elements stored in the queue, as the elements are stored in two stacks.

Can we implement this queue using just one stack?

While you can implement a queue with one stack, it would require additional recursive or auxiliary storage, and may not be as efficient or straightforward as using two stacks.

What are the common mistakes in this problem?

Common mistakes include failing to handle the transfer of elements between stacks correctly, misunderstanding the amortized time complexity, and overcomplicating the solution.

terminal

Solution

Solution 1: Double Stack

We use two stacks, where `stk1` is used for enqueue, and another stack `stk2` is used for dequeue.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

class MyQueue:
    def __init__(self):
        self.stk1 = []
        self.stk2 = []

    def push(self, x: int) -> None:
        self.stk1.append(x)

    def pop(self) -> int:
        self.move()
        return self.stk2.pop()

    def peek(self) -> int:
        self.move()
        return self.stk2[-1]

    def empty(self) -> bool:
        return not self.stk1 and not self.stk2

    def move(self):
        if not self.stk2:
            while self.stk1:
                self.stk2.append(self.stk1.pop())


# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

Continue Practicing

#225 implement stack using queues #341 flatten nested list iterator #173 binary search tree iterator