栈&队列&单调

本篇将介绍栈，队列，单调栈，单调队列，

栈

介绍

栈是一种线性数据结构，在数组的基础上添加了一个出入口
按照后进先出的原则进行删除和添加，称为LIFO (last in first out)

实现

我们可以通过数组和指针来模拟一个栈

1
2
3
4
5
6
7
8
9
10
11
int st[N];
// 这里使用 st[0] (即 *st) 代表栈中元素数量，同时也是栈顶下标

// 压栈 ：
st[++*st] = var1;
// 取栈顶 ：
int u = st[*st];
// 弹栈 ：注意越界问题, *st == 0 时不能继续弹出
if (*st) --*st;
// 清空栈
*st = 0;

也可以直接使用STL库的栈

1
2
3
4
5
6
7
8
#include <stack>
std::stack<int> st; //定义栈

st.push(1); // 为 st1 装入 1
st.top() //返回栈顶
st.pop() //弹出栈顶
st.empty() //返回是否为空
st.size() //返回元素数量

队列

介绍

队列也是一种线性数据结构，在数组的基础上添加了两个出入口
按照先进先出的原则进行删除和添加，称为FIFO (first in first out)

实现

我们可以通过数组和两个指针来模拟一个队列

1
2
3
4
5
6
7
int q[N], ql = 1, qr;

q[++qr] = x; //插入元素
ql++; //删除元素
cout << q[ql] << endl; //访问队首
cout << q[qr] << endl; //访问队尾
ql = 1; qr = 0; //清空队列

也可以直接使用STL库的队列

1
2
3
4
5
6
7
8
9
#include <queue>
std::queue<int> q; //定义队列

q.push(1); //插入队尾
q.front() //返回队首
q.back() //返回队尾
q.pop() //弹出队首
q.empty() //返回是否为空
q.size() //返回元素数量

单调

何为单调？顾名思义，单调即满足单调性的结构
结构内维护单调递增，或单调递减
我们可以在栈和队列的基础上维护单调性，使其能够判断单调情况

单调栈

将一个元素插入单调栈时，为了维护栈的单调性，需要在保证将该元素插入到栈顶后整个栈满足单调性的前提下弹出最少的元素。

例：有一个栈，栈中自顶向下的元素为 {0,11,45,81}，插入元素 14 时为了保证单调性需要依次弹出元素 0,11，操作后栈变为 {14,45,81}

实现

在原本栈的代码的基础上添加如下内容

1
2
3
4
int x //需要加入到栈中的元素
while !st.empty() && st.top()<x
    st.pop()
st.push(x)

单调队列

将一个元素插入单调队列时，为了维护队列的单调性
需要在保证将该元素插入到队尾后整个队列满足单调性的前提下弹出最少的元素。

实现

STL的queue无法完成实现单调队列，但使用数组实现的队列，可以根据单调栈的方式，实现单调队列
不同于单调栈，单调队列可以直接使用STL的优先队列类型实现，这里将着重讲解
priority_queue 默认是一个最大堆，这意味着队列的顶部元素总是具有最大的值。

1
2
3
4
5
6
7
8
9
#include <queue>

priority_queue<int,vector<int>,greater<int>> q //类型声明，参数分别为<存放的类型,存放的容器,存放的比较方式>
//当 greater<int> 换成 less<int> 将存放小根堆,即由小到大
q.top() //访问顶部元素
q.empty() //检查容器适配器是否为空
q.size() //返回元素数量
q.push(1) //插入元素并对底层容器排序
q.pop() //移除顶部元素

用例

通过单调的方式，我们可以以O(N)的方式解决滑动窗口求RMQ(区间最大最小值问题)的问题
如果使用暴力做法则需要O(NM)