栈和队列 | OI笔记

栈

特点：

元素遵循先进后出的原则
tt存储栈顶元素下标

定义

int stk[N]; // 栈
int tt = 0; // 指向栈顶元素所在位置

插入

stk[++ tt] = x;
// 从 1 开始存储

删除

tt --;

判空

tt > 0
// true 则非空，false 则为空

单调栈

分为单调递增栈和单调递减栈

含义：

栈中的元素是单调递增或单调递减的
对于栈中的 ax $\geqslant$ ay, ax 永远不会被作为答案输出，那么就在队列中删除 ax 以达到优化时间复杂度的目标

核心代码

while (tt && stk[tt] >= tmp) tt --;

stk[++ tt] = tmp;

单调栈：

求每一个数 左侧 / 右侧 离它最近且比他小的数，能将 O(n^2^) 的问题优化为 O(n)

acwing830 - 单调栈

const int N= 1e5; 
int n;
int stk[N + 10], tt;
int main()
{
	cin >> n;
	for (int i = 0; i < n; i ++)
	{
		int tmp;
		cin >> tmp;
		while (tt && stk[tt] >= tmp) tt --;
		if (!tt) cout << "-1" << ' ';
		else 	 cout << stk[tt] << ' ';
		
		stk[++ tt] = tmp;
	}
}

---

队列

特点

元素前进先出，在队尾插入元素，在队头弹出元素

定义

int q[N]; // 队列
int hh; // 队头
int tt = -1; // 队尾

插入

q[++ tt] = x;

弹出

hh ++;

队列判空

hh <= tt
// true 则非空，false则为空

循环队列

单调队列 / 滑动窗口

能够将 O(n^2^) 的时间复杂度优化成 O(n)

例题

acwing154 - 滑动窗口

const int N = 1e6;
int nums[N], q[N];

int hh = 0, tt = -1;
for (int i = 0; i < n; i ++)
{
	while (hh <= tt && i - k + 1 > q[hh]) hh ++;
	//判断队头是否滑出窗口 
	while (hh <= tt && nums[q[tt]] >= nums[i]) tt --;
	// 对队列进行严格单调性处理
	// 如果要求最大值则将 >= 改为 <= 即可
	q[++ tt] = i;
	// 读入队列 
	if (i >= k - 1) cout << nums[q[hh]] << ' ';
	// 判断 i 是否小于区间长度，如果是则跳过 
}