用两个栈实现一个队列

1 问题

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

2 方法

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

代码清单 1

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

3 结语

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