Posted on 2022-12-16 17:02
Uriel 閱讀(30)
評論(0) 編輯 收藏 引用 所屬分類:
數據結構 、
閑來無事重切Leet Code
用兩個stack模擬先進先出的隊列，要求所有操作大概都是O(1)復雜度
插入喝詢問隊列頭操作都是O(1)，但是pop隊列頭的時候需要先將第一個棧導入另一個棧，然后輸出隊頭并pop，之后導回原棧，但這樣實現的時間表現還行，看了下Discussion也是這么做的
1 #232
2 #Runtime: 17 ms (Beats 87.47%)
3 #Memory: 13.4 MB (Beats 87.63%)
4
5 class MyQueue(object):
6
7 def __init__(self):
8 self.in_stk, self.out_stk = [], []
9
10 def push(self, x):
11 """
12 :type x: int
13 :rtype: None
14 """
15 self.in_stk.append(x)
16
17 def pop(self):
18 """
19 :rtype: int
20 """
21 while self.in_stk:
22 self.out_stk.append(self.in_stk.pop())
23 ans = self.out_stk.pop()
24 while self.out_stk:
25 self.in_stk.append(self.out_stk.pop())
26 return ans
27
28 def peek(self):
29 """
30 :rtype: int
31 """
32 return self.in_stk[0]
33
34
35 def empty(self):
36 """
37 :rtype: bool
38 """
39 return (not self.in_stk) and (not self.out_stk)
40
41
42
43 # Your MyQueue object will be instantiated and called as such:
44 # obj = MyQueue()
45 # obj.push(x)
46 # param_2 = obj.pop()
47 # param_3 = obj.peek()
48 # param_4 = obj.empty()