队列实现栈以及栈实现队列

labuladong原创约 2397 字

本文讲解的例题

LeetCode	力扣	难度
232. Implement Queue using Stacks	232. 用栈实现队列	🟢
-	剑指 Offer 09. 用两个栈实现队列	🟢
225. Implement Stack using Queues	225. 用队列实现栈	🟢

前置知识

阅读本文前，你需要先学习：

队列是一种先进先出的数据结构，栈是一种先进后出的数据结构，形象一点就是这样：

这两种数据结构底层其实都是数组或者链表实现的，只是 API 限定了它们的特性，具体实现可以参见基础知识章节的队列/栈的原理及实现。

今天来看看如何使用「栈」的特性来实现一个「队列」，如何用「队列」实现一个「栈」。

一、用栈实现队列

力扣第 232 题「用栈实现队列」让我们实现的 API 如下：

java 🟢

class MyQueue {
    
    // 添加元素到队尾
    public void push(int x);
    
    // 删除队头的元素并返回
    public int pop();
    
    // 返回队头元素
    public int peek();
    
    // 判断队列是否为空
    public boolean empty();
}

cpp 🤖

class MyQueue {
public:
    // 添加元素到队尾
    void push(int x);
    
    // 删除队头的元素并返回
    int pop();
    
    // 返回队头元素
    int peek();
    
    // 判断队列是否为空
    bool empty();
};

python 🤖

class MyQueue:

    # 添加元素到队尾
    def push(self, x: int) -> None:
        pass

    # 删除队头的元素并返回
    def pop(self) -> int:
        pass

    # 返回队头元素
    def peek(self) -> int:
        pass

    # 判断队列是否为空
    def empty(self) -> bool:
        pass

go 🤖

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 {
    
}

javascript 🤖

var MyQueue = function() {
    
    // 添加元素到队尾
    this.push = function(x) {
        
    }
    
    // 删除队头的元素并返回
    this.pop = function() {
        
    }
    
    // 返回队头元素
    this.peek = function() {
        
    }
    
    // 判断队列是否为空
    this.empty = function() {
        
    }
}

我们使用两个栈 s1, s2 就能实现一个队列的功能（这样放置栈可能更容易理解）：

当调用 push 让元素入队时，只要把元素压入 s1 即可，比如说 push 进 3 个元素分别是 1,2,3，那么底层结构就是这样：

那么如果这时候使用 peek 查看队头的元素怎么办呢？按道理队头元素应该是 1，但是在 s1 中 1 被压在栈底，现在就要轮到 s2 起到一个中转的作用了：当 s2 为空时，可以把 s1 的所有元素取出再添加进 s2，这时候 s2 中元素就是先进先出顺序了：

当 s2 中存在元素时，直接调用操作 s2 的 pop 方法，弹出的就是最先插入的元素，即实现了队列的 pop 操作。

完整代码如下：

java 🟢

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();
    }
}

cpp 🤖

#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();
    }
};

python 🤖

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

go 🤖

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
}

javascript 🤖

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：

java 🟢

class MyStack {
    
    // 添加元素到栈顶
    public void push(int x);
    
    // 删除栈顶的元素并返回
    public int pop();
    
    // 返回栈顶元素
    public int top();
    
    // 判断栈是否为空
    public boolean empty();
}

cpp 🤖

class MyStack {
    
    // 添加元素到栈顶
    void push(int x);
    
    // 删除栈顶的元素并返回
    int pop();
    
    // 返回栈顶元素
    int top();
    
    // 判断栈是否为空
    bool empty();
};

python 🤖

class MyStack:

    # 添加元素到栈顶
    def push(self, x: int) -> None:
        pass
    
    # 删除栈顶的元素并返回
    def pop(self) -> int:
        pass
    
    # 返回栈顶元素
    def top(self) -> int:
        pass
    
    # 判断栈是否为空
    def empty(self) -> bool:
        pass

go 🤖

type MyStack struct {
}

// 添加元素到栈顶
func (s *MyStack) Push(x int) {
}

// 删除栈顶的元素并返回
func (s *MyStack) Pop() int {
}

// 返回栈顶元素
func (s *MyStack) Top() int {
}

// 判断栈是否为空
func (s *MyStack) Empty() bool {
}

javascript 🤖

var MyStack = function() {
    
    // 添加元素到栈顶
    this.push = function(x) {
    };
    
    // 删除栈顶的元素并返回
    this.pop = function() {
    };
    
    // 返回栈顶元素
    this.top = function() {
    };
    
    // 判断栈是否为空
    this.empty = function() {
    };
};

先说 push API，直接将元素加入队列，同时记录队尾元素，因为队尾元素相当于栈顶元素，如果要 top 查看栈顶元素的话可以直接返回：

java 🟢

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();
    }
}

cpp 🤖

#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();
    }
};

python 🤖

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

go 🤖

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
}

javascript 🤖

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 要从队尾取元素：

解决方法简单粗暴，把队列前面的都取出来再加入队尾，让之前的队尾元素排到队头，这样就可以取出了：

java 🟢

class MyStack {
    // 为了节约篇幅，省略上文给出的代码部分...

    // 删除栈顶的元素并返回
    public int pop() {
        int size = q.size();
        while (size > 1) {
            q.offer(q.poll());
            size--;
        }
        // 之前的队尾元素已经到了队头
        return q.poll();
    }
}

cpp 🤖

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;
    }
};

python 🤖

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)

go 🤖

// 为了节约篇幅，省略上文给出的代码部分...

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
}

javascript 🤖

// 为了节约篇幅，省略上文给出的代码部分...

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 变量没有更新，我们还需要一点小修改：

java 🟢

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();
    }
}

cpp 🤖

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;
    }
};

python 🤖

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)

go 🤖

// 为了节约篇幅，省略上文给出的代码部分...

// 删除栈顶的元素并返回
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
}

javascript 🤖

// 省略上文给出的代码部分...

// 删除栈顶的元素并返回
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();
}

这样就实现完了，完整的代码如下：

java 🟢

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();
    }
}

cpp 🤖

#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();
    }
};

python 🤖

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()

go 🤖

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
}

javascript 🤖

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)。

个人认为，用队列实现栈是没啥亮点的问题，但是用双栈实现队列是值得学习的。

从栈 s1 搬运元素到 s2 之后，元素在 s2 中就变成了队列的先进先出顺序，这个特性有点类似「负负得正」，确实不太容易想到。

引用本文的题目

安装我的 Chrome 刷题插件点开下列题目可直接查看解题思路：

LeetCode	力扣	难度
-	剑指 Offer 09. 用两个栈实现队列	🟢

队列实现栈以及栈实现队列

225. 用队列实现栈 https://leetcode.cn/problems/implement-stack-using-queues

225. Implement Stack using Queues https://leetcode.com/problems/implement-stack-using-queues

232. 用栈实现队列 https://leetcode.cn/problems/implement-queue-using-stacks

232. Implement Queue using Stacks https://leetcode.com/problems/implement-queue-using-stacks

剑指 Offer 09. 用两个栈实现队列 https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof

剑指 Offer 09. 用两个栈实现队列 LCOF https://leetcode.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof

一、用栈实现队列

二、用队列实现栈