各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 40 天。今天力扣上的每日一题是「232. 用栈实现队列」。

解题思路

两个数据结构的概念：

  • 栈：后进先出
  • 队列：先进先出

题目让我们用两个栈来实现一个队列，就是要让两个栈配合实现一个先进先出的数据结构。

思路是：「输入栈」会把输入顺序颠倒；如果把「输入栈」的元素逐个弹出放到「输出栈」，再从「输出栈」弹出元素的时候，则可以负负得正，实现了先进先出。

具体做法：

  • 可以把一个栈当做「输入栈」，把另一个栈当做「输出栈」。
    - 当 push() 新元素的时候，放到「输入栈」的栈顶，记此顺序为「输入序」。
    - 当 pop() 元素的时候，是从「输出栈」弹出元素。如果「输出栈」为空，则把「输入栈」的元素逐个 pop() 并且 push() 到「输出栈」中，这一步会把「输入栈」的栈底元素放到了「输出栈」的栈顶。此时负负得正，从「输出栈」的 pop() 元素的顺序与「输入序」相同。

以题目的下面输入为例：

  1. ["MyQueue", "push", "push", "peek", "pop", "empty"]
  2. [[], [1], [2], [], [], []]

操作的展示如下面的动图所示：

232.gif

代码

  1. class MyQueue(object):
  3.     def __init__(self):
  4.         self.stack1 = []
  5.         self.stack2 = []
  7.     def push(self, x):
  8.         self.stack1.append(x)
  10.     def pop(self):
  11.         if not self.stack2:
  12.             while self.stack1:
  13.                 self.stack2.append(self.stack1.pop())
  14.         return self.stack2.pop()
  16.     def peek(self):
  17.         if not self.stack2:
  18.             while self.stack1:
  19.                 self.stack2.append(self.stack1.pop())
  20.         return self.stack2[-1]
  22.     def empty(self):
  23.         return not self.stack1 and not self.stack2
  • 时间复杂度：push() 时间复杂度是O(1)；peek()/pop() 均摊时间复杂度是O(1)，单步操作的最坏时间复杂度是O(N)。
  • 空间复杂度：空间复杂度是O(N)，因为总的占用了N个元素的空间。

刷题心得

这个是经典题目，必须掌握的。类似的还有使用队列实现一个栈。

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！