P4828 栈的操作（入门）

解题思路

这道题要我们模拟栈的操作：输入 5 个整数全部入栈，然后连续做 3 次出栈，按出栈顺序输出弹出的 3 个数，最后再输出现在栈顶的元素。

第一步，想清楚栈的样子。 栈是“后进先出”的桶。5 个数按输入顺序依次入栈后，栈里从底到顶是：第 1 个输入的、第 2 个输入的、……、第 5 个输入的。栈顶是最后输入的那个数。

第二步，出栈 3 次是什么顺序？ 每次出栈都取当前栈顶。第 1 次取出最后输入的（第 5 个），第 2 次取出倒数第 2 个（第 4 个），第 3 次取出倒数第 3 个（第 3 个）。所以出栈顺序就是输入倒数中的最后 3 个数。

第三步，拿样例验证。 输入 4 9 12 6 7，入栈后栈里是 4、9、12、6、7。出栈 3 次依次得到 7、6、12，这就是第 1 行输出。此时栈里还剩 4、9，栈顶是 9，所以第 2 行输出 9。

第四步，注意输出格式。 第 1 行 3 个出栈元素用空格隔开，第 2 行输出栈顶元素，两行都要换行。

第五步，想一想为什么输出 9 而不是 4。 出栈 3 次后，栈里还剩第 1 个输入的数 4 和第 2 个输入的数 9，栈顶是后进去的 9，所以栈顶元素是 9。如果题目问的是栈底元素，那才是 4。做题时一定要分清“栈顶”和“栈底”，别把两个概念搞混。

小结： 这题只要理解“后进先出”，跟着题意一步步入栈、出栈，就能得到正确答案。

参考代码

// 用途：5 个整数入栈，做 3 次出栈输出出栈顺序，再输出剩余栈顶元素
#include <iostream>
using namespace std;

int main() {
    int st[5];
    int top = 0;
    // 把 5 个整数依次压入栈中
    for (int i = 0; i < 5; i++) {
        int num;
        cin >> num;
        st[top++] = num;
    }
    // 连续 3 次出栈，按出栈顺序输出
    for (int i = 0; i < 3; i++) {
        if (i > 0) cout << ' ';
        cout << st[--top];
    }
    cout << endl;
    // 此时栈顶元素就是剩余元素中的最后一个
    cout << st[top - 1] << endl;
    return 0;
}

复杂度分析

只有 5 个整数，入栈 5 次、出栈 3 次、再读一次栈顶，总共不到 10 次操作，每次 $O(1)$，总时间可看作 $O(1)$ 常数。空间上只用长度 5 的数组。题目规模固定，瞬间出结果。