题目

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

示例 1：

  1. 输入：
  2. ["CQueue","appendTail","deleteHead","deleteHead"]
  3. [[],[3],[],[]]
  4. 输出：[null,null,3,-1]
  5. 示例 2：
  6. 输入：
  7. ["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
  8. [[],[],[5],[2],[],[]]
  9. 输出：[null,-1,null,null,5,2]

提示：

  • 1 <= values <= 10000
  • 最多会对 appendTail、deleteHead 进行 10000 次调用

答案

  1. class CQueue:
  3.     def __init__(self):
  4.         self.stack1 = []
  5.         self.stack2 = []
  8.     def appendTail(self, value: int) -> None:
  9.         # 全部移动到2里
  10.         while self.stack1:
  11.             self.stack2.append(self.stack1.pop())
  12.         # 加入要加入的元素
  13.         self.stack1.append(value)
  14.         # 2中的全部元素移回去
  15.         while self.stack2:
  16.             self.stack1.append(self.stack2.pop())
  17.         return self.stack1
  21.     def deleteHead(self) -> int:
  22.         if not self.stack1:
  23.             return -1
  24.         else:
  25.             return self.stack1.pop()  # 队头部删除，
  31. # Your CQueue object will be instantiated and called as such:
  32. # obj = CQueue()
  33. # obj.appendTail(value)
  34. # param_2 = obj.deleteHead()

Note

解题思路
只使用一个栈 stack1 当作队列，另一个栈 stack2 用来辅助操作。

要想将新加入的元素出现栈底，需要先将 stack1 的元素转移到 stack2，将元素入栈 stack1，最后将 stack2 的元素全部回到 stack1。
面试题09. 用两个栈实现队列 - 图1

复杂度分析
1. 插入

时间复杂度：O(n)O(n)。
空间复杂度：O(n)O(n)，使用了辅助栈的空间。
2. 删除

时间复杂度：O(1)O(1)。
空间复杂度：O(1)O(1)，stack1 当作了队列，直接在原队列上删除，没使用额外空间。

参考

https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/solution/fu-zhu-zhan-python3-c-by-z1m/