这是什么： 两个 STL 容器。vector
是"长度可以变的数组"，stack 是"后进先出的桶"。
为什么现在补： L07 教了
queue，但同一族的 vector 和 stack
一直没提。vector
在长度事先不知道的题里比定长数组省心得多（CSP-J
2019 T2
公交换乘就是这种），而且它是后面存图的标准工具；stack
是 NOI 大纲入门级明文要求的（2.1.3-1）。
前置： L07 的 queue——stack
的用法和它几乎一模一样。
vector：长度可变的数组#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> v; // 空的，长度 0
v.push_back(10); // 往末尾加一个
v.push_back(20);
v.push_back(30);
cout << v.size() << endl; // 3
cout << v[1] << endl; // 20 —— 下标访问和普通数组一样
for (int i = 0; i < (int)v.size(); i++) {
cout << v[i] << " ";
}
cout << endl; // 10 20 30
v.pop_back(); // 删掉末尾一个
cout << v.size() << endl; // 2
v.clear(); // 全清空
cout << v.size() << endl; // 0
return 0;
}| 写法 | 作用 |
|---|---|
vector<int> v; |
建一个空的 |
vector<int> v(n); |
建 n 个，全是 0 |
vector<int> v(n, -1); |
建 n 个，全填 -1 |
v.push_back(x) |
末尾加一个 |
v.pop_back() |
末尾删一个（不返回值） |
v.size() |
现在有几个 |
v[i] |
第 i 个（从 0 开始） |
v.empty() |
是不是空的 |
v.clear() |
全清空 |
⚠️ v.size()
的类型是无符号整数。i < v.size() 里如果 i
是 int，编译器会警告；更要命的是 v.size() - 1
在 v 为空时会变成一个巨大的正数，而不是 -1。
📝 统一写成 (int)v.size()，把它转成普通
int 再用，一劳永逸。
vector 可以直接整个排序，和数组一样：
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> v;
v.push_back(30);
v.push_back(10);
v.push_back(20);
sort(v.begin(), v.end()); // 注意：数组写 sort(a, a+n)，vector 写 begin/end
for (int i = 0; i < (int)v.size(); i++) cout << v[i] << " ";
cout << endl; // 10 20 30
return 0;
}📝 什么时候用
vector、什么时候用普通数组？
长度已知且题目给了上限（n ≤ 10^5）就用普通数组，开在
main
外面更省事；长度事先不知道、要一个一个往里塞的时候用
vector。
stack：后进先出和 L07 的 queue
是一对：队列是排队（先来的先走），栈是摞盘子（后放的先拿）。
#include <bits/stdc++.h>
using namespace std;
int main() {
stack<int> st;
st.push(1);
st.push(2);
st.push(3);
while (!st.empty()) {
cout << st.top() << " "; // top() 只看不删
st.pop(); // pop() 只删不返回
}
cout << endl; // 3 2 1 —— 和放进去的顺序正好相反
return 0;
}queue（L07 已学） |
stack（本补丁） |
区别 |
|---|---|---|
q.push(x) |
st.push(x) |
一样 |
q.front() |
st.top() |
队列看队头，栈看栈顶 |
q.pop() |
st.pop() |
都是只删不返回 |
q.empty() / q.size() |
st.empty() / st.size() |
一样 |
📝 L07 关于 queue 的那条铁律对
stack 一字不改：top()
只看不删、pop() 只删不返回，要取值必须先
int x = st.top(); st.pop(); 两步走。
栈最典型的用途是括号匹配：
#include <bits/stdc++.h>
using namespace std;
int main() {
string s = "(()())";
stack<char> st;
bool ok = true;
for (int i = 0; i < (int)s.size(); i++) {
if (s[i] == '(') {
st.push(s[i]);
} else {
if (st.empty()) { ok = false; break; } // 右括号多了
st.pop();
}
}
if (!st.empty()) ok = false; // 左括号多了
cout << (ok ? "yes" : "no") << endl; // yes
return 0;
}⚠️ 坑 1：vector 没 push_back
过就用下标，是越界。
vector<int> v;
v[0] = 5; // 错！v 里一个元素都没有编译能过，运行时是未定义行为——可能崩溃，也可能"看起来正常"然后给出错误答案，后者更难查。
vector<int> v;
v.push_back(5); // 对：先塞进去
// 或者
vector<int> w(10); // 对：一次开 10 个，w[0]~w[9] 都能用⚠️ 坑 2：栈空的时候调 top()，和 L07 队列空时调
front() 是同一个坑。
不报错，返回一堆垃圾数据，答案莫名其妙。
📝 凡是取 top() / front()
之前，先确认 !empty()。 上面括号匹配那段之所以要写
if (st.empty()) { ok = false; break; }，就是在防这个。
CSP-J 2019 T2 公交换乘（洛谷 P5661） —— 坐地铁会得到一张 45 分钟内有效的优惠券，可以免掉一次票价不超过该地铁票价的公交车费；券会累积，用的时候优先用最早得到的那张。求总花费。
"券会累积、优先用最早的"这句话直接对应一个队列式的结构，但券还会过期、还要挑价格够的，所以简单的
queue 不够用——用 vector
存所有券、配一个"从哪开始找"的指针会顺手得多。数据范围 n ≤
10⁵，想清楚你的写法会不会退化成 O(n²)。
思路提示见 S8_真题分级提示.md，代码自己写。
stack 在 CSP-J 里主要出现在 T3 的表达式类题目（2020 T3
表达式、2022 T3
逻辑表达式）。那是本次冲刺目标之外的难度，先会用，遇到再说。
vector<int> v(5); 建出来的 5
个元素初始值是多少？stack 取栈顶元素并弹出，为什么不能写成一句
int x = st.pop();？for (int i = 0; i < v.size() - 1; i++) 在
v 为空时会发生什么？vector<int> v(5, -1); 则全是 -1）pop() 的返回类型是
void，只负责删除。必须两步：int x = st.top(); st.pop();——和
L07 的 queue 完全一样。v.size() 是无符号整数，0 - 1 不会得到
-1，而是一个极大的正数，循环会一直跑下去并越界。写成
(int)v.size() - 1。以后学：
set、map、priority_queue
属于提高级（大纲
2.2.2），本次冲刺不需要。想去重和查询"有没有出现过"时，用
S3 的计数数组就够了。