C++ 栈( stack )学习

1.栈

栈简单来说就是图1一样的东西，每一层放一个数据。添加数据后像图2一样。栈的特点为先进后出。就是先进去的后出来，后进去的先出来。经常用于前缀表达式计算和后缀表达式计算。

2.模拟栈

要模拟栈需要先在全局定义数组和函数:

int stack[1001]; // int数组模拟栈
int TOP = 0; // 栈顶指针初始化

如果想要是别的类型的栈，把数组的数据类型和push(int x)的参数改一下就好了。

1.1.入栈( push )

定义入栈( 即在栈顶添加元素 )函数:

void push(int x)
{
    TOP++;
    stack[TOP] = x;
}

1.2.出栈( pop )

定义出栈( 即删除栈顶元素 )函数:

void pop()
{
    TOP--;
}

1.3.获取栈顶元素( top )

定义获取栈顶元素函数:

int top()
{
    return st[TOP]; // 返回栈顶元素
}

3.直接使用栈( stack )

可以使用stack头文件直接调用函数，且功能更多。

3.1.导入头文件并创建栈

在代码最前面输入

#include <stack>

在main函数中输入stack <数据类型> 栈名;就能定义一个栈。

3.2.栈的操作

3.2.1.入栈( push )

入栈( 在栈顶添加元素 )函数为push()。有参函数。

push(x);

x为一个数据( 类型要和栈的类型一样 )。

3.2.2.出栈( pop )

出栈( 删除栈顶元素 )函数为pop()。无参函数。

pop();

3.2.3.获取栈顶元素( top )

获取栈顶元素函数为top()。无参函数。

top();

3.2.4.获取栈中元素个数( size )

获取栈中元素个数函数为size()。无参函数。

size();

3.2.5.判断栈是否为空( empty )

判断栈是否为空函数为empty()。无参函数。空返回1，不空返回0。

empty();

4.例

使用stack库进行后缀表达式运算。

#include <iostream> // 头文件
#include <stack>
#include <string>
#include <cmath>
using namespace std; // 命名空间

int main() // 主函数
{
    stack<string> s; // 定义栈
	string a; // 定义字符串
	getline(cin, a); // 带空格输入
    for (int i = a.length() - 1; i >= 0; i--)
	{
		int sum = 0, idx = 0;
		while (a[i] >= '0' && a[i] <= '9')
		{
			// 多位数处理
			sum = sum + (a[i] - '0') * pow(10, idx);
			idx++;
			i--;
		}
		if (sum != 0)
		{
			s.push(sum);
			continue;
		}
		// 符号处理
		int num1 = s.top();
		s.pop();
		int num2 = s.top();
		s.pop();
		if (a[i] == '+') // 加
		{
			s.push(num1 + num2);
		}
		else if (a[i] == '-') // 减
		{
			s.push(num1 - num2);
		}
		else if (a[i] == '*') // 乘
		{
			s.push(num1 * num2);
		}
		else if (a[i] == '/') // 除
		{
			if (num2 != 0)
			{
				s.push(num1 / num2);
			}
			else
			{
				s.push("wrong");
			}
		}
	}
	cout << s.top(); // 输出结果
	return 0; // 结束程序
}