Python用栈实现队列

ゞ浴缸里的玫瑰 2024-03-17 12:56 43阅读 0赞

## **1** **问题** ##

如何用栈实现队列。

## **2** **方法** ##

（1）void push(int x) 将元素 x 推到队列的末尾

（2）int pop() 从队列的开头移除并返回元素

（3）int peek() 返回队列开头的元素

（4）boolean empty() 如果队列为空，返回 true ；否则，返回 false

代码清单 1

<table> 
 <tbody> 
 <tr> 
 <td>class MyQueue: &nbsp; &nbsp;def __init__(self): &nbsp; &nbsp; &nbsp; &nbsp;""" &nbsp; &nbsp; &nbsp; &nbsp;in主要负责push，out主要负责pop &nbsp; &nbsp; &nbsp; &nbsp;""" &nbsp; &nbsp; &nbsp; &nbsp;self.stack_in = [] &nbsp; &nbsp; &nbsp; &nbsp;self.stack_out = [] # python的list像栈，先入后出。需要实现队列，先入先出。 # ✔ &nbsp; &nbsp;def push(self, x: int) -&gt; None: &nbsp; &nbsp; &nbsp; &nbsp;""" &nbsp; &nbsp; &nbsp; &nbsp;有新元素进来，就往in里面push &nbsp; &nbsp; &nbsp; &nbsp;""" &nbsp; &nbsp; &nbsp; &nbsp;self.stack_in.append(x) # ✔ &nbsp; &nbsp;def pop(self) -&gt; int: &nbsp; &nbsp; &nbsp; &nbsp;""" &nbsp; &nbsp; &nbsp; &nbsp;Removes the element from in front of queue and returns that element. &nbsp; &nbsp; &nbsp; &nbsp;""" &nbsp; &nbsp; &nbsp; &nbsp;if self.empty(): &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return None &nbsp; &nbsp; &nbsp; &nbsp;# if self.stack_in: &nbsp; &nbsp; &nbsp; &nbsp;# &nbsp; &nbsp; for i in range(len(self.stack_in)): &nbsp; &nbsp; &nbsp; &nbsp;# &nbsp; &nbsp; &nbsp; &nbsp; self.stack_out.append(self.stack_in.pop()) &nbsp; &nbsp; &nbsp; &nbsp;# return self.stack_out.pop() # 以上会出错，例如： # ["MyQueue","push","push","push","push","pop","push","pop","pop","pop","pop"] # [[],[1],[2],[3],[4],[],[5],[],[],[],[]] # 输出 # [null,null,null,null,null,1,null,5,2,3,4] # 预期结果 # [null,null,null,null,null,1,null,2,3,4,5] # push[5]时，基于先入先出的原则，[5]应该最后被pop出来。但按照上面的错误流程，[5]会被先从in转移到out然后被pop。 # 正确应该是先把out里的全pop完然后再把[5]从in转移到out然后pop。 &nbsp; &nbsp; &nbsp; &nbsp;if self.stack_out: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return self.stack_out.pop() &nbsp; &nbsp; &nbsp; &nbsp;else: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;for i in range(len(self.stack_in)): &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;self.stack_out.append(self.stack_in.pop()) &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;return self.stack_out.pop() # 为什么上面有self.stack_out.pop()，下面有self.pop()，这两个有什么区别？ # 区别在于，self.stack_out.pop()调用的不是我们在这里定义的pop函数。它调用的是stack_out作为list类的库函数， # 是list类固有的。每个list都有，随便新定义一个list，它也可以用.pop方法，返回的是list最末位的元素。 # 例如 定义list0 = [1,2,3,4]，要求return list0.pop(), list0，返回值为[4,[1,2,3]] # 下面的self.pop()是调用我们在这里定义的pop函数。 &nbsp; &nbsp;def peek(self) -&gt; int: &nbsp; &nbsp; &nbsp; &nbsp;""" &nbsp; &nbsp; &nbsp; &nbsp;Get the front element. &nbsp; &nbsp; &nbsp; &nbsp;""" &nbsp; &nbsp; &nbsp; &nbsp;ans = self.pop() &nbsp; &nbsp; &nbsp; &nbsp;self.stack_out.append(ans) &nbsp; &nbsp; &nbsp; &nbsp;return ans &nbsp; &nbsp;def empty(self) -&gt; bool: &nbsp; &nbsp; &nbsp; &nbsp;""" &nbsp; &nbsp; &nbsp; &nbsp;只要in或者out有元素，说明队列不为空 &nbsp; &nbsp; &nbsp; &nbsp;""" &nbsp; &nbsp; &nbsp; &nbsp;return not (self.stack_in or self.stack_out)</td> 
 </tr> 
 </tbody> 
</table>

## **3** **结语** ##

用栈实现队列，队列的各项函数操作是基于栈的函数的。在编辑队列的相关函数时，先思索其与栈的关系，如何用栈来实现，再直接调用栈的函数，就可以快速的实现队列的函数操作。