栈

STL模板

STL 中的 stack 容器提供了一众成员函数以供调用，常见的包括但不限于如下：

创建一个栈：

stack<int> stk;

修改元素：

stk.push(x); 将传入的参数插入到栈顶。
stk.pop(); 将栈顶的元素弹出。

查询：

stk.top(); 返回栈顶的元素。
stk.empty(); 返回栈是否为空。
stk.size(); 返回栈中元素的数量。

// 新建两个栈 st1 和 st2
std::stack<int> st1, st2;

// 为 st1 装入 1
st1.push(1);

// 将 st1 赋值给 st2
st2 = st1;

// 输出 st2 的栈顶元素
cout << st2.top() << endl;
// 输出: 1

数组模拟

通过两个变量 stk[N] 和 top 分别模拟栈的存储和栈顶下标，从而达到实现的目的。

创建一个栈：

int stk[N], top;

修改元素：

stk[++ top] = x; 将传入的参数插入到栈顶。
top --; 将栈顶的元素弹出。

查询：

stk[top] 返回栈顶的元素。
return top; 返回栈顶是否为空。
top 的大小即为栈中元素的多少。

// 新建一个栈 stk1
int stk[N], top;

// 将元素 1 压入栈中
stk[++ top] = 1;

// 输出 stk 中的栈顶元素
cout << stk[top] << endl;
// 输出为 1

// 将 stk 中的元素弹出栈
top --;

// 输出栈的大小
cout << top << endl;
// 输出为 0

队列

STL模板

STL 中的 queue 容器提供了一众成员函数以供调用，常见的包括但不限于如下：

创建一个队列：

queue<int> q;

修改元素：

q.push(x); 在队尾插入一个元素。
q.pop(); 在队头弹出一个元素。

查询：

q.front(); 返回队首元素。
q.back(); 返回队尾元素。
q.empty(); 判断队列是否为空。
q.size(); 返回队列中元素多少。

std::queue<int> q1, q2;

// 向 q1 的队尾插入 1
q1.push(1);

// 将 q1 赋值给 q2
q2 = q1;

// 输出 q2 的队首元素
std::cout << q2.front() << std::endl;
// 输出: 1

数组模拟

通过三个变量 q[N]，hh 和 tt 分别表示队列数组，队首和队尾。

创建一个队列：

int q[N], hh = 0, tt = -1;

修改元素：

q[++ tt] = x; 将传入的参数插入队尾。
hh ++;将队头弹出。
tt --;将队尾弹出。

查询：

q[hh] 返回对头的元素。
hh <= tt;判断队列是否为空。
tt - hh + 1返回队列中元素的数量。

int q[N], hh = 0, tt = -1;

// 向 q 的队尾插入 1
q[++ tt] = 1;

// 输出队列中的元素数量
cout << tt - hh + 1 << '\n';

// 输出队头元素并弹出
cout << q[hh ++] << '\n';

链表

由于链表的 STL 容器（list）并不常用，直接讲解数组模拟的双向链表。

数组模拟

通过四个变量（val[]， r[]， l[] 和 idx）分别表示下标为 idx 时的数值，以及这个元素左右两边所指向的下标（非元素本身）。

初始化链表：

idx = 2, r[0] = 1, l[1] = 0;

修改元素

insert(int a, int x) 在第 $a$ 个节点的右边插入元素 $x$ 。
insert(l[a], x) 在第 $a$ 个节点的左边插入元素 $x$ 。

void insert(int a, int x)
{
    val[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++;
}

remove(int a) 将第 $k$ 个元素删除：

void remove(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}