栈的逆序输出——题解

解题思路

栈遵循“后进先出”的原则。

将输入的数字按照原顺序依次压入栈中，最后输入的数字会位于栈顶。之后不断读取并删除栈顶元素，得到的顺序正好就是输入顺序的相反顺序。

处理过程：

1. 定义一个整数栈 stack<int> s；
2. 读入一个整数，就使用 s.push(x) 将它放入栈中；
3. 当 s.empty() 为假时：
   • 使用 s.top() 读取并输出栈顶元素；
   • 使用 s.pop() 删除栈顶元素。

易错点

pop() 没有返回值，不能写成：

int x = s.pop();

必须先使用 top() 读取，再使用 pop() 删除：

int x = s.top();
s.pop();

调用 top() 和 pop() 前，必须保证栈不为空。

正确性说明

设输入顺序为 $a_1,a_2,\ldots,a_n$。

所有元素依次入栈后，栈顶到栈底的顺序为 $a_n,a_{n-1},\ldots,a_1$。程序每次输出栈顶并将其删除，因此输出顺序依次为 $a_n,a_{n-1},\ldots,a_1$，正好是输入序列的逆序。

所以程序能够正确完成逆序输出。

复杂度分析

• 时间复杂度：$O(n)$；
• 空间复杂度：$O(n)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    stack<int> s;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s.push(x);
    }

    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }

    return 0;
}