Leetcode Problem Statement
Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (
void push(int x)Pushes element
xto 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.
- You must use only standard operations of a stack, which means only
push to top,
peek/pop from top,
is emptyoperations 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.
Input ["MyQueue", "push", "push", "peek", "pop", "empty"] [, , , , , ] Output [null, null, null, 1, 1, false] Explanation MyQueue myQueue = new MyQueue(); myQueue.push(1); // queue is:  myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is  myQueue.empty(); // return false
1 <= x <= 9
- At most 100 calls will be made to
- All the calls to
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.
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.
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
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
Now that we have a solid grasp of
stacks, we need to figure out the little trick that will allow us to implement a
queue with two
O(1) amortized time. Let’s define two stacks:
stack_2. We will always append
push() new values to
stack_2 is empty, we will take
stack_1 and save it for the time being. Then we will loop over
append() them to
stack_2. We will clear
stack_1 and returned the
stack_1 value we save earlier. By implementing this little trick, we will be able to achieve
O(1) amortized time complexity.
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 # 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 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()