1. 数据结构 – stack（栈）

栈是只能在一端插入 / 删除元素的线性结构

插入 / 删除元素的一端称为栈顶（top），另一端称为栈底（bottom）

2. 数据结构 – queue（队列）

队列是在一端插入元素，另一端删除元素的线性结构

插入元素的一端称为队尾（rear），删除元素的一端称为队头（front）

核心对比表（一眼记牢）

表格

例题

题目：设栈与队列初始状态为空。将元素 A,B,C,D,E,F,G,H 依次轮流入栈和入队，然后依次轮流出栈和退队，则输出序列为（ ）。

A. A,B,C,D,H,G,F,E

B. B,G,D,E,F,C,H,A

C. D,C,B,A,E,F,G,H

D. G,B,E,D,C,F,A,H

步骤 1：处理「依次轮流入栈和入队」，给元素分类

“依次轮流” 的意思是：按A→B→C→D→E→F→G→H的顺序，交替执行「入栈」和「入队」—— 先提的入栈，所以第一个操作是入栈，第二个是入队，循环往复。

我们逐个元素走一遍，记录栈和队列的状态：

表格

最终得到两个结构的状态：

• 栈：栈底是 A，往上依次是 C、E，栈顶是 G（入栈顺序 A→C→E→G，栈顶永远是最后入栈的元素）

• 队列：队头是 B，往后依次是 D、F，队尾是 H（入队顺序 B→D→F→H，队头永远是最先入队的元素）

步骤 2：处理「依次轮流出栈和退队」，算出输出序列

这里的 “依次轮流” 和入的顺序对应，交替执行「出栈」和「退队」—— 先出栈 1 个，再退队 1 个，循环直到所有元素输出。

这里必须严格遵守两个规则：

1. 出栈：只能从栈顶弹出，所以栈的出栈顺序固定为 G → E → C → A

2. 退队：只能从队头弹出，所以队列的出队顺序固定为 B → D → F → H

我们逐步骤执行，记录输出结果：

表格

最终答案

最终输出序列为 G,B,E,D,C,F,A,H，对应题目中的选项 D。

1️⃣ 正向生长栈（从低地址到高地址，像「叠盘子」）

• 题目设定：S(1:50)，初始 top=0

• 生长方向：从栈底（地址 1，最下面）向栈顶（地址 50，最上面）生长

• 空栈状态：top=0（指针在栈底 1 的下方，栈里没有元素）

• 入栈规则：top += 1，然后把元素存入 S[top]

  • 第 1 个元素入栈：top=1，存在 S[1]

  • 第 2 个元素入栈：top=2，存在 S[2]

  • ...

  • 第 20 个元素入栈：top=20，存在 S[20]

👉 元素个数计算：因为每入栈一个元素，top 就加 1，所以元素个数 = top - 初始top = 20 - 0 = 20，对应选项 B。

2️⃣ 反向生长栈（从高地址到低地址，像「弹夹压子弹」）

• 题目设定：S(1:m)，初始 top=m+1

• 生长方向：从栈底（地址 m，最尾部）向栈顶（地址 1，最头部）生长（和正向完全相反）

• 空栈状态：top=m+1（指针在栈底 m 的上方，栈里没有元素）

• 入栈规则：top -= 1，然后把元素存入 S[top]

  • 第 1 个元素入栈：top=m，存在 S[m]

  • 第 2 个元素入栈：top=m-1，存在 S[m-1]

  • ...

  • 当 top=20 时，说明已经从 m+1 向下移动了 (m+1)-20 步

👉 元素个数计算：每入栈一个元素，top 就减 1，所以元素个数 = 初始top - 当前top = (m+1) - 20 = m-19，对应选项 C。

二、为什么会有「从底部算」和「从顶部算」的区别？

表格

• 正向栈：top 从 0 开始往上走，每走一步代表多一个元素，所以个数就是 top 的值（从底部往上数）。

• 反向栈：top 从 m+1 开始往下走，每走一步代表多一个元素，所以个数是初始位置减去当前位置（从顶部往下数，或者说从底部往回算）。

三、一句话总结核心逻辑

不管栈是正向还是反向生长，元素个数永远等于「空栈时的 top 指针」和「当前 top 指针」之间的差值，因为这个差值就是入栈操作让指针移动的步数，每一步对应一个元素。

• 正向栈：空栈 top=0 → 个数 = 当前 top - 0

• 反向栈：空栈 top=m+1 → 个数 = (m+1) - 当前 top