Posted on 2022-12-16 17:02
Uriel 阅读(27)
评论(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()