用两个栈实现一个队列

以你之姓@ 2024-03-08 03:15 107阅读 0赞

**1** **问题**

用两个栈实队列的声明如下，请实现它的两个函数appendTail和deleteHead，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回）

**2** **方法**

定义两个栈stackln和 stackOut:前者对应上面分析的第一个栈,只用于尾部插入；后者对应第二个栈，只用于头部删除。  
尾部插入：无脑压入新数字到 stackln  
头部删除：  
如果stackOut不是空，弹出栈顶；如果stackOut是空,分为两种情况:  
如果stackln也是空，代表队列为空,返回-1;否则就将 stackln的数字倒入  
stackOut 中，再弹出栈顶。

代码清单 1

<table> 
 <tbody> 
 <tr> 
 <td>class&nbsp;CQueue: def&nbsp;_init_(self): #&nbsp;存较新的尾部插入数字 self.stackIn&nbsp;=[] #&nbsp;存较老的逆序数字 self.stackOut&nbsp;=&nbsp;[] def&nbsp;appendTail(self,&nbsp;value:&nbsp;int)&nbsp;-&gt;&nbsp;None #&nbsp;直接压入stackIn self.stackIn.append(value) def&nbsp;deleteHead(self)&nbsp;-&gt;&nbsp;int: if&nbsp;self.stackout: #&nbsp;stackOut还有数字，直接pop return&nbsp;self.stackout.pop() if&nbsp;not&nbsp;self.stackIn: #&nbsp;stackIn也没有数字，队列为空 return&nbsp;-1 while&nbsp;self.stackIn: #&nbsp;将stackIn的数字倒序导入stackout中 self.stack0ut.append(self.stackIr #&nbsp;弹出stackout return&nbsp;self.stackout.pop()</td> 
 </tr> 
 </tbody> 
</table>

**3** **结语**

针对用两个栈实现队列的问题，提出运用两个栈的方法，第一个栈只用于尾部插入，第二个栈只用于头部删除。在需要删除队列头时，如果第二个栈中还有数字，就把其栈顶弹出即可，否则就把第一个栈的所有数字都逆序导入第二个栈中，然后再弹出第二个栈的栈顶。如果两个栈都没有数字，就返回-1。通过本次实验，证明该方法是有效的。此方法还略微有些不足，希望以后能运用更好的方法来实现。