可变长度数组

$\text{vector}$ 与静态数组类似，但是更加灵活，具体体现在可以随时加入元素。

STL 的使用

vector<int> v(N, i); // 建一个存储 int 的变长数组，初始有 N 个值为 i 的元素（N, i 都可省略）
v.push_back(a); // 将元素 a 插入到 v 的末尾，并增加数组长度
int m = v.size(); // v.size() 返回数组长度
v.resize(n, a); // 重新调整数组大小为 n，若 n 比原来小则删除多余信息，比原来大则用 a 填充
int p = v[i]; // 支持下标直接访问对应元素，从 0 开始

vector<int>::iterator it; // 定义一个迭代器
// 迭代器有点类似指针，支持解引用，自增，自减，但不完全相同
v.begin(); // 返回数组 v 首元素的指针（迭代器）
v.end(); // 返回数组 v 末尾元素再往后一个元素的指针（迭代器），类似空指针

栈

静态数组实现

#define N 1000
int p = 0; // 栈顶指针
int stack[N];
void push(int x) {
	if (p >= N) cout << "Stack overflow!";
	else {
		stack[p] = x;
		p++;
	}
}
void pop() {
	if (p == 0) cout << "Stack is empty.";
	else p--;
}
int top() {
	if (p == 0) {
		cout << "Stack is empty.";
		return -1;
	}
	else return stack[p - 1];
}

STL 的使用

stack<int> s; // 建一个储存 int 的栈
s.push(a); // 将 a 压入栈
s.pop(); // 栈顶元素弹出
int m = s.top(); // 获取栈顶元素
int p = s.size(); // 获取元素个数
bool b = s.empty(); // 查询 s 是否为空

不开 $O2$ 优化，STL 的速度都会比较慢，此时手写是非常必要的。

典型例题

括号匹配

给定一个括号序列，判断是否合法。

**思路：**进行 while 循环，遇到左括号或者栈为空就入栈；遇到右括号，如果栈顶是与其对应的左括号，就直接弹出栈顶且不放入右括号，反之放入右括号。循环到序列末尾结束，最后判断栈若非空，则匹配不成功，反之成功。