P4825 小鱼的数字游戏（入门）

解题思路

小鱼看到一串数字，要反着念出来。比如看到 1、2、3，就要念成 3、2、1。我们帮它把 n 个数字倒序输出。

第一步，题目给了什么？ 第一行是一个整数 n（1<n<10），第二行是 n 个数字。也就是说数字个数不超过 9 个，非常少。

第二步，怎么倒序？ 和“字母的读写”那题一样，用栈的“后进先出”性质：把 n 个数字按输入顺序一个个压进栈里，最后进去的数字在栈顶。然后连续出栈 n 次，出栈顺序就是输入顺序的反面，正好是倒序。

第三步，举个具体的例子。 输入 7 个数：3 65 23 5 34 1 30。入栈后栈里从底到顶是 3、65、23、5、34、1、30。连续出栈 7 次得到 30、1、34、5、23、65、3，这就是要输出的答案。

第四步，注意细节。 n 最大是 9，所以栈数组开 10 个位置就够了。输出时数字之间用空格隔开，最后一个数字后面换行。

第五步，和“字母的读写”那题对比。 那题是 5 个字母，这题是 n 个数字，本质完全一样：都是把输入全部入栈、再全部出栈。区别只在于这里先读入数字个数 n，循环的次数跟着 n 走，而不是固定的 5 次。

第六步，想想栈里到底存了什么。 每次入栈的数字都被保存在数组里；出栈只是把 top 往回移一个位置，并没有真的把数据删掉，只是我们不再“看”它而已。理解这一点，以后做更复杂的栈题就不会被绕晕。

小结： 只要把“入栈”和“出栈”两步想明白，倒序问题就是栈最简单的应用之一。

参考代码

// 用途：读入 n 个数字，用栈处理后倒序输出（小鱼的数字游戏）
#include <iostream>
using namespace std;

int main() {
    int cnt = 0;
    cin >> cnt;
    int st[10];  // n 最大是 9
    int top = 0;
    // 把 n 个数字依次压入栈中
    for (int i = 0; i < cnt; i++) {
        int num;
        cin >> num;
        st[top++] = num;
    }
    // 依次出栈，出栈顺序就是倒序
    for (int i = 0; i < cnt; i++) {
        if (i > 0) cout << ' ';
        cout << st[--top];
    }
    cout << endl;
    return 0;
}

复杂度分析

n 个数字，入栈 n 次、出栈 n 次，每次都是 $O(1)$，总时间 $O(n)$。空间上栈最多存 n 个数，是 $O(n)$。因为 $n\le 9$，实际时间空间都极小，瞬间完成。