经过长达半个月的革命死战，终于来到了数据结构里更常见也更深一步的栈，队列和数组这一部分内容。然后明天就是中秋节了，这里面呢，贫道先提前祝各位道友是中秋快乐，合家团圆，心想事成，幸福美满。然后的话，就是大家喜闻乐见的看博文的环节了（虽然我感觉这种类型的也不会有什么人看。。。），闲话少叙，各位，请上眼。

栈，队列和数组

基础补充

我先说个前提啊，本人平时用$C++$比较多，所以针对这些特殊的数据结构，我就直接用$C++$的$STL$标准模板库来写了。想搞编程竞赛的童鞋们也可以去自学一下$STL$这个东西，比你考试的时候手撕算法要方便多了。

• 栈这个东西通俗讲就是一个线性表，不过对数据的存取操作只能在表的一端进行，就是插入数据和删除数据都只能通过对一个叫“栈顶”的东西进行操作完成（栈顶一般保存在指针里）。概括来说，栈的操作过程是“后进先出”。什么概念呢？举个例子：假设某栈$S = (a_1, a_2, a_3, a_4, a_5)$，其中$a_1$是栈底元素，$a_5$是栈顶元素。若元素按顺序$a_1, a_2, a_3, a_4, a_5$入栈，那么出栈顺序必定是$a_5, a_4, a_3, a_2, a_1$。

• 队列的操作方式和栈正好相反，概括来说是“先进先出”，元素只允许在表的一端插入（这种操作叫入队），在另一端弹出（这种操作叫出队）。

注：这里要打个重点号。根据栈和队列的描述，我们不难看出，不论是栈还是队列，都是一种操作受限的线性表，即他们的操作只能在表的一端或两端完成，所以假设你声明了一个栈：

stack <int> s[10];

你是万万不能直接访问$s[1]$或$s[5]$还是其他什么东西的，因为栈和队列都不允许你直接访问中间的某个元素。

注：这里要打两个重点号。选择题经常会拿着一个入栈序列或者入队序列，然后让你分析当栈或队列中所有元素均被弹出之后可能会产生什么样子的序列。考队列的情况一般出现在双端队列的情况下。

• 数组是由$n (n \ge 1)$个相同类型的数据元素组成的有限序列。道友们如果看过上一篇数据结构的笔记的话，应该能看出来，很多大题的编码我是通过数组完成的。得益于数组的连续存储和随机访问的特性，在很多情况下，数组仍然有它活跃的舞台。

---

接下来我将分别讲讲这三个数据结构的应用和他们的大题。

栈

STL中栈的操作

// 头文件
#include<stack>
using namespace std;

stack<int> s;           // 空栈

// 常用操作
s.push(x);              // 入栈，将 x 压入栈顶，O(1)
s.pop();                // 出栈，删除栈顶元素，O(1)，不返回被删元素
s.top();                // 返回栈顶元素，O(1)
s.empty();              // 判断栈是否为空，O(1)
s.size();               // 返回栈中元素个数，O(1)
s.emplace(args...);     // 原地构造并入栈，效率略高于 push，O(1)

如我们刚才所说的，栈和队列不能访问中间元素，因此不能遍历，也不能用迭代器（就是for循环里那个$i$）。所以要访问栈中的所有元素，你只能不断$.top()$然后$.pop()$。

考试的时候如果写代码规定了栈的结构和相应操作，那就按照题目要求来。

栈的应用

括号匹配

假设表达式中允许包含两种括号：圆括号$( )$和方括号$[ ]$，嵌套顺序任意，例如$( [ ] ( ) )$或$[ ( [ ] [ ] ) ]$均是合法表达式，而$[ ( ] )$，$( [ ( ) )$和$( ( ) ]$均是非法格式。

算法初始化一个空栈，顺序扫描输入的括号序列，若遇到左括号，将其压入栈中，表示新增一个待匹配的期待，且优先级最高。若遇到右括号，则检查栈是否为空：若栈为空且栈顶左括号与当前右括号匹配，则弹出栈顶，完成一次匹配；否则，括号序列非法，算法终止。扫描结束后，若栈为空，则括号序列合法，否则非法。

#include <iostream>
#include <string>
#include <stack>
using namespace std;

bool checkBrackets(const string& exp) 
{
	stack<char> st;                     // 使用 STL 栈

	for (char ch : exp) 
	{
		if (ch == '(' || ch == '[') 
		{
			st.push(ch);                // 左括号入栈
		}
		else if (ch == ')') 
		{
			if (st.empty() || st.top() != '(') 
			{
				return false;           // 栈空或栈顶不是 '('
			}
			st.pop();                   // 匹配成功，弹出
		}
		else if (ch == ']') 
		{
			if (st.empty() || st.top() != '[') 
			{
				return false;           // 栈空或栈顶不是 '['
			}
			st.pop();
		}
		// 其他字符（字母、数字、运算符等）直接忽略
	}

	return st.empty();                  // 栈空说明全部匹配
}

栈在表达式求值中的应用

中缀表达式转后缀表达式

在开这个题之前，我先介绍一下相关的概念。

• 中缀表达式：是人们常用的表达式，运算符位于两个操作数之间，如$3 + 4$。虽然符合人类阅读习惯，但不利于计算机求值。中缀表达式必须依靠括号来明确运算次序。

• 前缀表达式：运算符位于两个操作数之前，如$+ 3 4$。

• 后缀表达式：运算符位于两个操作数之后，如$3 4 +$。

然后见真题：

给定中缀表达式，将其转换成对应的后缀表达式。如中缀表达式$A + B * (C - D) - E / F$转换为$ABCD-*+EF/-$。（如果把中缀表达式写成表达式树，即非叶节点放运算符，叶节点放操作数）。

考试的时候可能会考手算，所以手算方法这里我也介绍一下：

1) 按运算优先级对整个表达式逐层加括号。

