4、栈和队列
参考：《大话数据结构》程杰
Paste_Image.png
栈：限定仅在表尾进行插入和删除操作的线性表
队列：只允许在一端进行插入操作，在另一端进行删除操作的线性表
4.1、栈
4.1.1、定义
栈（stack）：限定仅在表尾进行插入和删除的操作的线性表。允许插入和删除的一端称为栈顶（top），另一端称为栈底（buttom），不包含任何数据元素的栈称为空栈。栈是后进先出（Last in First out：LIFO）的线性表。
备注：栈是线性表，栈元素具有线性关系，即前驱和后继关系，只不过是一种特殊的线性表。栈的插入操作：进栈、压栈；栈的删除操作：出栈、弹栈。
Paste_Image.png
4.1.2、抽象数据类型
对于栈，具备线性表的操作特征，针对它操作的变化，将插入和删除，改为push和pop。
ADT 栈(stack)
Data
同线性表，元素具有相同的类型，相邻元素具有前驱和后驱关系
Operation
initStack(*S):初始化操作，建立一个空栈S
DestroyStack(*S):若栈存在，则销毁它
ClearStack(*S):将栈清空
StackEmpty(S):若栈为空，返回TRUE，否则FALSE
GetTop(S, *e):若栈存在且非空，用e返回S的栈顶元素
Push(*S, e):若栈S存在，插入新元素e到栈S中并成为栈顶元素
Pop(*S, *e):删除栈S中栈顶元素，并用e返回其值
StackLength(S):返回栈的元素个数
endADT
4.1.3、栈顺序存储及实现
1、栈的顺序存储结构
栈是线性表的特例，栈的顺序存储其实是线性表顺序存储的简化，简称为顺序栈。若存储栈的长度是StackSize，则栈顶位置top必须小于StackSize。
栈的结构定义：
typedef int SElemType;/*SElemType根据实际情况而定，这里假设为int*/
typedef struct{
SElemType.data[MAXSIZE];
int top; /*用于栈顶指针*/
}SqStack;
Paste_Image.png
2、进栈操作
进栈操作使用push，其代码如下：
Status Push(SqStack *S, SElemType e){
if(S->top == MAXSIZE -1){/*栈满*/
return ERROR;
}
S->top++;
S->data[S->top]=e;
return OK;
}
Paste_Image.png
3、出栈操作
出栈操作使用pop，代码如下：
/*若栈不空，则删除S的栈顶元素，用e返回其值*/
Status Pop(SqStack *S, SElemType *e){
if(S->top== -1)
return ERROR;
*e=S->data[S->top];
S->top--;
return OK;
}
4.1.4、两栈共享空间
数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的开始断，另一个栈为栈的末端，这样，两个栈如果增加元素，就是两栈点向中间延伸。
Paste_Image.png
两栈共享空间的结构如下：
typedef struct{
SElemType data[MAXSIZE];
int top1;/*栈1栈顶指针*/
int top2;/*栈2栈顶指针*/
}SqDoubleStack;
对于两栈共享空间的push方法，除了插入元素外，还需要判断式栈1还是栈2的栈号参数：stackNumber。
Status Push(SqDoubleStack *S, SElemType e, int stackNumber){
if(S->top1+1==S->top2)/*栈已满，不能再push新元素*/
return ERROR;
if(stackNumber == 1)/*栈1有元素进栈*/
S->data[++S->top1]=e;
else if(stackNumber == 2)
S->data[--S->top2]=e;
return OK;
}
对于两栈共享的pop操作，有如下操作：
Status Pop(SqDoubleStack *S, SElemType *e, int stackNumber){
if(stackNumber == 1){
if(S-> top1 == -1)
return ERROR; /*说明栈1是空栈，溢出*/
*e=S->data[S->top1--]; /*将栈1的栈顶元素出栈*/
}
else if(stackNumber == 2){
if(S->top2==MAXSIZE)
return ERROR;/*说明栈2是空栈，溢出*/
*e=S->data[[S->top2++]]; /*将栈2的栈顶元素出栈*/
}
return OK;
}
4.1.5、栈的链式存储结构
栈的链式存储结构，简称为链栈。将栈顶放在单链表的头部，对于栈链，基本不存在满栈的情况，除非内存没有可以使用的空间。链栈的结构代码如下：
typedef struct StackNode{
SElemType data;
struct StackNode *next;
}StackNode, *LinkStackPtr;
typedef struct LinkStack{
LinkStackPtr top;
int count;
}LinkStack
Paste_Image.png
1、进栈操作
对于链栈的进栈push操作，假设元素值为e的新结点是s，top为栈顶指针，示意如下：
/*插入元素e为新的栈顶元素*/
Status Push(LinkStack *S, SElemType e){
LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode));
s->data=e;
s->next=S->top;/*当前栈顶元素赋值给新结点的直接后继*/
S->top=s;
S->count++;
return OK;
}
Paste_Image.png
2、出栈操作
链栈的出栈pop操作，假设p用来存储要删除的栈顶结点，将栈顶指针下移一位，最后释放p即可。
/*若栈不空，则删除S的栈顶元素，用e返回其值*/
Status Pop(LinkStack *S, SElemType *e){
LinkStackPtr p;
if(StackEmpty(*S))
return ERROR;
*e=S->top->data;
p=S->top;/*将栈顶结点赋值给p，图3*/
S->top=S->top->next;/*栈顶指针下移一位，指向后一结点，图4*/
free(p); /*释放结点*/
S->count--;
return OK;
}
Paste_Image.png
3、顺序栈和链栈对比
顺序栈和链栈在时间复杂度上是一样的，均为O(1)，对于空间性能，顺序栈需要事先确定一个固定的长度，可能会造成内存浪费的问题，但是存取时定位方便。而链栈要求每个元素都有指针域，增加一些内存开销。如果栈的使用过程中元素变化不可预料，最好用链栈，反之，则建议使用顺序栈。
栈的引入简化程序设计问题，划分不同的关注层次，使得思考范围缩小，更加聚焦于要解决的核心问题。
4.1.6、栈应用—递归
1、斐波那契数列实现
数学函数定义：
Paste_Image.png
迭代方法如下：
int main(){
int i; int a[40]; a[0]=0; a[1]=1;
for(i=2; i<40;i++){
a[i] = a[i-1] + a[i-2];
}
}
递归代码实现如下所示：
/*斐波那契递归函数*/
int Fbi(int i){
if(i < 2)
return i == 0? 0:1;
return Fbi(i-1)+Fbi(i-2);
}
Paste_Image.png
2、递归定义
递归函数：直接调用自己或通过一系列调用语句间接调用自己的函数，每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回退出。
递归和迭代区别：迭代使用的是循环结构，递归使用的是选择结构，大量递归会建立函数的副本，消耗大量的时间和内存。
4.1.7、栈应用—四则表达式求值
1、后缀表达式
一种不需要括号的后缀表达法，把它称为逆波兰（Reverse Polish Notation，RPN）。
2、中缀表达式
4.2、队列
队列：只允许在一端进行插入操作，在另一端进行删除操作的线性表。队列是先进先出（First In First Out：FIFO）的线性表，允许插入的一端是队尾，允许删除的一端是对头。
Paste_Image.png
4.2.1、抽象数据类型
队列也是线性表，不同的是插入数据从队尾进行，删除数据从队头进行。
ADT 队列(Queue)
Data
同线性表，元素具有相同的类型，相邻元素具有前驱和后继的关系
Operation
InitQueue(*Q):初始化操作，建立一个空队列Q
DestroyQueue(*Q):若队列Q存在，则销毁它
ClearQueue(*Q):将队列Q清空
QueueEmpty(*Q):若队列为空，则返回true，否则返回false
GetHead(Q,*e)：若队列存在且非空，返回队头元素
EnQueue(*Q,e):若队列Q存在，插入新元素e并成为队尾元素
DeQueue(*Q,*e):删除队列Q中队头元素，e返回其值
QueueLength(Q):返回队列Q的元素个数
endDAT
4.2.2、循环队列
线性表有顺序存储和链式存储，栈是线性表，栈也有两种存储方式，队列也是线性表，也具有两种存储方式。
1、队列顺序存储不足
队列的入队列操作，在队尾追加一个元素，不需要移动任何元素，时间复杂度为O(1)。
Paste_Image.png
但是对于出队列操作，需要所有元素都向前移动，保证新队头的下标为0，时间复杂度为O(n)。
Paste_Image.png
2、循环队列实现
循环队列：解决假溢出就是队尾满了，从头开始，头尾相接的循环。
Paste_Image.png
填充元素的过程：
Paste_Image.png
问题：空队列时，front==rear，当队列满时，front==rear，如何进行判断
办法1：设置一个标志变量flag
办法2：当front==rear时，若队列中有元素，则是满队列，若队列取不到元素，则为空
办法3：修改条件，队列空，front==rear，当队列满时，修改条件，保留一个元素空间，即队列满是还有一个空闲存储空间，队列满的条件：（rear+1）%QueueSize == front。
通用计算队列长度的公式为：
（rear-front + QueueSize）%QueueSize
Paste_Image.png
循环队列的顺序存储结构代码：
typedef int QElemType; /*QElemType根据实际情况而定，这里假设int*/
typedef struct{
QElemType data[MAXSIZE];
int front; /*头指针*/
int rear; /*尾指针*/
}SqQueue;
1、初始化空队列
Status InitQueue(SqQueue *Q){
Q->front=0;
Q->rear=0;
return OK;
}
2、求队列的长度
int QueueLength(SqQueue Q){
return(Q.rear - Q.front + MAXSIZE)%MAXSIZE
}
3、入队列操作
Status EnQueue(SqQueue *Q, QElemType e){
if((Q->rear+1)%MAXSIZE == Q->front)/*队列满了*/
return ERROR;
Q->data[Q->rear]=e; /*元素e赋值给队尾*/
Q->rear=(Q->rear+1)%MAXSIZE; /*rear指针向后移一位置*/
return OK;
}
4、出队列操作
Status DeQueue(SqQueue *Q, QElemType *e){
if(Q->front == Q->rear)
return ERROR;
*e=Q->data[Q->front];
Q->front=(Q->front+1)%MAXSIZE;
return OK;
}
4.2.3、队列链式存储实现
队列的链式存储结构，就是线性表的单链表，只是限制了尾进头出，称为链队列。
Paste_Image.png
空队列，front和rear都指向头结点。
Paste_Image.png
链队列的数据结构：
typedef int QElemType /*QElemType根据实际情况而定，这里假设int*/
typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
QueuePtr front,rear;
}LinkQueue;
1、入队操作
Status EnQueue(LinkQueue *Q, QElemType e){
QueuePtr s=(QueuePtr)malloc(sizeof(QNode));
if(!s) /*存储分配失败*/
exit(OVERFlOW)
s->data=e;
s->next=NULL;
Q->rear->next=s;/*把拥有元素e新结点s赋值给原队尾的后继*/
Q->rear=s;
return OK;
}
Paste_Image.png
2、出队操作
头结点的后继结点出队，将头结点的后继改成它后面的结点。若链表除头结点外只剩一个元素，则需将rear指向头结点。
Status DeQueue(LinkQueue *Q, QElemType *e){
QueuePtr p;
if(Q->front == Q->rear)
return rear;
p=Q->front->next;/*将想要删除的队头结点暂时存给p*/
*e=p->data;
Q->front->next=p->next;
if(Q->rear==p)
Q->rear=Q->front;
free(p);
return OK;
}
Paste_Image.png
