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

数据结构精品课 已更新到 V2.1， 手把手刷二叉树系列课程 上线。

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

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

———–

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

这两种数据结构底层其实都是数组或者链表实现的，只是 API 限定了它们的特性，那么今天就来看看如何使用「栈」的特性来实现一个「队列」，如何用「队列」实现一个「栈」。

一、用栈实现队列

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

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

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

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

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class MyQueue:
    
    # 添加元素到队尾
    def push(self, x: int):
    
    # 删除队头的元素并返回
    def pop(self) -> int:
    
    # 返回队头元素
    def peek(self) -> int:
    
    # 判断队列是否为空
    def empty(self) -> bool:

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

type MyQueue struct {}

// 添加元素到队尾
func (q *MyQueue) push(x int) {}

// 删除队头的元素并返回
func (q *MyQueue) pop() int {}

// 返回队头元素
func (q *MyQueue) peek() int {}

// 判断队列是否为空
func (q *MyQueue) empty() bool {}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

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

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

class MyQueue {
    private Stack<Integer> s1, s2;
    
    public MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }
    // ...
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class MyQueue {
    private:
        stack<int> s1, s2;

    public:
        MyQueue() {
            stack<int> st1;
            s1 = st1;
            stack<int> st2;
            s2 = st2;
        }
        // ...
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class MyQueue:
    def __init__(self):
        self.s1 = []
        self.s2 = []
        
    # ...

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

type MyQueue struct {
    s1, s2 []int
}

func NewMyQueue() *MyQueue {
    return &MyQueue{
        s1: []int{},
        s2: []int{},
    }
}
// ...

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var MyQueue = function() {
    var s1 = [];
    var s2 = [];
    // ...
}

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

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

    /** 添加元素到队尾 */
    public void push(int x) {
        s1.push(x);
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class MyQueue {
private:
    stack<int> s1;
    stack<int> s2;

public:
    /** 添加元素到队尾 */
    void push(int x) {
        s1.push(x);
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class MyQueue:
    # 省略上文给出的代码部分，保留注释

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

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

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

/** 添加元素到队尾 */
func (this *MyQueue) push(x int)  {
    this.s1 = append(this.s1, x)
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

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

    /** 添加元素到队尾 */
    push(x) {
        this.s1.push(x);
    }
}

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

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

    /** 返回队头元素 */
    public int peek() {
        if (s2.isEmpty())
            // 把 s1 元素压入 s2
            while (!s1.isEmpty())
                s2.push(s1.pop());
        return s2.peek();
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

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

    /** 返回队头元素 */
    public:
        int peek() {
            if (s2.empty())
                // 把 s1 元素压入 s2
                while (!s1.empty()) {
                    s2.push(s1.top());
                    s1.pop();
                }

            return s2.top();
        }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

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

class MyQueue:
    def peek(self) -> int:
        if len(self.s2) == 0:
            # 把 s1 元素压入 s2
            while len(self.s1) != 0:
                self.s2.append(self.s1.pop())
        return self.s2[-1]

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

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

/** 返回队头元素 */
func (q *MyQueue) Peek() int {
    if len(q.s2) == 0 {
        // 把 s1 元素压入 s2
        for len(q.s1) > 0 {
            q.s2 = append(q.s2, q.s1[len(q.s1)-1])
            q.s1 = q.s1[:len(q.s1)-1]
        }
    }
    return q.s2[len(q.s2)-1]
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var MyQueue = function() {

    // 定义两个栈 s1 和 s2
    this.s1 = [];
    this.s2 = [];

    /** 将一个元素放入队列的尾部 */
    this.push = function(x) {
        this.s1.push(x);
    };

    /** 删除队列的第一个元素并返回 */
    this.pop = function() {
        this.peek();
        return this.s2.pop();
    };

    /** 返回队列第一个元素 */
    this.peek = function() {
        if (this.s2.length <= 0) {
            while (this.s1.length !== 0) {
                this.s2.push(this.s1.pop());
            }
        }
        return this.s2[this.s2.length - 1];
    };

    /** 判断队列是否为空 */
    this.empty = function() {
        return this.s1.length === 0 && this.s2.length === 0;
    };
};

同理，对于 pop 操作，只要操作 s2 就可以了。

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

    /** 删除队头的元素并返回 */
    public int pop() {
        // 先调用 peek 保证 s2 非空
        peek();
        return s2.pop();
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

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

    /** 删除队头的元素并返回 */
    int pop() {
        // 先调用 peek 保证 s2 非空
        peek();
        return s2.pop();
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class MyQueue:
    # 为了节约篇幅，省略上文给出的代码部分...

    def pop(self) -> int:
        # 先调用 peek 保证 s2 非空
        self.peek()
        return self.s2.pop()

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

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

/** 删除队头的元素并返回 */
func (q *MyQueue) pop() int {
    // 先调用 peek 保证 s2 非空
    q.peek()
    return q.s2.Pop()
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var MyQueue = function() {
    // 为了节约篇幅，省略上文给出的代码部分...

    /** 删除队头的元素并返回 */
    this.pop = function() {
        // 先调用 peek 保证 s2 非空
        this.peek();
        return this.s2.pop();
    }
};

最后，如何判断队列是否为空呢？如果两个栈都为空的话，就说明队列为空：

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

    /** 判断队列是否为空 */
    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

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

    /** 判断队列是否为空 */
    bool empty() {
        return s1.empty() && s2.empty();
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class MyQueue:
    # 为了节约篇幅，省略上文给出的代码部分...
 
    /** 判断队列是否为空 */
    def empty(self) -> bool:
        return self.s1.empty() and self.s2.empty()

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

type MyQueue struct {
    //省略上文给出的代码部分...
}

// 判断队列是否为空
func (q *MyQueue) empty() bool {
    return len(q.s1) == 0 && len(q.s2) == 0
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

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

    /** 判断队列是否为空 */
    this.empty = function() {
        return s1.isEmpty() && s2.isEmpty();
    }
}

至此，就用栈结构实现了一个队列，核心思想是利用两个栈互相配合。

值得一提的是，这几个操作的时间复杂度是多少呢？有点意思的是 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();
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

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

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

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

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

type MyStack struct {
    // 存储栈的数据
    data []int
}

/** 初始化栈 */
func Constructor() MyStack {
    return MyStack{make([]int, 0)}
}

/** 添加元素到栈顶 */
func (this *MyStack) Push(x int)  {
    this.data = append(this.data, x)
}

/** 删除栈顶的元素并返回 */
func (this *MyStack) Pop() int {
    n := len(this.data)
    val := this.data[n-1]
    this.data = this.data[:n-1]
    return val
}

/** 返回栈顶元素 */
func (this *MyStack) Top() int {
    return this.data[len(this.data)-1]
}

/** 判断栈是否为空 */
func (this *MyStack) Empty() bool {
    return len(this.data) == 0
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

function MyStack() {
    /** 添加元素到栈顶 */
    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;
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

#include <queue>
using namespace std;

class MyStack {
private:
    queue<int> q;
    int top_elem = 0;

public:
    /** 添加元素到栈顶 */
    void push(int x) {
        // x 是队列的队尾，是栈的栈顶
        q.push(x);
        top_elem = x;
    }
    
    /** 返回栈顶元素 */
    int top() {
        return top_elem;
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

from collections import deque

class MyStack:
    def __init__(self):
        self.q = deque()
        self.top_elem = 0

    # 添加元素到栈顶
    def push(self, x: int) -> None:
        self.q.append(x)
        self.top_elem = x

    # 返回栈顶元素
    def top(self) -> int:
        return self.top_elem

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

type MyStack struct {
    q []int
    top_elem int
}

/** 添加元素到栈顶 */
func (s *MyStack) push(x int) {
    // x 是队列的队尾，是栈的栈顶
    s.q = append(s.q, x)
    s.top_elem = x
}

/** 返回栈顶元素 */
func (s *MyStack) top() int {
    return s.top_elem
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

function MyStack() {
  var q = [];
  var top_elem = 0;

  /** 添加元素到栈顶 */
  this.push = function(x) {
    // x 是队列的队尾，是栈的栈顶
    q.push(x);
    top_elem = x;
  };

  /** 返回栈顶元素 */
  this.top = function() {
    return top_elem;
  };
}

我们的底层数据结构是先进先出的队列，每次 pop 只能从队头取元素；但是栈是后进先出，也就是说 pop API 要从队尾取元素：

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

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

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

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

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

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

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class MyStack:
  
    def pop(self) -> int:
        # 获取当前栈中元素个数
        size = len(self.q)
        while size > 1:
            # 将队头元素加入到队尾
            self.q.append(self.q.pop(0))
            size -= 1
            
        # 取出队头元素并返回
        return self.q.pop(0)

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

type MyStack struct {
    // 省略上文代码部分...
}

// 删除栈顶元素并返回
func (stack *MyStack) Pop() int {
    size := len(stack.q)
    for size > 1 {
        stack.q = append(stack.q, stack.q[0])
        stack.q = stack.q[1:]
        size--
    }
    // 之前的队尾元素已经到了队头
    result := stack.q[0]
    stack.q = stack.q[1:]
    return result
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var MyStack = function() {
    // 为了节约篇幅，省略上文给出的代码部分...

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

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

class MyStack {
    queue<int> q;
    int top_elem;
public:
    /** Initialize your data structure here. */
    MyStack() {
        
    }
    
    /** Push element x onto stack. */
    void push(int x) {
        q.push(x);
        top_elem = x;
    }
    
    /** Removes the element on top of the stack and returns that element. */
    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();
        // 移除之前的栈顶元素并返回
        return q.front();
    }
    
    /** Get the top element. */
    int top() {
        return top_elem;
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        return q.empty();
    }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

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

    /** 删除栈顶的元素并返回 */
    def pop(self) -> int:
        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 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

type MyStack struct {
    // 为了节约篇幅，省略上文给出的代码部分...
    q []int
    top_elem int
}

/** 删除栈顶的元素并返回 */
func (this *MyStack) Pop() int {
    size := len(this.q)
    // 留下队尾 2 个元素
    for size > 2 {
        n := this.q[0]
        this.q = this.q[1:]
        this.q = append(this.q, n)
        size--
    }
    // 记录新的队尾元素
    this.top_elem = this.q[0]
    n := this.q[0]
    this.q = this.q[1:]
    this.q = append(this.q, n)
    // 删除之前的队尾元素
    n = this.q[0]
    this.q = this.q[1:]
    return n
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

function MyStack() {
    // 为了节约篇幅，省略上文给出的代码部分...
    
    /** 删除栈顶的元素并返回 */
    this.pop = function () {
        let 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();
    }
}

最后，API empty 就很容易实现了，只要看底层的队列是否为空即可：

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

    /** 判断栈是否为空 */
    public boolean empty() {
        return q.isEmpty();
    }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

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

    /** 判断栈是否为空 */
    public:
        bool empty() {
            return q.empty();
        }
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

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

    '''判断栈是否为空'''
    def empty(self) -> bool:
        return self.q.empty()

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

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

/** 判断栈是否为空 */
func (this *MyStack) Empty() bool {
    return len(this.q) == 0
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。

var MyStack = function() {
    // 为了节约篇幅，省略上文给出的代码部分...

    /** 判断栈是否为空 */
    this.empty = function() {
        return q.isEmpty();
    }
}

很明显，用队列实现栈的话，pop 操作时间复杂度是 O(N)，其他操作都是 O(1)​。​

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

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

希望本文对你有帮助。

引用本文的题目

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

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

＿＿＿＿＿＿＿＿＿＿＿＿＿

《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复关键词「进群」可加入算法群；回复「全家桶」可下载配套 PDF 和刷题全家桶：

共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释