栈&单调栈笔记

栈

先进后出，由于 STL 中的 stack 内存分配逻辑是 deque，常数极大，所以通常用数组或 vector 模拟。

对于数组模拟栈，数组的第一个位置通常被设为栈顶，下面是已被封装成类的代码。

struct stackr{
	long long sta[10000];
	int to=-1;
	void push(long long push_in){sta[++to]=push_in;};
	void pop(){--to;};
	int size(){return to+1;};
	bool empty(){return to<=-1;};
	long long top(){return sta[to];};
};

对于使用 vector 模拟栈，不难发现，stack 和 vector 有许多类似之处：

单调栈

常用于求解下一个大于或小于 \(x\in \mathbb Z\) 的位置，时间复杂度常常是 \(\mathcal O(n)\)。