C++一本通数据结构：栈

栈是线性的数据结构，入口与出口相同，先进入栈的元素后出来，类似于放一摞盘子，最后放上去的盘子最先拿。

如图，栈的头项被称为栈顶，最后一项被称为栈底

所属库

#include 

与栈相关的函数

stack  stk;               //建立int类型的栈stk，类型自定
stk.pop();                     //出栈操作，取出栈顶元素
stk.push(a);                   //入栈操作，将a存入栈的顶部
stk.size()                     //获取栈stk中的元素个数 
stk.empty()                    //判断栈stk是否为空 （空为1，不空为0）
stk.top()                      //获取栈stk栈顶位置的元素 

关于栈的题目

1.括号匹配问题

题目描述：给出一个含有括号的字符串，判断这个字符串中的括号是否互相匹配

分析：若可以互相匹配，则每当检测到一个右括号时，它的左侧都有一个左括号与之对应，与之对应的左括号是右括号位置往左数的第一个。

解法：每读到一个左括号，将其入栈，每读到一个右括号，先检测栈是否为空，若为空，则不匹配，否则出栈。

代码

#include 
#include 
#include 
using namespace std;

stack  stk;

int main () {
	char c;
	while (c = getchar()) {
		if (c == '@') break;                 //@为结束符
		if (c == '(') {
			stk.push(1);                     //左括号入栈
		}
		else if (c == ')' ) {
			if (stk.empty()) {               //如果栈为空，则不匹配
				cout << "NO" << endl;
				return 0;
			}
			else stk.pop();                  //出栈
		}
	}
	if (stk.empty()) {
		cout << "YES" << endl;
	}
	else cout << "NO" << endl;
	return 0;
}

2.求表达式的值

题目描述：给出一个后缀表达式，求它的值

分析：在后缀表达式中，若两个数字后有一个运算符，则将两个数字进行该项运算，运算优先级越低，数字与运算符距离越远

解法：依次读入这个表达式，如果为数字，直接入栈，如果为运算符，那么将栈顶的两个元素出栈运算，将运算结果入栈，后缀表达式读入完毕后，栈只剩一项，该项为这个后缀表达式的值。

代码

#include 
#include 
#include 
using namespace std;

stack  stk; 

int main () {
	char x;
	long long k = 0;
	while (x = getchar()) {
		if (x == '@') break;                             //@为结束符
		if (x >= '0' && x <= '9') {
			k = 10 * k + x - '0';
		}
		else if (x == ' ') {
			stk.push(k);                                 //入栈
			k = 0;
		}
		else {
			long long a = stk.top();
			stk.pop();
			long long b = stk.top();                     //出栈计算，入栈
			stk.pop();
			if (x == '+') stk.push(a + b);
			if (x == '-') stk.push(b - a);
			if (x == '*') stk.push(a * b);
			if (x == '/') stk.push(b / a);
		}
	}
	cout << stk.top() << endl;
	stk.pop();
	return 0;
}