栈 - 北冥有鱼 | Scarecrow = 2022

# 简介

和队列一样，栈 stack 也是一种线性序列结构，其存放的元素也是按照线性逻辑次序排列的，然而，与一般的线性结构相比，栈的操作仅限于逻辑上特定的一端，即新元素只能从栈的一端插入，也只能从这一端删除已有的元素。栈中允许元素插入和删除的一端称为栈顶，禁止操作的盲端称为栈底。于是，插入元素和删除元素就分别成为入栈和出栈。

	// 常规操作
	#include <iostream>
	#include <stack>
	#include <cstdio>

	using namespace std;

	stack<int> myStack;

	int main()
	{
	printf("the size of myStack:%d\n", myStack.size());
	for (int i = 0; i < 10; ++i)
	{
	myStack.push(i);
	}
	printf("the top of myStack:%d\n", myStack.top());
	printf("the size of myStack:%d\n", myStack.size());
	int sum = 0;
	while (!myStack.empty())
	{
	sum += myStack.top();
	myStack.pop();
	}
	printf("sum:%d\n", sum);
	if (myStack.empty())
	{
	printf("myStack is empty");
	}
	return 0;
	}

	the size of myStack:0
	the top of myStack:9
	the size of myStack:10
	sum:45
	myStack is empty

# 栈的应用

# 逆序输出

You are given a sequence of integer numbers. Zero-complexity transposition of the sequence is the reverse of this sequence. Your task is to write a program that prints zero-complexity transposition of the given sequence.

输入描述
For each case, the first line of the input file contains one integer n-length of the sequence (0 ＜ n ≤ 10 000). The second line contains n integers numbers-a1, a2, …, an (-1 000 000 000 000 000 ≤ ai ≤ 1 000 000 000 000 000).

输出描述
For each case, on the first line of the output file print the sequence in the reverse order.

输入

	5
	-3 4 6 -8 9

输出

9 -8 6 4 -3

测试代码

	#include <iostream>
	#include <stack>
	#include <cstdio>

	using namespace std;

	stack<long long> reverse;

	int main()
	{
	int num;
	while (scanf("%d", &num) != EOF)
	{
	while (num--)
	{
	long long number;
	scanf("%lld", &number);
	reverse.push(number);
	}
	while (!reverse.empty())
	{
	printf("%lld ", reverse.top());
	reverse.pop();
	}
	printf("\n");
	}
	return 0;
	}

	5
	-3 4 6 -8 9
	9 -8 6 4 -3

# 括号匹配问题

输出包括两行，第一行输出原始输入字符，第二行由 $ ? 和空格组成， $ ? 分别代表与之对应的左括号和右括号无法匹配。