2) 将每个运算符都移到其所在括号的右括号之后，形成“左操作数 右操作符 运算符”的结构。

3) 删除所有括号，得到后缀表达式。

转化成算法的思想如下：

1) 遇到操作数：直接加入后缀表达式。

2) 遇到界限符：若为“$($”，直接入栈，若为“$)$”，不入栈，且不断弹出栈顶运算符并加入后缀表达式，直到遇到“$($”，将其弹出并丢弃。

3) 遇到运算符，分两种情况：

• 若其优先级高于栈顶运算符或栈顶为“$($”，则直接入栈。

• 若其优先级低于或等于栈顶运算符，则依次弹出栈中运算符并加入后缀表达式，直到栈空或栈顶为“$($”或栈顶运算符为优先级更低的运算符为止，再将当前运算符入栈。

代码如下：

// 返回运算符优先级，数字越大优先级越高
int priority(char op) 
{
	if (op == '+' || op == '-') return 1;
	if (op == '*' || op == '/') return 2;
	return 0;   // '(' 或 ')' 视为最低
}

// 中缀转后缀
string infixToPostfix(const string& infix) 
{
	stack<char> opStack;        // 运算符栈
	string postfix;             // 结果字符串

	for (int i = 0; i < (int)infix.size(); i++) 
	{
		char ch = infix[i];

		// 1. 跳过空格
		if (ch == ' ') continue;

		// 2. 如果是数字（支持多位数），直接加入结果
		if (isdigit(ch)) 
		{
			while (i < (int)infix.size() && isdigit(infix[i])) 
			{
				postfix += infix[i];
				i++;
			}
			postfix += ' ';     // 用空格分隔操作数，方便阅读
			i--;                // 回退一格，因为 for 循环会 i++
		}
		// 3. 左括号直接入栈
		else if (ch == '(') 
		{
			opStack.push(ch);
		}
		// 4. 右括号：弹出栈顶直到遇到左括号
		else if (ch == ')') 
		{
			while (!opStack.empty() && opStack.top() != '(') 
			{
				postfix += opStack.top();
				postfix += ' ';
				opStack.pop();
			}
			if (!opStack.empty()) opStack.pop();    // 弹出左括号，不输出
		}
		// 5. 运算符：比较优先级
		else 
		{
			// 栈顶运算符优先级 >= 当前运算符时，先弹出（保证左结合）
			while (!opStack.empty() && opStack.top() != '(' && priority(opStack.top()) >= priority(ch)) 
			{
				postfix += opStack.top();
				postfix += ' ';
				opStack.pop();
			}
			opStack.push(ch);
		}
	}

	// 6. 把栈中剩余运算符全部弹出
	while (!opStack.empty()) 
	{
		postfix += opStack.top();
		postfix += ' ';
		opStack.pop();
	}

	return postfix;
}

后缀表达式求值

算法执行过程：从左到右依次扫描表达式，若当前项是操作数，则将其入栈，若是操作符，则从栈中弹出两个操作数$op$，先弹出的是右操作数$Y$，后弹出的是左操作数$X$（左操作数就是中缀表达式里左边的数，右操作数就是右边的。加法和乘法里是不区分的，但减法和除法是必须要区分的）。执行操作数$X op Y$并将结果作为操作数压回栈中。所有项处理完毕后，栈顶元素即为最终计算结果。

// 计算后缀表达式（操作数与运算符之间用空格分隔）
int evaluatePostfix(const string& postfix) 
{
	stack<int> st;                  // 操作数栈
	istringstream iss(postfix);
	string token;

	while (iss >> token) 
	{
		// 如果是运算符
		if (token == "+" || token == "-" || token == "*" || token == "/") 
		{
			int b = st.top(); st.pop();   // 先弹出的是右操作数
			int a = st.top(); st.pop();   // 后弹出的是左操作数
			int res = 0;
			if (token == "+")      res = a + b;
			else if (token == "-") res = a - b;
			else if (token == "*") res = a * b;
			else                   res = a / b;   // 整数除法
			st.push(res);
		}
		// 否则是操作数，转换为整数后入栈
		else 
		{
			st.push(stoi(token));
		}
	}
	return st.top();                // 栈顶即为最终结果
}