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 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.
trueif the queue is empty,
- 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.
Stack is where we add to the top and pop from the top, like a stack of plates.
Queue is where we add to the back and pop from the top, like a queue at a shop being served.
The question gives us a hint to use two stacks.
If we want to append, say to S1 (our main stack), let's say we append
Then we add B to the queue:
We want to pop the queue, in theory
a should be popped and not
b as it's first-in-first-out.
With the second stack we can add the values in the opposite way. We can do something like this:
- Add A to stack:
- We want to add B, so move A to the second stack.
stack1: stack2: a
- Add B to stack1
stack1: b stack2: a
- Add A back to stack 1
stack1: a b stack2:
a will be popped, in a queue
a was put in first so it's meant to be popped out first.
Here's a solution:
class MyQueue: def __init__(self): self.inStack, self.outStack = ,  def push(self, x: int) -> None: self.inStack.append(x) def pop(self) -> int: self.move() return self.outStack.pop() def peek(self) -> int: self.move() return self.outStack[-1] def empty(self) -> bool: return (not self.inStack) and (not self.outStack) def move(self): # moves all elements of the "inStack" to the "outStack" when the "outStack" is empty. if not self.outStack: while self.inStack: # While our instack has items in it, pop them and append them to the outstack self.outStack.append(self.inStack.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()