# 栈

栈是后进先出 (last in first out, LIFO) 的线性表。

# 顺序栈

栈可以采用数组模拟，代码如下：

	// from oi-wiki
	int st[N];
	// 这里使用 st [0] (即 *st) 代表栈中元素数量，同时也是栈顶下标
	st[++*st] = var1; // 压栈

	int u = st[*st]; // 取栈顶

	if (st) --st; // 弹栈：注意越界问题，*st == 0 时不能继续弹出

	*st = 0; // 清空栈

# 共享栈

共享栈可以节省存储空间，并降低发生上溢的可能。

# Catalan 数

# 单调栈

# 题目描述

洛谷中给出的单调栈板子题 P5788 【模板】单调栈描述为

给出项数为 $n$ 的整数数列 $\{a_i\}_{i=1}^n$ . 定义函数 $f(i)$ 表示第 $i$ 个元素后第一个大于 $a_i$ 的下标。即 $f(i) = \min_{i<j\leq n, a_j>a_i}\{j\}$ . 若不存在，则 $f(i) = 0$ . 试求 $f(i), i=1,2,\dots,n$ .

# 思路

该问题的最优时间复杂度是 $O(n)$ 的。此时需要的空间复杂度为 $O(n)$ . 即只需对序列进行一次遍历即可求出所有元素对应的 $f(i)$ 值。

具体的思路是：在遍历过程中维护一个栈 (单调栈)。每次遍历到一个新元素 $a_j$ 时，尝试将栈顶所有比其小的元素弹出栈，并将其插入栈。这样，每一个被弹出的元素 $a_i$ , 比它大的最小下标的元素就是 $a_j$ , 进而 $f(i) = j$ . 伪代码如下：

单调栈

	for (int i=0;i<n;i++) {
	while (!s.empty() && s.top<a[i]) {
	s.pop();
	}
	s.push();
	}

关于单调栈中需要的信息，采用数组维护即可。

# 变形

LeetCode 496. 作为其变形，题目如下：

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置右侧的第一个比 x 大的元素。

给你两个没有重复元素的数组 nums1 和 nums2 , 下标从 0 开始计数，其中 nums1 是 nums2 的子集。

对于每个 0 <= i < nums1.length , 找出满足 nums1[i] == nums2[j] 的下标 j , 并且在 nums2 确定 nums2[j] 的下一个更大元素。如果不存在下一个更大元素，那么本次查询的答案是 -1 .

返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的下一个更大元素。

代码如下：

LeetCode496

	class Solution {
	public:
	vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
	unordered_map<int, int> ans2;
	stack<int> s;
	for (auto n:nums2) {
	while (!s.empty() && s.top()<n) {
	ans2[s.top()] = n;
	s.pop();
	}
	s.push(n);
	}

	while (!s.empty()) {
	ans2[s.top()] = -1;
	s.pop();
	}

	vector<int> ret;
	for (auto n:nums1) {
	ret.push_back(ans2[n]);
	}

	return ret;
	}
	};

# 栈