数据元素(Data Element) ：
是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。
数据结构(data structure)
是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简而言之，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。
数据元素的物理结构有两种：顺序存储结构和链式存储结构
顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
逻辑上关联的数据元素，物理存储结构中相邻。
链式存储结构：在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。
逻辑上关联的数据元素，物理存储结构中不一定相邻
数据结构上的基本操作
插入
删除
更新
查找
排序(线性结构)
遍历
接下来我们了解一下一种基本的数据结构——线性表。定义：n个数据元素的的有限序列其特点是除了表头和表尾外，表中的每一个元素有且仅有唯一的前驱和唯一的后继，表头有且只有一个后继，表尾有且只有一个前驱。而今天要学习的栈和队列正是两种特殊的线性表。
栈是只能在某一端插入和删除的特殊线性表，进行删除和插入的一端称栈顶，另一堆称栈底。插入一般称为进栈（PUSH），删除则称为退栈（POP）。 栈也称为后进先出表（LIFO表）。
一个栈可以用定长为Ｎ的数组Ｓ来表示，用一个栈指针TOP指向栈顶。若TOP＝0，表示栈空，TOP=N时栈满。进栈时TOP加１。退栈时TOP减１。当TOP<1、进栈（PUSH）算法
①若TOP≥ｎ时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）；
②TOP++（栈指针加１，指向进栈地址）；
③S[TOP]=X，结束（X为新进栈的元素）；
2、退栈（POP）算法
①若TOP≤0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈， 空则下溢；不空则作②)；
②X=S[TOP]，（退栈后的元素赋给X）；
③TOP–，结束（栈指针减１，指向栈顶）。
0时为下溢。栈指针在运算中永远指向栈顶。
1、进栈（PUSH）算法
①若TOP≥ｎ时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）；
②TOP++（栈指针加１，指向进栈地址）；
③S[TOP]=X，结束（X为新进栈的元素）；
2、退栈（POP）算法
①若TOP≤0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈， 空则下溢；不空则作②)；
②X=S[TOP]，（退栈后的元素赋给X）；
③TOP–，结束（栈指针减１，指向栈顶）。
代码：
#include<cstdlib>
#include<iostream>
using namespace std;
#define size 100
int a[size+1],n,d,i=0,j;
main()
{
cout<<"Please enter a number(N) base 10:"; cin>>n;
cout<<"please enter a number(d):"; cin>>d;
do{
a[++i]=n%d;
n=n/d;
}while(n!=0);
for (j=i;j>=1;j--)cout<<a[j];
return 0;
}
【例1】括号的匹配（表达式的合法性检查）
http://ybt.ssoier.cn:8088/problem_show.php?pid=1353
https://www.luogu.com.cn/problem/P1739
【问题描述】
假设一个表达式有英文字母（小写）、运算符（+，—，*，/）和左右小（圆）括号构成，以“@”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“YES”；否则返回“NO”。假设表达式长度小于255，左圆括号少于20个。
【算法分析】
读到左括号进栈，读到右括号，栈顶元素出栈。
不能匹配的情况：
匹配完所有的右括号之后，栈不空(存在多余的左括号)；
读到右括号，需要栈顶元素出栈时，栈是空的(右括号数量超过左括号)
#include<cstdio>
#include<cstdlib>
using namespace std;
char c[256];
bool judge(char c[256])
{
int top=0,i=0;
while (c[i]!='@')
{
if (c[i]=='(') top++;
if (c[i]==')')
{
if (top>0) top--;
else return 0;
}
i++;
}
if (top!=0) return 0; //检测栈是否为空。不空则说明有未匹配的括号
else return 1;
}
main()
{
scanf("%s",c);
if (judge(c))printf("YES");
else printf("NO");
return 0;
}
【例2】编程求一个后缀表达式的值http://ybt.ssoier.cn:8088/problem_show.php?pid=1331
【问题描述】
从键盘读入一个后缀表达式（字符串），只含有0-9组成的运算数及加（+）、减（—）、乘（*）、除（/）四种运算符。每个运算数之间用一个空格隔开，不需要判断给你的表达式是否合法。以@作为结束标志。
【算法分析】
后缀表达式的处理过程很简单，过程如下：扫描后缀表达式，凡遇操作数则将之压进堆栈，遇运算符则从堆栈中弹出两个操作数进行该运算，将运算结果压栈，然后继续扫描，直到后缀表达式被扫描完毕为止，此时栈底元素即为该后缀表达式的值。
代码：
#include <bits/stdc++.h>
using namespace std;long long stack1[257]; char s[256];
long long comp(char s[])//函数
{
long long i=0,top=0,x,y;
while(s[i]!='@')
{
switch(s[i])
{
case'+':stack1[--top]+=stack1[top+1];break;
case'-':stack1[--top]-=stack1[top+1];break;
case'*':stack1[--top]*=stack1[top+1];break;
case'/':stack1[--top]/=stack1[top+1];break;
default:x=0;while(s[i]!=' ') x=x*10+s[i++]-'0'; stack1[++top]=x;
}
i++;//找下一个
}
return stack1[top];//返回最后的值
}
int main()
{
cin.getline(s,256);
cout<<comp(s);
return 0;
}
【例3】车厢调度http://ybt.ssoier.cn:8088/problem_show.php?pid=1357
【问题描述】
有一个火车站，铁路如图所示，每辆火车从A驶入，再从B方向驶出，同时它的车厢可以重新组合。假设从A方向驶来的火车有n节（n<=1000），分别按照顺序编号为1，2，3，…，n。假定在进入车站前，每节车厢之间都不是连着的，并且它们可以自行移动到B处的铁轨上。另外假定车站C可以停放任意多节车厢。但是一旦进入车站C，它就不能再回到A方向的铁轨上了，并且一旦当它进入B方向的铁轨，它就不能再回到车站C。
负责车厢调度的工作人员需要知道能否使它以a1,a2,…,an的顺序从B方向驶出，请来判断能否得到指定的车厢顺序。
【输入】
输入文件的第一行为一个整数n，其中n<=1000，表示有n节车厢，第二行为n个数字，表示指定的车厢顺序。
【输出】
如果可以得到指定的车厢顺序，则输出一个字符串”YES”，否则输出”NO”（注意要大写，不包含引号）。
【输入样例】
5
5 4 3 2 1
【输出样例】
YES
分析：
该题就是前面思考题的一部分。车站C相当于一个栈。我们用模拟法来做，假设我们已经处理了前i-1节从B方向驶出的车厢，我们现在要让ai驶出。若ai不在车站C中，我们就让若干车厢从A方向驶入车站C，直到ai驶入，再将它从B方向驶出；若ai在车站C中，如果它是车站C中停在最前面的，则将它从B方向驶出，否则原问题无解。
如样例中，出栈序列是3 5 4 2 1，模拟过程如下：
①一开始栈为空
②由于3不在栈中，就需要把1,2,3依次进栈，再出栈，这样符合出栈序列第一个数是3，当前栈为{1,2}
③第2个出栈的是5,5不在栈中，则就把4,5压栈，再出栈就可以得到5，此时栈为{1,2，4}
④第3个出栈的是4，正好是栈顶元素，直接出栈，栈变为{1,2}
⑤第4个出栈的是2，正好是栈顶元素，直接出栈，栈变为{2}
⑥第5个出栈的是1，正好是栈顶元素，直接出栈，栈变为{}
在模拟过程中没有碰到要出栈的数在栈中但不是栈顶元素的情况，所以该方案可行。
【参考程序】
#include <bits/stdc++.h>
using namespace std; const int N = 1010;
int stack1[N],a[N]; int top,n;
int main()
{ cin >> n;
for (int i = 1;i <= n;++ i)
cin >> a[i];
top = 0;
for (int i = 1,cur = 1;i <= n;++ i) //cur为当前要从A方向驶入的车厢号
{
while (cur <= a[i])
stack1[++ top] = cur ++;
if (stack1[top] == a[i])
-- top;
else
{ cout << "NO" << endl; return 0;
}
}
cout << "YES" << endl;
return 0;
}
【例5】中缀表达式值【问题描述】
http://ybt.ssoier.cn:8088/problem_show.php?pid=1358
输入一个中缀表达式（由0-9组成的运算数、加+减—乘*除/四种运算符、左右小括号组成。注意“-”也可作为负数的标志，表达式以“@”作为结束符），判断表达式是否合法，如果不合法，请输出“NO”；否则请求出表达式的值并输出。
【输入文件】
输入文件的第一行为一个以@结束的字符串。
【输出文件】
如果表达式不合法，请输出“NO”，要求大写。
如果表达式合法，请输出计算结果。
【输入样例】
1＋2×8-9
【输出样例】
8
代码：
#include <bits/stdc++.h>
using namespace std;
int t1,t2,n,x,flag,r[205],s1[1010];
char a[1010],b[1010],s2[1010];
inline void out(char c) {
if(c=='+') s1[--t1]+=s1[t1+1];
else if(c=='-') s1[--t1]-=s1[t1+1];
else if(c=='*') s1[--t1]*=s1[t1+1];
else if(c=='/') s1[--t1]/=s1[t1+1];
}
bool check(char str[],int len) { // 检查表达式是否合法
if (r[str[0]]>0) return false ; // 开头有一个运算符的情况
for (int i = 1; i < len; i ++) { // 连续两个运算符的情况
if (r[str[i]]&& r[str[i-1]]) return false;
}
int sum = 0;
for (int i = 0; i < len; i ++) { // 判断括号是否匹配
if (str[i] == '(') sum ++;
else if (str[i] == ')')
{ sum --; if (sum<0) return 0; }
} return sum == 0;
}
int main() {
cin>>b; int j=0;
for(int i = 0; i <= strlen(b); ++i)
{
if((i == 0 ||b[i-1] == '(')&& b[i] == '-')
a[j++] = '0';//负号前面加0
a[j++] = b[i];
}
r['+']=1,r['-']=1; r['*']=2,r['/']=2;
if (!check(a,strlen(a))) // 表达式不合法
{ cout << "NO" << endl;return 0; }
for (int i = 0; i < strlen(a); i ++)
if (a[i] == '@') {a[i]=')'; x=i;}
int i=0;s2[++t2]='(';
while(i<=x) {
if(a[i]>='0'&&a[i]<='9') {
int x=0;
while(a[i]>='0'&&a[i]<='9')
{ x=x*10+a[i]-'0'; i++; }
s1[++t1]=x;
}
if(a[i]=='(') s2[++t2]='(';
if(a[i]==')') {
while(s2[t2]!='('&&t2>0)
out(s2[t2--]);
t2--;
}
if(r[a[i]]) {
while(r[a[i]]<=r[s2[t2]])
out(s2[t2--]);
s2[++t2]=a[i];
}
i++;
}
printf("%d",s1[t1]);
return 0;
}
