题目:
用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )
示例 1:
输入:
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出:[null,null,3,-1]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof
class CQueue:
def __init__(self):
self.A,self.B=[],[]
def appendTail(self, value: int) -> None:
self.A.append(value)
def deleteHead(self) -> int:
if self.B:
return self.B.pop()
elif not self.A:
return -1
else:
while self.A:
self.B.append(self.A.pop())
return self.B.pop()
用两个栈实现一个队列 来进行删除头元素和添加队尾元素,
需要一个栈用来进行插入队尾 另一个栈进行删除头元素操作。
即删除头元素时 因为A栈的头元素被压入栈底 所以只能通过B栈来进行出栈操作删除头元素。
刚开始B栈无元素 需判断A栈是否有元素:
有两种情况:
- 如果A栈没有元素 则B栈肯定也没有 则返回-1
- A栈中有元素 将A栈中的元素压入B栈 例如123 进A栈
入B栈后就是321 即删除B栈栈顶元素的顺序队列的出队顺序相同:
B栈存放的就是其实就是待删除的元素了。
此时如果进行添加队尾元素操作,则还是入A栈。因为他前面的元素还在B栈等待进行删除操作,
不用考虑队列的完整性。