AT_tenka1_2013_qualB_b 天下一後入れ先出しデータ構造

栈是最基本的数据结构之一，它以后进先出（Last In First Out，LIFO）的方式存储数据。栈最初为空，可以进行元素的添加和取出操作，但取出操作总是按照最后添加的顺序进行。 有一天，在天下一株式会社工作的ユウヤ君被要求扮演栈的角色。你担心ユウヤ君，于是决定帮他处理输入中给出的命令序列，并按照要求输出结果。 --- 输入以如下格式从标准输入给出。 > $Q$ $L$ $query_1$ $query_2$ $\ldots$ $query_Q$ - 第 $1$ 行给出命令的数量 $Q$（$1 \leq Q \leq 10^5$）和栈的最大容量 $L$（$1 \leq L \leq 2147483647$），两者以空格分隔。 - 第 $2$ 行到第 $Q+1$ 行的 $Q$ 行中，第 $i$（$1 \leq i \leq Q$）行给出第 $i$ 条命令。 每条命令属于以下 $4$ 种之一： 1. Push $N$ $M$ - 向栈中添加 $N$ 个元素 $M$。不输出任何内容。 2. Pop $N$ - 从栈中取出 $N$ 个元素。无输出。 3. Top - 输出栈顶元素，输出占一行。该操作不会改变栈的内容。 4. Size - 输出栈中元素的数量，输出占一行。 $N$、$M$ 均为整数，满足 $1 \leq N \leq 10^5$，$-2^{20} \leq M \leq 2^{20}$。 其中，栈顶元素指的是当前最后被加入的元素，即如果此时执行一次 Pop 1，将被取出的元素。 - 若 $Q \leq 50$，$N \leq 50$，则本题可获得 $30$ 分的部分分（满分 $60$ 分）。 请依次处理所有命令，并在遇到 Top 或 Size 命令时输出结果。 但在以下 $3$ 种情况下，栈会抛出异常并终止： - 若在元素数量大于 $L-N$ 的栈上执行 Push $N$ $M$ - 若在元素数量小于 $N$ 的栈上执行 Pop $N$ - 若在空栈上执行 Top 栈抛出的异常如下： - 若因 Push 操作异常导致程序终止，输出 `FULL` - 若因 Pop 或 Top 操作异常导致程序终止，输出 `EMPTY` 这些异常均输出一行，且异常发生后栈会放弃后续所有命令。 如果栈能顺利处理所有命令，则最后输出一行 `SAFE`。 ``` 7 20 Push 2 3 Push 4 5 Top Size Pop 5 Top Size ``` ``` 5 6 3 1 SAFE ``` ``` 1 10 Push 40 40 ``` ``` FULL ``` ``` 5 10 Push 1 2 Top Pop 1 Top Size ``` ``` 2 EMPTY ``` ``` 4 10 Top Size Push 1 1 Top ``` ``` EMPTY ```

第 $1$ 行包含两个整数 $Q$ 和 $L$，以空格分隔。 接下来 $Q$ 行，每行一条命令，格式如下之一： - `Push N M` - `Pop N` - `Top` - `Size`

每遇到一次 Top 或 Size 命令，输出一行结果。 若遇到异常，输出一行 `FULL` 或 `EMPTY`，并终止程序。 若所有命令均正常处理，最后输出一行 `SAFE`。

- $Q$ 的最大值为 $10^5$，$L$ 的最大值为 $2147483647$。 - $N$ 的最大值为 $10^5$，$M$ 的取值范围为 $-2^{20}$ 到 $2^{20}$。 - 若输入规模较小（$Q \leq 50$，$N \leq 50$），可获得部分分。 - 注意高效实现栈的操作，避免超时或内存超限。 由 ChatGPT 4.1 翻译