专题9 · 数据结构1

🎬 视频节奏

1. 0–12′　栈：FILO 原理 → 数组模拟（栈指针）→ STL stack
2. 12–25′　队列：FIFO 原理 → 数组模拟 → 循环队列 → STL queue
3. 25–30′　对比：结构特性、操作逻辑、适用场景、怎么选型
4. 30–42′　例题：表达式括号匹配（栈）/ 猴子选大王（队列）
5. 42′+　拓展：后缀表达式求值 / Blah 数集

🎯 这一讲要拿下什么

• 能徒手用数组写出栈和队列，说清指针每一次怎么动。
• 能解释循环队列为什么要牺牲一个格子，以及判空 / 判满的三件套。
• 看到关键词（匹配、撤销、排队、轮转）能立刻选对结构。
• 括号匹配与约瑟夫环两道真题能独立 AC。

📦 数组

任意位置读 / 写 / 插 / 删。
自由度最高，边界全靠自己。

🥞 栈 Stack

只能从一头进出。
后放进去的先拿出来 —— FILO。

🚶 队列 Queue

从一头进、另一头出。
先来的先走 —— FIFO。

🥞 生活原型：一摞盘子

洗好的盘子一个个往上摞，用的时候只能从最上面拿。最后摞上去的，第一个被拿走 —— 这就是栈。想拿最底下那个？必须先把上面的全拿掉。

🚶 生活原型：排队买票

先来的人站前面，先买到先走；新来的人只能站到队尾，不许插队 —— 这就是队列。处理顺序完全由"到达顺序"决定。

🥞 亲手摞一次：只能从上往下拿

📖 术语表（背下来，读题才不卡）

🔧 接口速查

🕳️ 另外两个高频坑

🚶 排队演示：不许插队，也不许从队尾溜走

📖 术语 & 与栈的差别

✍️ 完整模板（背这一段就够）

const int M = 100005;
int q[M], head = 0, tail = 0;

bool empty(){ return head == tail; }
bool full() { return (tail + 1) % M == head; }
int  size() { return (tail - head + M) % M; }

void push(int x){
  if(full()) return;          // 满了就别写，否则覆盖队首
  q[tail] = x;
  tail = (tail + 1) % M;     // ★ 取模回绕
}
void pop(){
  if(empty()) return;
  head = (head + 1) % M;     // ★ 取模回绕
}
int front(){ return q[head]; }

🧠 三个公式怎么来的

🔧 接口速查

🤔 那 STL 的 queue 会假溢出吗？

不会。 STL 的 queue 默认底层是 deque（双端队列），它内部就是分块的循环结构，会自动扩容，你不用管指针回绕。

结构

栈：一头开口
队列：两头开口

指针

栈：1 个（top）
队列：2 个（head/tail）

顺序

栈：FILO（逆序）
队列：FIFO（保序）

典型场景

栈：括号匹配、撤销、DFS
队列：排队模拟、BFS

✍️ 标程（数组模拟栈）

char stk[300];          // 左括号 < 20，开 300 稳
int main(){
  string s; cin >> s;
  int top = -1;                 // 空栈
  for(int i=0;i<(int)s.size();i++){
    char c = s[i];
    if(c == '@') break;         // 结束符
    if(c == '('){
      stk[++top] = c;             // ① 入栈
    } else if(c == ')'){
      if(top < 0){                // ② 栈空 = 右括号多
        cout << "NO
"; return 0;
      }
      top--;                      // 弹出配对
    }
  }
  cout << (top < 0 ? "YES" : "NO") << '
';
  return 0;
}

🕳️ 这题的三个失分点

✍️ 标程（STL queue）

#include <queue>
int n, m;
cin >> n >> m;
queue<int> q;
for(int i=1;i<=n;i++) q.push(i);  // 编号入队

int k = 1;                            // 当前报的数
while((int)q.size() > 1){
  int x = q.front(); q.pop();        // 队首出队
  if(k == m){                         // 报到 m：淘汰
    k = 1;                            // ★ 重新从 1 报
  } else {                            // 没报到：回队尾
    q.push(x);
    k++;                              // ★ 报数 +1
  }
}
cout << q.front() << '
';

🤔 为什么这题用队列、不用栈？

因为规则是"按顺序轮转"——这一轮没轮到的，要排到后面去等着，而不是立刻回头处理它。这正是 FIFO。
如果用栈，被压下去的猴子会最先被弹出来，顺序就反了。

🧮 拓展 1：后缀表达式求值

后缀表达式（逆波兰式）把运算符放在操作数后面，如 3 4 + 5 * = 35，不需要括号。

🔢 拓展 2：Blah 数集

数集从 a 开始，每次产生 2x+1 和 3x+1，要求从小到大输出第 n 项。

① 特判档：先别想算法，看数据范围表

题目给的数据范围表就是出题人给你的送分清单。看到「n = 1」「只有一组数据」这类一行， 就先写个 if 直接输出答案。2 分钟换 5~10 分，全场最划算。

② 暴力档：按题意最直白地写一遍

多重循环、DFS 全枚举、朴素 O(n³)……不要优化，只要保证最小那档全对。 它既是保底分，又是后面对拍的标尺——没有它你无法证明正解是对的。

③ 特殊性质档：题目里那句「若……」

常见的送分性质：数据已经有序、所有值完全相同、规模小到可以 O(n²)、 只出现一种类型。题目写出来就是让你拿的，专门写一份即可。

④ 正解档：思路定了，就赢了八成

考场上的时间几乎都花在想思路上，不是写代码。写完先跑样例， 再用第 ② 档的暴力版造小数据对拍——这是唯一能证明你思路对的办法。

表达式括号匹配 · BRACKET

第1档 · 2 分钟
输入只有 @ → Yes

第2档 · 8 分钟
反复扫描删除相邻的 ()，删不动了看是否为空

第3档 · 10 分钟
只有一种括号 → 可以不记类型，单纯计数（前缀非负且总数相等）

第4档 · 15 分钟
栈：遇 ( 入栈，遇 ) 看栈顶，最后栈空

猴子选大王 · MONKEY

第1档 · 2 分钟
n == 1 → 1

第2档 · 8 分钟
数组模拟，每次数 m 个删一个，n ≤ 10⁴ 稳过

第3档 · 10 分钟
m == 2 → 有 O(1) 公式 2·(n−2^⌊log₂n⌋)+1

第4档 · 15 分钟
队列模拟：没数到 m 的出队再入队，数到 m 的出局，直到剩一个