本文共 1015 字,大约阅读时间需要 3 分钟。
用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成 在队列尾部插入整数 和 在队列头部删除整数 的功能。(若队列中没有元素,deleteHead 操作返回 -1 ) 【解题思路】 两个栈,一个只负责入(栈顶为队列的尾),一个只负责出(栈顶为队列的首)
- 加入队尾 appendTail()函数: 将数字 val 加入栈 A 即可。
- 删除队首deleteHead()函数: 有以下三种情况。
- 当栈 B 不为空: B中仍有已完成倒序的元素,因此直接返回 B 的栈顶元素。
- 否则,当 A 为空: 即两个栈都为空,无元素,因此返回 -1 。
- 否则: 将栈 A 元素全部转移至栈 B 中,实现元素倒序,并返回栈 B 的栈顶元素。
class CQueue(object): def __init__(self): self.A,self.B=[],[] # A负责入,B负责出 def appendTail(self, value): self.A.append(value) def deleteHead(self): if self.B: return self.B.pop() # 若B有值,先弹出 # 若B没有值,就看A if not self.A: return -1 # A没有值,返回-1 while self.A: # 若A有值,则先倒到B中 self.B.append(self.A.pop()) return self.B.pop()'''作者:jyd链接:https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/solution/mian-shi-ti-09-yong-liang-ge-zhan-shi-xian-dui-l-2/'''
转载地址:http://pfjii.baihongyu.com/