数据结构与栈
一、概念
1. 数据
数据就是电脑可以存储的东西，例如一段文字、图片、视频、音频等等。
计算机系统中，各种字母、数字符号的组合、语音、图形、图像等，统称为数据。
计算机科学中，数据是指所有能输入到计算机并被计算机程序处理的符号总称。
2. 数据结构
数据结构是计算机存储、组织数据的一个方式，是指相互之间存在一种，或多种特定关系的数据元素的集合。
3. 数据结构分类
二、栈
1. 栈
栈是只能在某一端插入和删除的特殊线性表，进行删除和插入的一端称作栈顶，另一端称作栈底。
2. 相关概念
2.1 入栈
又叫压入，把数据装入栈
2.2 出栈
又叫弹出、弹栈，把数据从栈取出
2.3 栈的特点
先进后出，后进先出
2.4 栈顶
允许进出的一端
2.5 栈底
不允许进出的一端
2.6 栈顶元素
最上方的元素，最后入栈的元素
2.7 栈底元素
最下方的元素，最先入栈的元素
三、数组模拟栈
1. 初始化空栈
一个栈可以用定义长度为 n + 1 n+1 n+1 的数组 s [ ] s[] s[] 来表示，该栈存储 n n n 个元素，然后设置指针指向栈顶元素。
const int n = 100;
数据类型 s[n+1];
int top = 0;
2. 入栈
void push(数据类型 x)
{
if (top < n) // 如果栈未满
{
s[++top] = x;
}
// 上溢处理...
}
3. 出栈
void pop()
{
if (top > 0) // 如果不是空栈
{
top--;
}
// 下溢处理...
}
4. 获取栈顶元素
数据类型 getTop()
{
return s[top];
}
5. 判断栈是否为空
bool isEmpty()
{
return (top == 0); // top = 0 时是空栈
}
6. 获取栈内元素个数
int sizeStack()
{
return top;
}
四、栈的运用
1. 括号的匹配
1.1 审题
题目描述
假设一个表达式有英文字母（小写）、运算符（ + + +， − - −， × \times ×， ÷ \div ÷）和左右小（圆）括号构成，以“ @ @ @”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回
“YES”；否则返回“NO”。假设表达式长度小于 255 255 255，左圆括号少于 100 100 100 个。
输入描述
包括一行数据，即表达式
输入文件为bracket.in
输出描述
包括一行，即
“YES”或“NO”
输出文件为bracket.out
样例1
输入
2*(x+y)/((1-x)*2)@输出
YES
1.2 参考答案
#include <iostream>
#include <cstdio>
using namespace std;
char s[105];
char c;
int top;
int main()
{
freopen("bracket.in", "r", stdin);
freopen("bracket.out", "w", stdout);
while (cin >> c)
{
if (c == '@')
{
break;
}
if (c != '(' && c != ')')
{
continue;
}
if (c == '(')
{
s[++top] = c;
}
else
{
if (top == 0)
{
cout << "NO" << endl;
return 0;
}
top--;
}
}
if (top == 0)
{
cout << "YES";
}
else
{
cout << "NO";
}
fclose(stdin);
fclose(stdout);
return 0;
}
2. 括号的匹配 2.0
2.1 审题
题目描述
假设一个表达式有英文字母（小写）、运算符（ + + +， − - −， × \times ×， ÷ \div ÷）和左右小、中（圆）括号构成，以“ @ @ @”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回
“YES”；否则返回“NO”。如果中括号在小括号内，是不合法的。假设表达式长度小于 255 255 255，左圆括号少于 100 100 100 个。
输入描述
包括一行数据，即表达式
输入文件为bracket.in
输出描述
包括一行，即
“YES”或“NO”
输出文件为bracket.out
样例1
输入
2*(x+y)/([1-x])*2)@输出
NO
2.2 参考答案
#include <iostream>
#include <cstdio>
using namespace std;
char s[105];
char c;
int top;
int main()
{
freopen("bracket.in", "r", stdin);
freopen("bracket.out", "w", stdout);
while (cin >> c)
{
if (c == '@')
{
break;
}
if (c == '(')
{
s[++top] = c;
}
else if (c == '[')
{
if (s[top] == '(')
{
cout << "NO";
return 0;
}
else
{
s[++top] = c;
}
}
else if (c == ')')
{
if (s[top] == '(')
{
top--;
}
else
{
cout << "NO";
return 0;
}
}
else if (c == ']')
{
if (s[top] == '[')
{
top--;
}
else
{
cout << "NO";
return 0;
}
}
}
if (top == 0)
{
cout << "YES";
}
else
{
cout << "NO";
}
fclose(stdin);
fclose(stdout);
return 0;
}
3. 括号的匹配 3.0
3.1 审题
题目描述
假设一个表达式有英文字母（小写）、运算符（ + + +， − - −， × \times ×， ÷ \div ÷）和左右小、中、大、尖括号构成，以“ @ @ @”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回
“YES”；否则返回“NO”。合法的括号：{[(<>)]}。假设表达式长度小于 255 255 255，左圆括号少于 100 100 100 个。
输入描述
包括一行数据，即表达式
输入文件为bracket.in
输出描述
包括一行，即
“YES”或“NO”
输出文件为bracket.out
样例1
输入
2*(x+y)/([1-x])*2)@输出
NO
3.2 参考答案
#include <iostream>
#include <cstdio>
using namespace std;
char s[105];
char c;
int top;
int main()
{
freopen("bracket.in", "r", stdin);
freopen("bracket.out", "w", stdout);
while (cin >> c)
{
if (c == '@')
{
break;
}
if (c == '<')
{
s[++top] = c;
}
else if (c == '(')
{
if (s[top] == '<')
{
cout << "NO";
return 0;
}
else
{
s[++top] = c;
}
}
else if (c == '[')
{
if (s[top] == '(' || s[top] == '<')
{
cout << "NO";
return 0;
}
else
{
s[++top] = c;
}
}
else if (c == '{')
{
if (s[top] == '(' || s[top] == '[' || s[top] == '<')
{
cout << "NO";
return 0;
}
else
{
s[++top] = c;
}
}
else if (c == '>')
{
if (s[top] == '<')
{
top--;
}
else
{
cout << "NO";
return 0;
}
}
else if (c == ')')
{
if (s[top] == '(')
{
top--;
}
else
{
cout << "NO";
return 0;
}
}
else if (c == ']')
{
if (s[top] == '[')
{
top--;
}
else
{
cout << "NO";
return 0;
}
}
else if (c == '}')
{
if (s[top] == '{')
{
top--;
}
else
{
cout << "NO";
return 0;
}
}
}
if (top == 0)
{
cout << "YES";
}
else
{
cout << "NO";
}
fclose(stdin);
fclose(stdout);
return 0;
}