数据结构
数组 array
·数组有维度之分, 是十分重要的数据结构, 最简单的数组是一维数组, 其逻辑结构为线性表.
·数组的特点: 插入删除是 $O(n)$ 的, 但是可以随机下标访问.
STL中的可变长度数组 vector
基础操作
<vector>
vector <int> v;
vector <int> :: iterator it;
v.push_back(x); v.pop_back();
v.front(); v.back(); v.begin(); v.end();
v.size(); v.empty(); v.clear(); v[k];
遍历
for (auto x : v) // v数组的值不改变
x++;
for (auto &x : v) // v数组的值改变
x++;
链表 list
·链表也是线性表的一种, 但是它不按照线性的顺序存储数据, 而是存放到下一个元素的指针.
·可以实现 $O(1)$ 的插入, 但是不支持随机查询任一元素.
·链表的特点: 插入删除迅速, 不支持随机下标访问.
链表的实现
使用数组实现.
常见应用及例题
存图(链式前向星), 约瑟夫问题.
栈 stack
·栈是一种特殊的线性表, 只能在一端插入 / 删除.
·被弹出栈的数据总是栈中所有数据中最后进来的那个，这种储存数据的方法叫做先进后出（FILO, First In Last Out).
基础操作
·最上面的元素被称为栈顶 (top).
·把一个元素放到栈的最上面被称为压入 (push).
·把栈顶从栈中删除被称为弹出 (pop).
栈的实现
建议数组模拟.
int stack[100010], top = 0;
void push(int x) {
stack[++top] = x;
}
int pop() {
return stack[top--];
}
常见应用及例题
维护递归, 实现 \(dfs\), 单调栈优化 \(dp\), 括号匹配.
STL中的栈 stack
<stack>
stack <int> st;
s.push(x); s.pop(); s.size(); s.empty();
单调栈
队列 queue
·队列也是线性表.
·被移除队列的数总是队列中最早进来的那个, 这种储存数据的方法叫做先进先出 (FIFO, First In First Out).
·如果每次入队出队都是由 $head++$ $tail++$ 完成, 会出现队列 "假溢" 的情况.
·我们可以尝试循环的利用队列的空间, 这就被称作循环队列.
·循环队列很简单, 当指针移动到数组最后一个元素的时候让它回到第一个就好了.
基础操作
·队列最前端的数叫做队头(front), 最后端的数叫做队尾(back).
·入队(push): 在队列最前端的前面加入一个数.
·出队(pop): 把队列最后端的数移出队列.
队列的实现
数组 \(q\), 这是队列的本体.
\(head\) \(tail\) 分别表示队头的下标和队尾的下标.
入队和栈一样, 若要加入数 \(x\), 让 \(tail++\), 然后给 \(q[tail]\) 赋值为 \(x\) 即可.
出队只需让 \(head++\).
int q[100010], head = 1, tail = 0;
void push(int x) {
q[++tail] = x;
}
int pop() {
return q[head++];
}
循环队列的实现
if (tail == n + 1) tail = 1; q[tail] = x;
STL中的队列 queue
<queue>
queue <int> q; q.push(x) q.pop();
q.front(); q.back(); q.size(); q.empty();
单调队列
即队列元素单调递增 (或递减), 是一个 \(O(n)\) 的算法.
单调队列的实现
实现 (递增): 插入 \(x\) 时若队尾元素比 \(x\) 大, 则不断将队尾元素弹出.
void push(int x) {
while (tail >= head && que[tail] <= x) tail --;
st[++tail] = x;
}