Queuetostack

要用队列模拟栈，可以使用两个队列来实现。以下是基于这个思路的C++代码示例：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <queue>
using namespace std;

class MyStack {
public:
    MyStack() {

    }

    void push(int x) {
        q1.push(x); // 把新元素加入到队列 q1 中
        top_element = x; // 记录栈顶元素
    }

    int pop() {
        while (q1.size() > 1) { // 把 q1 中除了最后一个元素以外的所有元素加入到 q2 中
            top_element = q1.front(); // 更新栈顶元素
            q2.push(top_element);
            q1.pop();
        }
        int result = q1.front(); // 取出最后一个元素作为出栈元素
        q1.pop();
        swap(q1, q2); // 交换 q1 和 q2
        return result;
    }

    int top() {
        return top_element; // 直接返回栈顶元素
    }

    bool empty() {
        return q1.empty(); // 判断 q1 是否为空即可
    }

private:
    queue<int> q1;
    queue<int> q2;
    int top_element;
};

​ 在这个实现中，我们把新元素加入到队列 q1 中，并记录下栈顶元素。出栈操作时，我们把 q1 中除了最后一个元素以外的所有元素加入到 q2 中，然后取出 q1 中的最后一个元素作为出栈元素，交换 q1 和 q2，再返回出栈元素。其它操作则直接访问 q1 和 top_element 即可。

​ 这样的实现可以保证出栈操作的时间复杂度为 O(n)，其中 n 是栈的大小，其它操作的时间复杂度均为 O(1)。

以下是使用上述代码实现栈的示例：

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
using namespace std;

class MyStack {
public:
    MyStack() {

    }

    void push(int x) {
        q1.push(x); // 把新元素加入到队列 q1 中
        top_element = x; // 记录栈顶元素
    }

    int pop() {
        while (q1.size() > 1) { // 把 q1 中除了最后一个元素以外的所有元素加入到 q2 中
            top_element = q1.front(); // 更新栈顶元素
            q2.push(top_element);
            q1.pop();
        }
        int result = q1.front(); // 取出最后一个元素作为出栈元素
        q1.pop();
        swap(q1, q2); // 交换 q1 和 q2
        return result;
    }

    int top() {
        return top_element; // 直接返回栈顶元素
    }

    bool empty() {
        return q1.empty(); // 判断 q1 是否为空即可
    }

private:
    queue<int> q1;
    queue<int> q2;
    int top_element;
};

int main() {
    MyStack s;
    s.push(1);
    s.push(2);
    s.push(3);
    cout << s.top() << endl; // 输出 3
    s.pop();
    cout << s.top() << endl; // 输出 2
    s.push(4);
    cout << s.top() << endl; // 输出 4
    s.pop();
    s.pop();
    cout << s.top() << endl; // 输出 1
    cout << s.empty() << endl; // 输出 0
    s.pop();
    cout << s.empty() << endl; // 输出 1
    return 0;
}

​ 在这个示例中，我们创建了一个 MyStack 对象 s，并依次把元素 1、2、3 加入到栈中。然后我们输出了栈顶元素（即 3），接着执行了一次出栈操作，再次输出栈顶元素（即 2），并把元素 4 加入到栈中。然后我们又输出了栈顶元素（即 4），接着执行了两次出栈操作，最后输出了栈是否为空的结果。

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用