题目:
用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )
示例 1:
输入:
[“CQueue”,“appendTail”,“deleteHead”,“deleteHead”]
[[],[3],[],[]]
输出:[null,null,3,-1]
示例 2:
输入:
[“CQueue”,“deleteHead”,“appendTail”,“appendTail”,“deleteHead”,“deleteHead”]
[[],[],[5],[2],[],[]]
输出:[null,-1,null,null,5,2]
提示:
1 <= values <= 10000
最多会对 appendTail、deleteHead 进行 10000 次调用
分析:
- 用队列实现,直接用用自带的函数insert插入就行,不需要用来两个栈来实现
- 用两个栈实现,用item1当作主的,另一个当辅助用,要想新的元素加入栈底,需要将之前的元素存入辅助栈中,然后将元素入栈item1,然后将辅助栈的元素压入item1
用队列实现的代码:
class CQueue:
def __init__(self):
self.item1 = []
# self.item2 = []
def appendTail(self, value: int) -> None:
# while self.item1:
# self.item2.append(self.item1.pop())
# self.item1.append(value)
# while self.item2:
# self.item1.append(self.item2.pop())
return self.item1.insert(0,value)
def deleteHead(self) -> int:
if len(self.item1) == 0:
return -1
return self.item1.pop()
用队列实现结果:
用两个栈实现的代码:
class CQueue:
def __init__(self):
self.item1 = []
self.item2 = []
def appendTail(self, value: int) -> None:
while self.item1:
self.item2.append(self.item1.pop())
self.item1.append(value)
while self.item2:
self.item1.append(self.item2.pop())
return self.item1
def deleteHead(self) -> int:
if len(self.item1) == 0:
return -1
return self.item1.pop()
用两个栈实现结果: