力扣小白刷题之232题用栈实现队列

题目描述

使用栈实现队列的下列操作:

  • push(x) — 将一个元素放入队列的尾部。
  • pop() — 从队列首部移除元素
  • peek() — 返回队列首部的元素
  • empty() — 返回队列是否为空

说明:

  • 你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top,size 和 is empty 操作是合法的。
  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列) 来模拟一个栈,只要是标准的栈操作即可。
  • 假设所有的操作都是有效的,(例如,一个空的队列不会调用 pop 或 peek 操作)。

思路

栈的顺序为后进先出,而队列的顺序为先进先出。使用两个栈实现队列,一个元素需要经过两个栈才能出队列,在经过第一个栈时元素顺序被反转,经过第二个栈时再次被反转,此时就是先进先出顺序。

参考:https://leetcode-cn.com/problems/implement-queue-using-stacks/solution/shi-yong-liang-ge-zhan-yi-ge-zhuan-men-ru-dui-yi-g/

  • 使用两个栈,一个栈(in) 用于元素进栈,一个栈(out) 用于元素出栈。
  • pop() 或 peek() 的时候:
    • 如果 out 里面有元素,直接从 out 里弹出(pop)或者 peek 元素
    • 如果 out 里面没有元素,一次性将 in 里面的所有元素倒入 out。(为此,可以写一个辅助函数 in2out,一次性将 in 里面的元素倒入 out)
      注意:一定要保证 out 为空的时候,才能把元素从 in 里拿到 out 中。

力扣小白刷题之232题用栈实现队列_第1张图片
力扣小白刷题之232题用栈实现队列_第2张图片

代码

力扣小白刷题之232题用栈实现队列_第3张图片
力扣小白刷题之232题用栈实现队列_第4张图片

你可能感兴趣的