数据结构基础—栈和队列
一、栈和队列的基本概念和性质
栈和队列都是特殊的线性表
对他们的操作有着规定和限制：在插入和删除时只能对某一端操作
- 栈：只能在一端进行(先进后出)
- 队列：只能在表尾插入，在表头删除(先进先出）
二、栈
表头为栈底，表尾为栈顶
1.栈的基本操作和规则
a.进栈和出栈
- 进栈：栈顶则成为进栈的数据(插入)。如果是顺序表，则一定要进行判满
- 出栈：将当前栈顶移出(删除)，不管什么存储类型，一定要判空
b.进栈、出栈前后的次序
一个数的出栈可以在另一个数进栈前出，但不可以在另一个数进栈后，在这个数(另一个进栈的数)前出。
当一个数进栈后，若它前面有数，则在出栈时它前面的所有数的排列都是入栈的逆序。
举个栗子：若进栈顺序为1 2 3，则，出栈时，不可能是那种排列？
答案：不可能是 3 1 2，为什么呢？
咱们一个一个分析，之前说过，一个数的出栈可以在另一个数入栈之前
- 1进，2进前1出，2进，3进前2出，3进3出 ： 1 2 3
- 1进，2进前1出，2进，3进，3出2出 ：1 3 2
- 1进，2进，3进前2出，1出 ，3进3出 ：2 1 3
- 1进，2进，3进前2出，3进，3出1出 ：2 3 1
- 1进，2进，3进，3出2出1出 ：3 2 1
所以不可能出现 3 1 2 的排列的，即，若3前面有数，则出栈后3后的顺序一定是1 2 的逆序(和上面对应)
C.栈的类型
根据存储结构的不同分为顺序栈(顺序存储)和链栈(链式存储)，在这里主要是研究顺序栈(链栈和链表差不多...)
d.顺序栈的一些基本操作
//是否为空
S.base == S.top;
//是否已满
S.top - S.base =>len;
//栈不存在
S.base = NULL;
/*类型自己转换吧*/
//栈的基本结构
typedef struct Stack{
char *base;
char *top;
int Size;
}SqStack;
//创建空栈
void InitStack(SqStack &S){
S.base = (char *)malloc(MaxSize*sizeof(char));//开辟空间
if(!S.base) cout << "创建失败\n";
S.top = S.base; //栈空的条件
S.Size = MaxSize;
cout << "空栈创建成功\n";
}
//进栈
void Push(SqStack &S,char e){
if((S.top-S.base) >=MaxSize){ //判满
S.base = (char *)malloc(S.base,(MaxSize+ADD)*sizeof(char));
if(!S.base) cout << "创建失败\n";
S.top = S.base+MaxSize;
S.Size = S.Size+ADD;
}else{
*S.top++ = e;
}
}
//出栈，获取出栈元素
char Pop(SqStack &S){
char e;
if(S.top == S.base) cout << "栈空";
e = *--S.top;
return e;
}
//输出栈的元素
void Get(SqStack &S){
for(int i = 0;S.base != S.top-i;i++){
cout << *(S.base+i);
}
}
2.栈在计算机的多种实现形式
3.栈的案例分析
表达式的求值(表达式最后添加一个"#")
相关知识：
- 前缀式：+ * ab * - c / def
- 中缀式：a * b+ (c - d / e) * f
- 后缀式：ab * cde / - f * +
- 后缀式
思路：将我们常见的中缀式先转化成后缀式，在根据后缀式来进行计算
- 中缀式->后缀式(利用运算符的优先级)
- 先建立一个后缀式栈(1栈)来放最后生成的后缀式，在建立一个运算符栈(2栈)，栈底为"#"来判断各个运算符之间的关系
- 遍历输入的表达式
- 若判断 1栈为空直接入1栈，否则判断是否是操作数(a,b,c...)，是，则也直接入1栈
- 若当前为运算符，则与2栈的的栈顶的运算符比较优先级，若有先级高与栈底，则入2栈；若低于或等于，则将栈顶的运算符出2栈，进1栈，再将当前栈顶与之比较直到优先级最高为止
- 若遇到"()","("直接如2栈，")"将"("前所有的运算符出2栈，进1栈。并将"("出2栈
- 最后遍历到 "#"时，运算符依次出2栈，直到2栈栈顶为"#"
- 转换完成
- 后缀式求值
- 再建立一个操作栈(3栈)，用来暂时存放计算过程和最终显示结果
- 遍历1栈
- 若遍历到的1栈元素为数字，则，入3栈
- 若若遍历到的1栈元素为运算符，则，将3栈中的后两个元素出栈，与该运算符进行正常运算，结果再入3栈
- 如此反复，直到"#"位置
- 输出3栈的栈顶(也就这一个元素)即可完成计算
具体的代码有点多了，大家想看就看看吧...
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
using namespace std;
#define MaxSize 100
#define ADD 10
#define M 20
typedef struct Stack{
char *base;
char *top;
int Size;
}SqStack;
typedef struct stack{
int *base;
int *top;
int Size;
}intStack;
//创建一个空的栈1,2
void InitStack(SqStack &S){
S.base = (char *)malloc(MaxSize*sizeof(char));//开辟空间
if(!S.base) cout << "创建失败\n";
S.top = S.base; //栈空的条件
S.Size = MaxSize;
cout << "空栈创建成功\n";
}
//创建一个空的栈3
void Initstack(intStack &S){
S.base = (int *)malloc(MaxSize*sizeof(int));//开辟空间
if(!S.base) cout << "创建失败\n";
S.top = S.base; //栈空的条件
S.Size = MaxSize;
cout << "空栈创建成功\n";
}
//进栈 1,2
void Push(SqStack &S,char e){
if((S.top-S.base) >=MaxSize){
S.base = (char *)malloc((MaxSi