样例输入

)(rttyy())sss)(

输出

	)(rttyy())sss)(
	? ?$

测试代码

	#include <iostream>
	#include <stack>
	#include <cstdio>
	#include <string>

	using namespace std;

	stack<int> brackets;

	int main()
	{
	string str;
	while (cin >> str)
	{
	string answer(str.size(), ' '); // 设定为输入空格个长度
	for (int i = 0; i < str.size(); ++i)
	{
	if (str[i] == '(')
	{
	brackets.push(i); // 压入左括号的下标
	}
	else if (str[i] == ')')
	{
	if (!brackets.empty())
	{
	brackets.pop();
	}
	else
	{
	answer[i] = '?'; // 右括号不匹配
	}
	}
	}
	while (!brackets.empty())
	{
	answer[brackets.top()] = '$';
	brackets.pop();
	}
	cout << str << endl;
	cout << answer << endl;
	}
	return 0;
	}

	)(rttyy())sss)(
	)(rttyy())sss)(
	? ?$

# 简单计算器

描述
读入一个只包含 +, -, *, / 的非负整数计算表达式，计算该表达式的值。

输入描述
测试输入包含若干测试用例，每个测试用例占一行，每行不超过 200 个字符，整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有 0 时输入结束，相应的结果不要输出。

输出描述
对每个测试用例输出 1 行，即该表达式的值，精确到小数点后 2 位。

输入

	1 + 2
	4 + 2 * 5 - 7 / 11
	0

输出

	3.00
	13.36

测试代码

	#include <iostream>
	#include <stack>
	#include <cstdio>
	#include <string>
	#include <cctype>

	using namespace std;

	stack<char> operation;
	stack<double> data;

	int Priority(char c)
	{
	if (c == '#')
	{
	return 0;
	}
	else if (c == '$')
	{
	return 1;
	}
	else if (c == '+' \|\| c == '-')
	{
	return 2;
	}
	else
	{
	return 3;
	}
	}

	double getNumber(string str, int &index)
	{
	double number = 0;
	while (isdigit(str[index]))
	{
	number = number * 10 + str[index] - '0';
	index++;
	}
	return number;
	}

	double Calculate(double x, double y, char op)
	{
	double result = 0;
	if (op == '+')
	{
	result = x + y;
	}
	else if (op == '-')
	{
	result = x - y;
	}
	else if (op == '*')
	{
	result = x * y;
	}
	else if (op == '/')
	{
	result = x / y;
	}
	return result;
	}

	int main()
	{
	string str;
	while (getline(cin, str))
	{
	if (str == "0")
	{
	break;
	}
	int index = 0;
	str += '$'; // 字符串尾部添加 $
	operation.push('#'); // 运算符栈底添加#
	while (index < str.size())
	{
	if (str[index] == ' ')
	{
	index++;
	}
	else if (isdigit(str[index]))
	{
	data.push(getNumber(str, index));
	}
	else
	{
	if (Priority(operation.top()) < Priority(str[index]))
	{
	operation.push(str[index]);
	index++;
	}
	else
	{
	double y = data.top();
	data.pop();
	double x = data.top();
	data.pop();
	data.push(Calculate(x, y, operation.top()));
	operation.pop();
	}
	}
	}
	printf("%.2f\n", data.top());
	}
	return 0;
	}

	1 + 2
	3.00
	4 + 2 * 5 - 7 / 11
	13.36
	0

# 堆栈的使用

堆栈是一种基本的数据结构。堆栈具有两种基本操作方式， push 和 pop 。其中 push 一个值会将其压入栈顶，而 pop 则会将栈顶的值弹出。现在我们就来验证一下堆栈的使用。

输入描述
对于每组测试数据，第一行是一个正整数 n（0 < n <= 10000） 。而后的 n 行，每行的第一个字符可能是 'P' 或者 'O' 或者 'A' ；如果是 'P' ，后面还会跟着一个整数，表示把这个数据压入堆栈；如果是 'O' ，表示将栈顶的值 pop 出来，如果堆栈中没有元素时，忽略本次操作；如果是 'A' ，表示询问当前栈顶的值，如果当时栈为空，则输出 'E' 。堆栈开始为空。

输出描述
对于每组测试数据，根据其中的命令字符来处理堆栈；并对所有的 'A' 操作，输出当时栈顶的值，每个占据一行，如果当时栈为空，则输出 'E' 。

样例输入

	3
	A
	P 5
	A
	4
	P 3
	P 6
	O
	A

输出

	E
	5
	3

测试代码

	#include <iostream>
	#include <stack>
	#include <cstdio>
	#include <string>

	using namespace std;

	stack<int> myStack;

	int main()
	{
	int n;
	char type;
	int x;
	while (scanf("%d", &n) != EOF)
	{
	if (n == 0)
	{
	break;
	}
	for (int i = 0; i < n; ++i)
	{
	cin >> type;
	if (type == 'A')
	{
	if (myStack.empty())
	{
	cout << "E" << endl;
	}
	else
	{
	cout << myStack.top() << endl;
	}
	}
	else if (type == 'P')
	{
	cin >> x;
	myStack.push(x);
	}
	else if (type == 'O')
	{
	if (!myStack.empty())
	{
	myStack.pop();
	}
	}
	}
	}
	return 0;
	}

	3
	A
	E
	P 5
	A
	5
	4
	P 3
	P 6
	O
	A
	3

CPP 数据结构刷题栈

# 简介

# 栈的应用

# 逆序输出

# 括号匹配问题

# 简单计算器

# 堆栈的使用

队列

2022.6.8