Implementing a FIFO Queue Using Two Stacks: Efficient Algorithm with Amortized O(1) Time Complexity

2023-10-11 12:53:33
The title of this question is described here. The question will give us a set of defined Queue queue interfaces, which requires the bottom layer to be implemented with two stacks. In other words, we are required to use two LIFO stacks to implement a FIFO Queue test exampleExample 1:Input[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”][[], [1], [2], [], [], []]Output[null, null, null, 1, 1, false]ExplanationMyQueue myQueue = new MyQueue();myQueue.push(1); myQueue.push(2); myQueue.peek(); myQueue.pop(); myQueue.empty(); 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.演算法關鍵點在於用LIFO的特質，去組合、實作出FIFO的功能。其實可以這樣想，既然是LIFO，代表可以用第一個stack作為輸入的buffer，用第二個stack作為輸出的buffer。這樣一來，每個元素等於依照順序進出了stack兩次，LIFO 再 LIFO，等價於 FIFO。例如 輸入順序是 [1, 2, 3]，再逐一pop出來，再推入另一個stack，此時變成[3, 2, 1]這時候再依序pop出來，就會得到1, 2, 3，剛好就是我們原本想要的FIFO輸出順序。程式碼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 FalseComplexity analysis time Complexity: amortized O(1)init(), push(), empty() The time complexity of the function is O(1). In each call of peek() and pop(), the original order will be reversed once more, from LIFO to FIFO. The average amortized time complexity is O (1) Space complexity: O(n)stack consumption The maximum length is the total number of elements. Key knowledge points The key point is to use the 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
1697029695
#Application #question #Implement #Queue #Stacks_Leetcode #Implement #Queue #Stacks