AI summary
type
status
date
slug
summary
category
tags
icon
password
队列是一种先进先出的数据结构，栈是一种先进后出的数据结构，形象一点就是这样：
这两种数据结构底层其实都是数组或者链表实现的，只是 API 限定了它们的特性，具体实现可以参见基础知识章节的 队列/栈的原理及实现。
今天来看看如何使用「栈」的特性来实现一个「队列」，如何用「队列」实现一个「栈」。
232. 用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：实现MyQueue类：
void push(int x)将元素 x 推到队列的末尾
int pop()从队列的开头移除并返回元素
int peek()返回队列开头的元素
boolean empty()如果队列为空，返回true；否则，返回false
我们使用两个栈
s1, s2 就能实现一个队列的功能，当调用 push 让元素入队时，只要把元素压入 s1 即可，比如说 push 进 3 个元素分别是 1,2,3，那么底层结构就是这样：
那么如果这时候使用
peek 查看队头的元素怎么办呢？按道理队头元素应该是 1，但是在 s1 中 1 被压在栈底，现在就要轮到 s2 起到一个中转的作用了：当 s2 为空时，可以把 s1 的所有元素取出再添加进 s2，这时候 s2 中元素就是先进先出顺序了：
当
s2 中存在元素时，直接调用操作 s2 的 pop 方法，弹出的就是最先插入的元素，即实现了队列的 pop 操作。Python 的 列表（list） 可以用作 栈，因为它支持：
append()在栈顶压入元素（Push）
pop()从栈顶弹出元素（Pop）
append() 和 pop() 时间复杂度为 O(1)，适用于大多数情况。list 在删除中间元素时性能较差，因为它是 动态数组，删除元素可能会导致 数据移动。完整代码如下：
值得一提的是，这几个操作的时间复杂度是多少呢？
有点意思的是
peek 操作，调用它时可能触发 while 循环，这样的话时间复杂度是 O(N)，但是大部分情况下 while 循环不会被触发，时间复杂度是 O(1)。像这种情况，可以说它们的最坏时间复杂度是 O(N)，因为包含
while 循环，可能需要从 s1 往 s2 搬移元素。但是它们的均摊时间复杂度是 O(1)，这个要这么理解：对于一个元素，最多只可能被搬运一次，也就是说
peek 操作平均到每个元素的时间复杂度是 O(1)。225. 用队列实现栈
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop和empty）。实现MyStack类：
void push(int x)将元素 x 压入栈顶。
int pop()移除并返回栈顶元素。
int top()返回栈顶元素。
boolean empty()如果栈是空的，返回true；否则，返回false。
题目要求两个队列，其实一个队列就够了。
先说
push API，直接将元素加入队列，同时记录队尾元素，因为队尾元素相当于栈顶元素，如果要 top 查看栈顶元素的话可以直接返回。pop 的方法简单粗暴，把队列前面的都取出来再加入队尾，让之前的队尾元素排到队头，这样就可以取出了。完整代码如下：
很明显，用队列实现栈的话，
pop 操作时间复杂度是 O(N)，其他操作都是 O(1)。Python 的collections.deque提供了以下常用方法：
append(x)appendleft(x)pop()popleft()extend(iterable)extendleft(iterable)rotate(k)reverse()
个人认为，用队列实现栈是没啥亮点的问题，但是用双栈实现队列是值得学习的。
从栈
s1 搬运元素到 s2 之后，元素在 s2 中就变成了队列的先进先出顺序，这个特性有点类似「负负得正」，确实不太容易想到。