The title of this question is here
Title description
The question will give us a set of defined Queue queue interfaces, requiring the bottom layer to be implemented with two stacks.
That is to say,We are required to use two LIFO stacks to implement a FIFO Queue
Test example
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);
myQueue.push(2);
myQueue.peek();
myQueue.pop();
myQueue.empty();
Restrictions
Constraints:
1 <= x <= 9At 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.
algorithm
The key point is to useThe characteristics of LIFO, to combine and implement the functions of FIFO。
In fact, you can think of it this way. Since it is LIFO, it means that you can use the first stack as the input buffer and the second stack as the output buffer.
Thus,Each element is equal to entering and exiting the stack twice in order, LIFO and then LIFO, which is equivalent to FIFO.。
For example, the input sequence is [1, 2, 3]then pop them out one by one, and then push into another stack,
At this time it becomes[3, 2, 1]
At this time, if we pop them out in sequence, we will get 1, 2, 3, which is exactly the FIFO output sequence we originally wanted.
Program code
class MyQueue:
def __init__(self):
”””
Initialize your data structure here.
”””
self.inbox = []
self.outbox = []
def push(self, x: int) -> None:
”””
Push element x to the back of queue.
”””
self.inbox.append( x )
def pop(self) -> int:
”””
Removes the element from in front of queue and returns that element.
”””
self.peek()
return self.outbox.pop()
def peek(self) -> int:
”””
Get the front element.
”””
if len( self.outbox ) != 0:
return self.outbox[-1]
else:
while len(self.inbox) != 0:
top_of_inbox = self.inbox.pop()
self.outbox.append( top_of_inbox )
return self.outbox[-1]
def empty(self) -> bool:
”””
Returns whether the queue is empty.
”””
if len(self.inbox) + len(self.outbox) == 0:
return True
else:
return False
Complexity analysis
Time complexity: amortized O(1)
The time complexity of init(), push(), empty() functions is O(1).
In each call of peek() and pop(), the original order will be reversed again, from LIFO to FIFO, and the average amortized time complexity is O (1)
Space complexity: O(n)
The maximum length consumed by the stack is the total number of elements.
Key knowledge points
The key point is to useThe characteristics of LIFO, to combine and implement the functions of FIFO。
Each element enters and exits the stack twice in order, LIFO and then LIFO, which is equivalent to FIFO.。
Reference:
[1] Python/JS/Java/C++ sol by two stacks [w/ Comment] – Implement Queue using Stacks – LeetCode
