栈和队列
1，栈(stack)
栈是限定仅在表尾进行插入或者删除操作的线性表
栈 :线性表
->
一对一的关系
-》
数组
链表
栈是有限制的线性表(阉割版的线性表)
栈更重要的是一种思想
先进后出，后进先出
在程序设计或算法中，会经常用到这种思想
“撸串”
“死胡同堵车”
“压子弹”
栈顶(top)：进行插入或者删除的那一端
栈尾(bottom)：不允许进行插入或者删除的一端
栈的基本操作：
类型的实现
数组
链表
操作的实现
常用的操作
initStack：初始化栈
clearStack :清空栈 -》把栈的所有元素都干掉
destroyStack:销毁一个栈
pop:出栈
push:入栈(压栈)
不是很常用的操作
getTop:获取栈顶元素，但是不出栈
stackIsEmtpy:判断栈是否为空
stackLength:栈的长度
（1）顺序栈：用顺序结构的线性表来实现栈
顺序结构的线性表 -》 数组
栈顶和栈尾分别对应数组的哪一端比较好？
栈顶是经常要进行插入或者删除的，那么怎么方便你就怎么选
经过分析：选择a[n-1]这端做完栈顶，a[0]端作为栈尾
-》
typedef int ElemType;//栈元素的类型
#define MAX_ELEM_NUM 100
struct sqStack
{
ElemType stack[MAX_ELEM_NUM];//用来保存数据
int top;//栈顶元素在stack中的下标
}
typedef struct sqStack STACK;
（2）链式栈：用链式的线性表来实现栈
链式的线性表 -> 链表
typedef int ElemType;
struct node //定义了一个新的类型，叫做 struct node
{
ElemType data;//存储数据 -》数据域
struct node * next;//存储下一个元素的地址，因为下一个
//元素和当前元素是一个类型，所以他的类型是
//struct node * next ->指针域
};
typedef struct node NODE;//给struct node取一个别名NODE
struct stack //<-这是我们声明的新类型 “头结点”
{
//这个头结点的成员变量，不是确定的，是按你的需求增加
//你觉得这个链表中，哪些信息对你比较重要或者经常用到
//你就保存它
int nodeNum;//用来保存链表中的节点的个数
NODE * first;//指向栈顶元素
NODE * last;//指向栈尾元素
//.......按需增加
};
typedef struct stack STACK;
first和last哪端作为栈顶比较好？
对于插入而言：头插和尾插都很方便
对于删除而言：删除first和删除last哪个方便？
删除first比较简单
->
采用first作为栈的栈顶
作业：
输入一个整数，然后倒序输出这个整数的各位数字，用栈实现
12345
->
5 4 3 2 1
设输入序列1、2、3、4，则下述序列中（）不可能是出栈序列。
A. 1、2、3、4 B. 4、 3、2、1
C. 1、3、4、2 D.４、1、2、3
1、若入栈序列是 a, b, c, d, e，则不可能的出栈序列是（）。
（A） edcba（B）decba（C）dceab （D）abcde
2， 队列
队列(Queue)是一种先进先出，后进后出的线性表。
它只允许在表的一端进行插入，在另一端进行删除。
队尾：允许插入的一端叫做队尾
对头：允许删除的一端叫队头
“排队”
队列更重要的是一种思想，“先进先出”
队列的实现
队列类型的实现
(1)顺序队列：用顺序结构的线性表来实现队列
“环形数组”
开辟一段连续的地址空间用来保存队列中的每一个元素 Q[]
定义两个变量，保存两个重要的信息：
1，d ：队头元素的下标（打饭的阿姨的位置）
2，e : 下一个入队元素的下标
(下一位打饭的同学要加入的位置，其实就是当前队列队尾的下一个)
typedef int ElemType;//队列元素的类型
#define QUEUE_MAX_NUM 100
typedef struct SqQueue
{
ElemType queue[QUEUE_MAX_NUM];
int d;//队头下标
int e;//下一个队尾的下标
int num;//队列中元素的个数(当前排队的人数)
}SqQueue;
(2)链式队列：用链式结构的线性表来实现队列
链表
"带头结点的单向链表"
typedef int ElemType;//队列的元素
struct node
{
ElemType data;
struct node * next;
}
typedef struct node NODE;
typedef struct LkQueue
{
NODE * first;//指向队头元素
NODE * last;//指向队尾
int num;//队列中元素的个数
}LkQueue;
first指向队头，last指向队尾。因为队头要删除节点，作为单向链表而言，last作为对头的话，极不方便
设计好，实现起来就会轻松
设计不好，很麻烦
操作的实现
initQueue：初始化队列
clearQueue:清空一个队列
destroyQueue:销毁一个队列
EnQueue:入队
DeQueue:出队
getHead:返回队头元素
queueIsEmpty:是否为空
queueLength:返回队列元素的个数，即队列的长度
-----------------------------------------------------------
我们知道，线性表(链表，栈和队列)，都是一个具有相同属性的数据
的集合。
集合中的元素：必须要是同一类型的？是的
那如果我需要用线性表保存不同类型的集合，是不是
就得写多份代码
现在一个项目中，既需要用到保存Int型数据的链表
又需要用到保存char型数据的链表
还需要用到保存double型数据的链表
也就是说需要三个或者多个不同类型的链表
那么是不是得把同一个代码写多份，才能满足
int double char ......
共同点？
我们可以保存他们的地址，因为他们的地址都是四个字节
作业：
求表达式的值
表达式是以字符串的形式输入
如：
char a[100] = "3+2*8-4*3+5-6+7/2+10-5";
//不考虑括号，运算符只考虑 ，所有的操作数都是int
1，创建两个栈s1 ,s2
s1 存操作数的栈
s2 存运算符的栈
2，按照要求把这个表达式的操作数和运算符入栈
flag 第一个操作数和第一个运算符直接入栈
后面的操作数x怎么处理呢？分两种情况
s2的栈顶元素c2与x的后面的运算符c1做比较(比较优先级)
如果c2<c1 :x直接入栈
如果c2>=c1：则计算 y c2 x的值 -》当做新的x
(y是s1的出栈元素,c2是s2的出栈元素,y和c2都需要出栈)
goto flag (循环什么时候结束？字符串入栈完毕)
3，把s1,s2出栈
进行运算 -》结果