Leetcode Problem Statement

Description

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

  • void push(int x) Pushes element x to the back of the queue.
  • int pop() Removes the element from the front of the queue and returns it.
  • int peek() Returns the element at the front of the queue.
  • boolean empty() Returns true if the queue is empty, false otherwise.

Notes:

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

Examples

Example 1:

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.

Follow-up: Can you implement the queue such that each operation is amortized O(1) time complexity? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer.

Key Insights

A queue is a (FIFO) first in first out data structure that can be visualized as a cashier lineup at a supermarket where customers are processed in the order they arrived. Queues are very useful in iterative graph traversal implementations.

A stack is a (LIFO) last in first out data structure that can be visualized as a stack of plates at a buffet. In Python, a list is an array of pointers stored as a contiguous memory block, which means that elements can be accessed and popped from the end in O(1) time. Elements can be appended to the end as long as the index has not reached the end of the allocated block of memory. If an element is appended to a list that has run out of space, an automatic operation allocates a new block of memory that is twice as long as the existing list and copies the values into the new list in O(N) time. Since this operation doesn’t happen all of the time, the amortized time complexity is actually O(1). Given this property, we can say that time complexity of an append operation is practically O(1).

Now that we have a solid grasp of queues and stacks, we need to figure out the little trick that will allow us to implement a queue with two stacks in O(1) amortized time. Let’s define two stacks: stack_1 and stack_2. We will always append push() new values to stack_1. If stack_2 is empty, we will take stack_1[0] and save it for the time being. Then we will loop over stack_2, pop() elements n-1 to 1 from stack_1 and append() them to stack_2. We will clear stack_1 and returned the stack_1[0] value we save earlier. By implementing this little trick, we will be able to achieve O(1) amortized time complexity.

Python Solution

class MyQueue:

    def __init__(self):
        self.stack_1 = []
        self.stack_2 = []
        
    def push(self, x: int) -> None:
        self.stack_1.append(x)

    def pop(self) -> int:
        # If stack_2 has values, pop() from the end.
        # If stack_2 is empty, save the first value in
        # stack_1 and then populate stack_2 by popping
        # values n to 1 from the end of stack_1. Set
        # stack_1 = [] and return the "top of the stack"
        if self.stack_2:
            return self.stack_2.pop()
        else:
            res = self.stack_1[0]
            # Note: The "[::-1]" syntax reverses a list
            self.stack_2 = self.stack_1[1:][::-1]
            self.stack_1 = []
            return res
        
    def peek(self) -> int:
        # If stack_2 has values, return it's tail value.
        # If stack_2 is empty, return the head of stack_1.
        if self.stack_2:
            return self.stack_2[-1]
        else:
            return self.stack_1[0]
    
    def empty(self) -> bool:
        # If stack_1 or stack_2 have values, we need
        # to return False, otherwise True
        return not (self.stack_1 or self.stack_2)
        
# 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()