代码随想录算法训练营第十天|232. 用栈实现队列、225. 用队列实现栈

【参考链接】

1.栈提供push 和 pop 等等接口，所有元素必须符合先进后出规则，所以栈不提供走访功能，也不提供迭代器(iterator)。 不像是set 或者map 提供迭代器iterator来遍历所有元素。

2.栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）。所以STL中栈往往不被归类为容器，而被归类为container adapter（容器适配器）。

3.栈的底层实现可以是vector，deque，list 都是可以的， 主要就是数组和链表的底层实现。

4.队列中先进先出的数据结构，同样不允许有遍历行为，不提供迭代器。

232. 用栈实现队列

【注意】

1.需要两个栈一个输入栈，一个输出栈。

2.在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。

3.如果进栈和出栈都为空的话，说明模拟的队列为空了。

【代码】

push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。
peek() -- 返回队列首部的元素。 与pop()函数功能类似。

一定要懂得复用，功能相近的函数要抽象出来，不要大量的复制粘贴，很容易出问题！
empty() -- 返回队列是否为空。

 1 class MyQueue(object):
 2 
 3     def __init__(self):
 4         #in：push，out：pop
 5         self.stack_in = []
 6         self.stack_out = []
 7 
 8     def push(self, x):
 9         """
10         :type x: int
11         :rtype: None
12         """
13         self.stack_in.append(x) #直接往in里push，不需要判断
14 
15 
16     def pop(self):
17         """
18         :rtype: int
19         """
20         if self.empty(): #in，out为空则模拟的队列中没有元素
21             return None
22         
23         if self.stack_out: #out不为空时，先移除out中的元素
24             return self.stack_out.pop()
25         else:
26             #此时out为空，需要从in中加载数据到out中，再pop()
27             for i in range(len(self.stack_in)):
28                 self.stack_out.append(self.stack_in.pop())
29             #移除列表中的一个元素(默认最后一个元素)
30             return self.stack_out.pop()
31 
32 
33     def peek(self):
34         """
35         :rtype: int
36         """
37         ans = self.pop()
38         self.stack_out.append(ans)
39         return ans
40 
41 
42     def empty(self):
43         """
44         :rtype: bool
45         """
46         #只要in或者out有元素，说明队列不为空
47         return not(self.stack_in or self.stack_out)
48 
49 
50 
51 # Your MyQueue object will be instantiated and called as such:
52 # obj = MyQueue()
53 # obj.push(x)
54 # param_2 = obj.pop()
55 # param_3 = obj.peek()
56 # param_4 = obj.empty()

225. 用队列实现栈

【注意】

1.一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时再去弹出元素就是栈的顺序了。

2.Python 中的 deque 是一个低级别的、高度优化的双端队列，对于实现优雅、高效的Pythonic 队列和堆栈很有用，它们是计算中最常见的列表式数据类型。

【代码】

使用队列实现栈的下列操作：

• push(x) -- 元素 x 入栈
• pop() -- 移除栈顶元素
• top() -- 获取栈顶元素
• empty() -- 返回栈是否为空

 1 class MyStack(object):
 2 
 3     def __init__(self):
 4         self.que = deque()
 5 
 6     def push(self, x):
 7         """
 8         :type x: int
 9         :rtype: None
10         """
11         self.que.append(x)
12 
13     def pop(self):
14         """
15         :rtype: int
16         """
17         if self.empty():
18             return None
19         for i in range(len(self.que)-1):
20             self.que.append(self.que.popleft()) #出口
21         return self.que.popleft()
22 
23 
24     def top(self):
25         """
26         :rtype: int
27         """
28         if self.empty(): #为空
29             return None
30         return self.que[-1]
31 
32 
33     def empty(self):
34         """
35         :rtype: bool
36         """
37         return not self.que 
38 
39 
40 
41 # Your MyStack object will be instantiated and called as such:
42 # obj = MyStack()
43 # obj.push(x)
44 # param_2 = obj.pop()
45 # param_3 = obj.top()
46 # param_4 = obj.empty()