队列实现栈以及栈实现队列
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准,解决了之前 chatGPT 翻译可能出错的问题~
读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:
LeetCode | 力扣 | 难度 |
---|---|---|
225. Implement Stack using Queues | 225. 用队列实现栈 | 🟢 |
232. Implement Queue using Stacks | 232. 用栈实现队列 | 🟢 |
- | 剑指 Offer 09. 用两个栈实现队列 | 🟢 |
- | 剑指 Offer 09. 用两个栈实现队列 | 🟢 |
队列是一种先进先出的数据结构,栈是一种先进后出的数据结构,形象一点就是这样:
![](/algo/images/%E6%A0%88%E9%98%9F%E5%88%97/1.jpg)
这两种数据结构底层其实都是数组或者链表实现的,只是 API 限定了它们的特性,具体实现可以参见基础知识章节的 队列/栈的原理及实现。
今天来看看如何使用「栈」的特性来实现一个「队列」,如何用「队列」实现一个「栈」。
一、用栈实现队列
力扣第 232 题「用栈实现队列」让我们实现的 API 如下:
class MyQueue {
// 添加元素到队尾
public void push(int x);
// 删除队头的元素并返回
public int pop();
// 返回队头元素
public int peek();
// 判断队列是否为空
public boolean empty();
}
class MyQueue {
public:
// 添加元素到队尾
void push(int x);
// 删除队头的元素并返回
int pop();
// 返回队头元素
int peek();
// 判断队列是否为空
bool empty();
};
class MyQueue:
# 添加元素到队尾
def push(self, x: int) -> None:
pass
# 删除队头的元素并返回
def pop(self) -> int:
pass
# 返回队头元素
def peek(self) -> int:
pass
# 判断队列是否为空
def empty(self) -> bool:
pass
type MyQueue struct {}
// 添加元素到队尾
func (q *MyQueue) push(x int) {
}
// 删除队头的元素并返回
func (q *MyQueue) pop() int {
return 0
}
// 返回队头元素
func (q *MyQueue) peek() int {
}
// 判断队列是否为空
func (q *MyQueue) empty() bool {
}
var MyQueue = function() {
// 添加元素到队尾
this.push = function(x) {
}
// 删除队头的元素并返回
this.pop = function() {
}
// 返回队头元素
this.peek = function() {
}
// 判断队列是否为空
this.empty = function() {
}
}
我们使用两个栈 s1, s2
就能实现一个队列的功能(这样放置栈可能更容易理解):
![](/algo/images/%E6%A0%88%E9%98%9F%E5%88%97/2.jpg)
当调用 push
让元素入队时,只要把元素压入 s1
即可,比如说 push
进 3 个元素分别是 1,2,3,那么底层结构就是这样:
![](/algo/images/%E6%A0%88%E9%98%9F%E5%88%97/3.jpg)
那么如果这时候使用 peek
查看队头的元素怎么办呢?按道理队头元素应该是 1,但是在 s1
中 1 被压在栈底,现在就要轮到 s2
起到一个中转的作用了:当 s2
为空时,可以把 s1
的所有元素取出再添加进 s2
,这时候 s2
中元素就是先进先出顺序了:
![](/algo/images/%E6%A0%88%E9%98%9F%E5%88%97/4.jpg)
当 s2
中存在元素时,直接调用操作 s2
的 pop
方法,弹出的就是最先插入的元素,即实现了队列的 pop
操作。
完整代码如下:
class MyQueue {
private Stack<Integer> s1, s2;
public MyQueue() {
s1 = new Stack<>();
s2 = new Stack<>();
}
// 添加元素到队尾
public void push(int x) {
s1.push(x);
}
// 返回队头元素
public int peek() {
if (s2.isEmpty())
// 把 s1 元素压入 s2
while (!s1.isEmpty()) {
s2.push(s1.pop());
}
return s2.peek();
}
// 删除队头元素并返回
public int pop() {
// 先调用 peek 保证 s2 非空
peek();
return s2.pop();
}
// 判断队列是否为空
// 两个栈都为空才说明队列为空
public boolean empty() {
return s1.isEmpty() && s2.isEmpty();
}
}
#include <stack>
class MyQueue {
private:
std::stack<int> s1, s2;
public:
MyQueue() {
}
// 添加元素到队尾
void push(int x) {
s1.push(x);
}
// 返回队头元素
int peek() {
if (s2.empty())
// 把 s1 元素压入 s2
while (!s1.empty()) {
s2.push(s1.top());
s1.pop();
}
return s2.top();
}
// 删除队头元素并返回
int pop() {
// 先调用 peek 保证 s2 非空
peek();
int poppedValue = s2.top();
s2.pop();
return poppedValue;
}
// 判断队列是否为空
// 两个栈都为空才说明队列为空
bool empty() {
return s1.empty() && s2.empty();
}
};
class MyQueue:
def __init__(self):
# 使用两个栈s1和s2
self.s1 = []
self.s2 = []
# 添加元素到队尾
def push(self, x: int) -> None:
self.s1.append(x)
# 返回队头元素
def peek(self) -> int:
if not self.s2:
# 把 s1 元素压入 s2
while self.s1:
self.s2.append(self.s1.pop())
return self.s2[-1]
# 删除队头元素并返回
def pop(self) -> int:
# 先调用 peek 保证 s2 非空
self.peek()
return self.s2.pop()
# 判断队列是否为空
# 两个栈都为空才说明队列为空
def empty(self) -> bool:
return not self.s1 and not self.s2
type MyQueue struct {
s1, s2 []int
}
func Constructor() MyQueue {
return MyQueue{
s1: make([]int, 0),
s2: make([]int, 0),
}
}
// 添加元素到队尾
func (this *MyQueue) Push(x int) {
this.s1 = append(this.s1, x)
}
// 返回队头元素
func (this *MyQueue) Peek() int {
if len(this.s2) == 0 {
// 把 s1 元素压入 s2
for len(this.s1) > 0 {
this.s2 = append(this.s2, this.s1[len(this.s1)-1])
this.s1 = this.s1[:len(this.s1)-1]
}
}
return this.s2[len(this.s2)-1]
}
// 删除队头元素并返回
func (this *MyQueue) Pop() int {
// 先调用 peek 保证 s2 非空
this.Peek()
retval := this.s2[len(this.s2)-1]
this.s2 = this.s2[:len(this.s2)-1]
return retval
}
// 判断队列是否为空
// 两个栈都为空才说明队列为空
func (this *MyQueue) Empty() bool {
return len(this.s1) == 0 && len(this.s2) == 0
}
var MyQueue = function() {
// 创建两个栈 s1 和 s2
this.s1 = [];
this.s2 = [];
};
// 添加元素到队尾
MyQueue.prototype.push = function(x) {
this.s1.push(x);
};
// 返回队头元素
MyQueue.prototype.peek = function() {
// 如果 s2 为空,就要把 s1 的元素压入 s2
if (this.s2.length == 0)
while (this.s1.length) {
this.s2.push(this.s1.pop());
}
// 返回 s2 的顶部元素
return this.s2[this.s2.length-1];
};
// 删除队头元素并返回
MyQueue.prototype.pop = function() {
// 先调用 peek 保证 s2 非空
this.peek();
// 然后返回 s2 的顶部元素
return this.s2.pop();
};
// 判断队列是否为空
MyQueue.prototype.empty = function() {
// 两个栈都为空才说明队列为空
return this.s1.length == 0 && this.s2.length == 0;
};
至此,就用栈结构实现了一个队列,核心思想是利用两个栈互相配合。
值得一提的是,这几个操作的时间复杂度是多少呢?
有点意思的是 peek
操作,调用它时可能触发 while
循环,这样的话时间复杂度是 O(N),但是大部分情况下 while
循环不会被触发,时间复杂度是 O(1)。由于 pop
操作调用了 peek
,它的时间复杂度和 peek
相同。
像这种情况,可以说它们的最坏时间复杂度是 O(N),因为包含 while
循环,可能需要从 s1
往 s2
搬移元素。
但是它们的均摊时间复杂度是 O(1),这个要这么理解:对于一个元素,最多只可能被搬运一次,也就是说 peek
操作平均到每个元素的时间复杂度是 O(1)。
关于时间复杂度的分析方法,详见 时空复杂度实用分析方法。
二、用队列实现栈
如果说双栈实现队列比较巧妙,那么用队列实现栈就比较简单粗暴了,只需要一个队列作为底层数据结构就能实现了。
力扣第 225 题「用队列实现栈」让我们实现如下 API:
class MyStack {
// 添加元素到栈顶
public void push(int x);
// 删除栈顶的元素并返回
public int pop();
// 返回栈顶元素
public int top();
// 判断栈是否为空
public boolean empty();
}
class MyStack {
// 添加元素到栈顶
void push(int x);
// 删除栈顶的元素并返回
int pop();
// 返回栈顶元素
int top();
// 判断栈是否为空
bool empty();
};
class MyStack:
# 添加元素到栈顶
def push(self, x: int) -> None:
pass
# 删除栈顶的元素并返回
def pop(self) -> int:
pass
# 返回栈顶元素
def top(self) -> int:
pass
# 判断栈是否为空
def empty(self) -> bool:
pass
type MyStack struct {
}
// 添加元素到栈顶
func (s *MyStack) Push(x int) {
}
// 删除栈顶的元素并返回
func (s *MyStack) Pop() int {
}
// 返回栈顶元素
func (s *MyStack) Top() int {
}
// 判断栈是否为空
func (s *MyStack) Empty() bool {
}
var MyStack = function() {
// 添加元素到栈顶
this.push = function(x) {
};
// 删除栈顶的元素并返回
this.pop = function() {
};
// 返回栈顶元素
this.top = function() {
};
// 判断栈是否为空
this.empty = function() {
};
};
先说 push
API,直接将元素加入队列,同时记录队尾元素,因为队尾元素相当于栈顶元素,如果要 top
查看栈顶元素的话可以直接返回:
class MyStack {
Queue<Integer> q = new LinkedList<>();
int top_elem = 0;
// 添加元素到栈顶
public void push(int x) {
// x 是队列的队尾,是栈的栈顶
q.offer(x);
top_elem = x;
}
// 返回栈顶元素
public int top() {
return top_elem;
}
public boolean empty() {
return q.isEmpty();
}
}
#include<queue>
using namespace std;
class MyStack {
queue<int> q;
int top_elem = 0;
public:
// 添加元素到栈顶
void push(int x) {
// x 是队列的队尾,是栈的栈顶
q.push(x);
top_elem = x;
}
// 返回栈顶元素
int top() {
return top_elem;
}
bool empty() {
return q.empty();
}
};
class MyStack:
def __init__(self):
# 使用一个队列 q 来实现一个栈
self.q = []
# 栈顶元素
self.top_elem = 0
# 添加元素到栈顶
def push(self, x: int) -> None:
# x 是队列的队尾,是栈的栈顶
self.q.append(x)
self.top_elem = x
# 返回栈顶元素
def top(self) -> int:
return self.top_elem
# 检查栈是否为空
def empty(self) -> bool:
return len(self.q) == 0
import "container/list"
type MyStack struct {
q *list.List
top_elem int
}
// MyStack构造器
func Constructor() MyStack {
return MyStack{q: list.New()}
}
// 添加元素到栈顶
func (this *MyStack) Push(x int) {
// x 是队列的队尾,是栈的栈顶
this.q.PushBack(x)
this.top_elem = x
}
// 返回栈顶元素
func (this *MyStack) Top() int {
return this.top_elem
}
// 检查栈是否为空
func (this *MyStack) Empty() bool {
return this.q.Len() == 0
}
var MyStack = function() {
this.q = [];
this.top_elem = 0;
};
// 添加元素到栈顶
MyStack.prototype.push = function(x) {
// x 是队列的队尾,是栈的栈顶
this.q.push(x);
this.top_elem = x;
};
// 返回栈顶元素
MyStack.prototype.top = function() {
return this.top_elem;
};
MyStack.prototype.empty = function() {
return this.q.length === 0;
};
我们的底层数据结构是先进先出的队列,每次 pop
只能从队头取元素;但是栈是后进先出,也就是说 pop
API 要从队尾取元素:
![](/algo/images/%E6%A0%88%E9%98%9F%E5%88%97/5.jpg)
解决方法简单粗暴,把队列前面的都取出来再加入队尾,让之前的队尾元素排到队头,这样就可以取出了:
![](/algo/images/%E6%A0%88%E9%98%9F%E5%88%97/6.jpg)
class MyStack {
// 为了节约篇幅,省略上文给出的代码部分...
// 删除栈顶的元素并返回
public int pop() {
int size = q.size();
while (size > 1) {
q.offer(q.poll());
size--;
}
// 之前的队尾元素已经到了队头
return q.poll();
}
}
class MyStack {
// 为了节约篇幅,省略上文给出的代码部分...
// 删除栈顶的元素并返回
int pop() {
int size = q.size();
while (size > 1) {
q.push(q.front());
q.pop();
size--;
}
// 之前的队尾元素已经到了队头
int res = q.front();
q.pop();
return res;
}
};
class MyStack:
# 为了节约篇幅,省略上文给出的代码部分...
# 删除栈顶的元素并返回
def pop(self):
size = len(self.q)
while size > 1:
self.q.append(self.q.pop(0))
size -= 1
# 之前的队尾元素已经到了队头
return self.q.pop(0)
// 为了节约篇幅,省略上文给出的代码部分...
func (this *MyStack) Pop() int {
size := len(this.q)
for size > 1 {
this.q = append(this.q, this.q[0])
this.q = this.q[1:]
size--
}
// 之前的队尾元素已经到了队头
poppedElement := this.q[0]
this.q = this.q[1:]
return poppedElement
}
// 为了节约篇幅,省略上文给出的代码部分...
MyStack.prototype.pop = function() {
var size = this.q.length;
while (size > 1) {
this.q.push(this.q.shift());
size--;
}
// 之前的队尾元素已经到了队头
return this.q.shift();
};
这样实现还有一点小问题就是,原来的队尾元素被推到队头并删除了,但是 top_elem
变量没有更新,我们还需要一点小修改:
class MyStack {
// 为了节约篇幅,省略上文给出的代码部分...
// 删除栈顶的元素并返回
public int pop() {
int size = q.size();
// 留下队尾 2 个元素
while (size > 2) {
q.offer(q.poll());
size--;
}
// 记录新的队尾元素
top_elem = q.peek();
q.offer(q.poll());
// 删除之前的队尾元素
return q.poll();
}
}
class MyStack {
// 为了节约篇幅,省略上文给出的代码部分...
// 删除栈顶的元素并返回
public:
int pop() {
int size = q.size();
// 留下队尾 2 个元素
while (size > 2) {
q.push(q.front());
q.pop();
size--;
}
// 记录新的队尾元素
top_elem = q.front();
q.push(q.front());
q.pop();
// 删除之前的队尾元素
int target = q.front();
q.pop();
return target;
}
};
class MyStack:
# 为了节约篇幅,省略上文给出的代码部分...
# 删除栈顶的元素并返回
def pop(self):
size = len(self.q)
# 留下队尾 2 个元素
while size > 2:
self.q.append(self.q.pop(0))
size -= 1
# 记录新的队尾元素
self.top_elem = self.q[0]
self.q.append(self.q.pop(0))
# 删除之前的队尾元素
return self.q.pop(0)
// 为了节约篇幅,省略上文给出的代码部分...
// 删除栈顶的元素并返回
func (this *MyStack) Pop() int {
size := len(this.q)
// 留下队尾 2 个元素
for size > 2 {
this.q = append(this.q, this.q[0])
this.q = this.q[1:]
size--
}
// 记录新的队尾元素
top_elem := this.q[0]
this.q = append(this.q, this.q[0])
this.q = this.q[1:]
// 删除之前的队尾元素
result := this.q[0]
this.q = this.q[1:]
return result
}
// 省略上文给出的代码部分...
// 删除栈顶的元素并返回
MyStack.prototype.pop = function() {
var size = this.q.length;
// 留下队尾 2 个元素
while (size > 2) {
this.q.push(this.q.shift());
size--;
}
// 记录新的队尾元素
this.top_elem = this.q[0];
this.q.push(this.q.shift());
// 删除之前的队尾元素
return this.q.shift();
}
这样就实现完了,完整的代码如下:
class MyStack {
Queue<Integer> q = new LinkedList<>();
int top_elem = 0;
// 添加元素到栈顶
public void push(int x) {
q.offer(x);
top_elem = x;
}
// 删除栈顶的元素并返回
public int pop() {
int size = q.size();
while (size > 2) {
q.offer(q.poll());
size--;
}
top_elem = q.peek();
q.offer(q.poll());
return q.poll();
}
// 返回栈顶元素
public int top() {
return top_elem;
}
// 判断栈是否为空
public boolean empty() {
return q.isEmpty();
}
}
#include <queue>
class MyStack {
private:
std::queue<int> q;
int top_elem = 0;
public:
// 添加元素到栈顶
void push(int x) {
q.push(x);
top_elem = x;
}
// 删除栈顶的元素并返回
int pop() {
int size = q.size();
while (size > 2) {
q.push(q.front());
q.pop();
size--;
}
top_elem = q.front();
q.push(q.front());
q.pop();
int value = q.front();
q.pop();
return value;
}
// 返回栈顶元素
int top() {
return top_elem;
}
// 判断栈是否为空
bool empty() {
return q.empty();
}
};
from queue import Queue
class MyStack:
def __init__(self):
self.q = Queue()
self.top_elem = 0
# 添加元素到栈顶
def push(self, x: int) -> None:
self.q.put(x)
self.top_elem = x
# 删除栈顶的元素并返回
def pop(self) -> int:
size = self.q.qsize()
while size > 2:
self.q.put(self.q.get())
size -= 1
self.top_elem = self.q.queue[0]
self.q.put(self.q.get())
return self.q.get()
# 返回栈顶元素
def top(self) -> int:
return self.top_elem
# 判断栈是否为空
def empty(self) -> bool:
return self.q.empty()
type MyStack struct {
q []int
topElement int
}
func Constructor() MyStack {
return MyStack{}
}
// 添加元素到栈顶
func (this *MyStack) Push(x int) {
this.q = append(this.q, x)
this.topElement = x
}
// 删除栈顶的元素并返回
func (this *MyStack) Pop() int {
size := len(this.q)
for i := 0; i < size - 2; i++ {
this.q = append(this.q, this.q[0])
this.q = this.q[1:]
}
this.topElement = this.q[0]
this.q = append(this.q, this.q[0])
this.q = this.q[1:]
popElement := this.q[0]
this.q = this.q[1:]
return popElement
}
// 返回栈顶元素
func (this *MyStack) Top() int {
return this.topElement
}
// 判断栈是否为空
func (this *MyStack) Empty() bool {
return len(this.q) == 0
}
var MyStack = function() {
this.q = [];
this.top_elem = 0;
// 添加元素到栈顶
this.push = function(x) {
this.q.push(x);
this.top_elem = x;
}
// 删除栈顶的元素并返回
this.pop = function() {
var size = this.q.length;
while (size > 2) {
this.q.push(this.q.shift());
size--;
}
this.top_elem = this.q[0];
this.q.push(this.q.shift());
return this.q.shift();
}
// 返回栈顶元素
this.top = function() {
return this.top_elem;
}
// 判断栈是否为空
this.empty = function() {
return this.q.length === 0;
}
}
很明显,用队列实现栈的话,pop
操作时间复杂度是 O(N),其他操作都是 O(1)。
个人认为,用队列实现栈是没啥亮点的问题,但是用双栈实现队列是值得学习的。
![](/algo/images/%E6%A0%88%E9%98%9F%E5%88%97/4.jpg)
从栈 s1
搬运元素到 s2
之后,元素在 s2
中就变成了队列的先进先出顺序,这个特性有点类似「负负得正」,确实不太容易想到。
引用本文的文章
《labuladong 的算法笔记》已经出版,关注公众号查看详情;后台回复「全家桶」可下载配套 PDF 和刷题全家桶:
![](/algo/images/souyisou2.png)