栈与列队
- 栈是限定仅在表尾进行插入和删除操作的线性表
- 队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表
栈的定义
栈（stack）是限定仅在表尾进行插入和删除操作的线性表
允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈。栈又称为后进先出（LastIn First Out）的线性表，简称LIFO结构
栈的插入操作，叫作进栈，也称压栈、入栈，如下图所示：
栈的删除操作，叫作出栈，也有的叫作弹栈，如下图所示：
栈的抽象数据类型
对于栈来讲，理论上线性表的操作特性它都具备，可由于它的特殊性，所以针对它在操作上会有些变化，特别是插入和删除，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); 返回栈S的元素个数。
endADT
由于栈本身就是一个线性表，所以同样具有线性表的顺序存储结构和链式存储结构
栈的顺序存储结构
既然栈是线性表的特例，那么栈的顺序存储其实也是线性表顺序存储的简化，我们简称为顺序栈。线性表是用数组来实现的，那么想想看，对于栈这种只能一头插入、删除的线性表来说，用数组哪一端作为栈顶和栈底比较好？
通常使用下标为0的一端作为栈底，因为首元素都存在栈底，变化最小，所以让它作为栈底。定义一个top变量来指示栈顶元素在数组中的位置，若存储栈的长度为StackSize，则栈顶位置top必须小于StackSize。当栈存在一个元素时，top等于0，通常把空栈的判定条件定为top等于−1
栈的结构定义
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */
typedef struct
{
SElemType data[MAXSIZE];
int top; /* 用于栈顶指针 */
}SqStack;
若现在有一个栈，StackSize是5，则栈普通情况、空栈和栈满的情况示意图如下：
进栈操作
栈的插入，即入栈操作，入下图：
入栈操作Push
/* 插入元素e为新的栈顶元素 */
Status Push(SqStack *S,SElemType e)
{
if(S->top == MAXSIZE -1) /* 栈满 */
{
return ERROR;
}
S->top++; /* 栈顶指针增加一 */
S->data[S->top]=e; /* 将新插入元素赋值给栈顶空间 */
return OK;
}
出栈操作
出栈操作Pop
/* 若栈不空，则删除S的栈顶元素，用e返回其值， 并返回OK；否则返回ERROR */
Status Pop(SqStack *S, SElemType *e)
{
if (S->top == -1) // 栈空
return ERROR;
*e = S->data[S->top]; /* 将要删除的栈顶元素赋值给e */
S->top--; /* 栈顶指针减一 */
return OK;
}
两栈共享空间
其实栈的顺序存储还是很方便的，因为它只允许栈顶进出元素，所以不存在线性表插入和删除需要移动元素的问题，但是也存在一个缺陷，就是必须先确定数组存储空间大小，万一不够用，就需要使用编程手段进行扩容，很麻烦。
用一个数组来存储两个栈，数组有两个端点，两个栈有两个栈底，让一个栈的栈底为数组的始端，即下标为0处，另一个栈为数组的末端，即下标为数组长度n-1处。两个栈如果增加元素，就是两端点向中间延伸
关键思路：它们是在数组的两端，向中间靠拢，top1和top2是栈1和栈2的栈顶指针，只要它们俩不见面，两个栈就可以一直使用。
当栈1为空时，top1等于-1；当栈2为空时，top2等于n。若栈2是空栈，栈1的top1等于n-1时，就是栈1满了。反之，当栈1为空，top2等于0时，栈2满。但是更多数情况下是两个栈见面之时，也就是两个指针相差1，即top1+1=top2为栈满
两栈共享空间
/*两栈共享空间结构 */
typedef struct
{
SElemType data[MAXSIZE];
int top1; /* 栈1栈顶指针 */
int top2; /* 栈2栈顶指针 */
} SqDoubleStack;
对于两栈共享空间的push方法，除了要插入元素值参数外，还需要有一个判断是栈1还是栈2的栈号参数stackNumber。
插入元素
/* 插入元素e为新的栈顶元素 */
Status Push(SqDoubleStack *S, SElemType e, int stackNumber)
{
/* 栈已满，不能再push新元素了 */
if (S->top1 + 1 == S->top2)
return ERROR;
/* 栈1有元素进栈 */
if (stackNumber == 1)
/* 若栈1则先top1+1后给数组元素赋值 */
S->data[++S->top1] = e;
/* 栈2有元素进栈 */
else if (stackNumber == 2)
/* 若栈2则先top2-1后给数组元素赋值 */
S->data[--S->top2] = e;
return OK;
}
因为开始我们就已经判断了是否有栈满的情况，所以后面的top1+1和top2-1是不需要担心溢出问题的。
弹出元素
两栈共享空间的pop方法，判断栈1栈2的参数stackNumber即可
/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
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;
}
使用这样的数据结构，通常都是两个栈的空间需求有相反关系时，也就是一个栈增长另外一个栈缩短的情况。这样使用两栈共享空间存储方法才有较大的意义，否则两个栈都在不停的增长，那么很快就会因栈满而溢出。
栈的链式存储结构
栈的链式存储结构，简称为链栈
由于单链表有头指针，而栈顶指针也是必须的，所以比较好的办法是把栈顶放在单链表的头部。另外，都已经有了栈顶在头部了，单链表中比较常用的头结点也就失去了意义，通常对于链栈来说，是不需要头结点的。
对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间，如果真的发生，那此时的计算机操作系统已经面临死机崩溃的情况，而不是这个链栈是否溢出的问题。但对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是top=NULL的时候。
链栈的结构
/* 链栈结构 */
typedef struct StackNode
{
SElemType data;
struct StackNode *next;
} StackNode,*LinkStackPtr;
typedef struct LinkStack
{
LinkStackPtr top;
int count;
} LinkStack;
栈的链式存储结构——进栈操作
对于链栈的进栈push操作，假设元素值为e的新结点是s，top为栈顶指针，如下图
/* 插入元素e为新的栈顶元素 */
Status Push(LinkStack *S,SElemType e)
{
LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode));
s->data=e;
s->next=S->top; /* 把当前的栈顶元素赋值给新结点的直接后继，见图中1 */
S->top=s; /* 将新的结点s赋值给栈顶指针，见图中2 */
S->count++;
return OK;
}
栈的链式存储结构——出栈操作
假设变量p用来存储要删除的栈顶结点，将栈顶指针下移一位，最后释放p即可
/* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
Status Pop(LinkStack *S,SElemType *e)
{
LinkStackPtr p;
if(StackEmpty(*S))
return ERROR;
*e=S->top->data;
p=S->top; /* 将栈顶结点赋值给p，见图中③ */
S->top=S->top->next; /* 使得栈顶指针下移一位，指向后一结点，见图中④ */
free(p); /* 释放结点p */
S->count--;
return OK;
}
链栈的进栈push和出栈pop没有任何循环操作，时间复杂度均为O(1)。
顺序栈与链栈对比
1、它们时间复杂度上均为O(1)。
2、对于空间性能，顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的问题，但它的优势是存取时定位很方便，而链栈则要求每个元素都有指针域，这同时也增加了一些内存开销，但对于栈的长度无限制
3、如果栈的使用过程中元素变化不可预料，有时很小，有时非常大，那么最好是用链栈，如果它的变化在可控范围内，建议使用顺序栈
栈的作用
栈的引入简化了程序设计的问题，划分了不同关注层次，使得思考范围缩小，更加聚焦于要解决的问题核心。反之，像数组等，因为要分散精力去考虑数组的下标增减等细节问题，反而掩盖了问题的本质。
对于一些高级的语言，比如：Java,OC等都有对栈结构的封装，可以不需要关注它的实现细节，就可以直接使用stack的push和pop方法，非常方便。
栈的应用-递归
栈有一个很重要的应用：在程序设计语言中实现了递归。递归中的一个结点例子：斐波那契数列。
斐波那契数列实现
如果兔子在出生两个月后就有繁殖能力，一对兔子每个月能生出一对小兔子。假设所有的兔都不死，那么一年后可以繁殖多少对兔子？
分析
第一个月兔子没有繁殖能力，所以还是一对；第二个月也还是一对，两个月后，生下一对兔子，小兔子总数为2；三个月后，老兔子又生下一对，因为小兔子目前还没有繁殖能力，所以现在为3对兔子，这样一次类推，如下图：
表中数字1，1，2，3，5，8，13...构成了一个序列，而且又明显的特点：前面相邻两项只和构成后一项
编号①的一对兔子经过六个月就变成8对兔子，数学函数来定义就是：
打印出前40位的斐波那契数列数。
#include "stdio.h"
int Fbi(int i) /* 斐波那契的递归函数 */
{
if( i < 2 )
return i == 0 ? 0 : 1;
return Fbi(i - 1) + Fbi(i - 2); /* 这里Fbi就是函数自己，等于在调用自己 */
}
int main()
{
int i;
int a[40];
printf("迭代显示斐波那契数列：\n");
a[0]=0;
a[1]=1;
printf("%d ",a[0]);
printf("%d ",a[1]);
for(i = 2;i < 40;i++)
{
a[i] = a[i-1] + a[i-2];
printf("%d ",a[i]);
}
printf("\n");
printf("递归显示斐波那契数列：\n");
for(i = 0;i < 40;i++)
printf("%d ", Fbi(i));
return 0;
}
递归定义
把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数。当然，写递归程序最怕的就是陷入永不结束的无穷递归中，所以，每个递归定义必须至少有一个条件，满足时递归不再进行。
| 迭代 | 递归 |
|---|---|
| 循环结构 | 选择结构 |
| 不需要反复调用函数和占用额外的内存 | 使程序的结构更清晰、更简洁、更容易让人理解，从而减少读懂代码的时间。但是大量的递归调用会建立函数的副本，会耗费大量的时间和内存 |
在前行阶段，对于每一层递归，函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段，位于栈顶的局部变量、参数值和返回地址被弹出，用于返回调用层次中执行代码的其余部分，也就是恢复了调用的状态
队列的定义
队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表
队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。假设队列是q=(a1，a2，...，an)，那么那么a1就是队头元素，而an是队尾元素。删除时，总是从a1开始，而插入时，列在最后。
队列的抽象数据类型
ADT 队列(Queue)
Data
同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系。
Operation
InitQueue(*Q): 初始化操作，建立一个空队列Q。
DestroyQueue(*Q): 若队列Q存在，则销毁它。
ClearQueue(*Q): 将队列Q清空。
QueueEmpty(Q): 若队列Q为空，返回true，否则返回false。
GetHead(Q, *e): 若队列Q存在且非空，用e返回队列Q的队头元素。
EnQueue(*Q, e): 若队列Q存在，插入新元素e到队列Q中并成为队尾元素。
DeQueue(*Q, *e): 删除队列Q中队头元素，并用e返回其值。
QueueLength(Q): 返回队列Q的元素个数
endADT
循环队列
线性表有顺序存储和链式存储，栈式线性表，所以有这两种存储方式，同样，列队作为一种特殊的线性表，也同样存在这两种存储方式。先看列队的顺序存储结构。
队列顺序存储的不足
假设一个队列有n个元素，则顺序存储的队列需建立一个大于n的数组，并把队列的所有元素存储在数组的前n个单元，数组下标为0的一端即是队头。所谓的入队列操作就是在队尾追加一个元素，不需要移动任何元素，时间复杂度为O(1)，如下图：
与栈不同的是，队列元素的出列是在队头，即下标为0的位置，队列中的所有元素都得向前移动，以保证队列的队头，也就是下标为0的位置不为空，此时时间复杂度为O(n)，如下图：
可细想一下，为什么出列队时一定要移动全部元素？如果不去限制列队的元素必须存储在数组的前n个单元这一条件，那么出队的性能就会大大增加，也就是说，队头不需要一定在下标为0的位置。
为了避免当只有一个元素时，队头和队尾重合使处理变得麻烦，所以引入两个指针，front指针指向队头元素，rear指针指向队尾元素的下一个位置，当front等于rear时，此队列不是还剩一个元素，而是空队列。
假设是长度为5的数组，初始状态，front与rear指针均指向下标为0的位置。然后入队a1、a2、a3、a4，front指针依然指向下标为0位置，而rear指针指向下标为4的位置
出队a1,a2，front指针指向下标为2的位置，rear不变，再入队a5，front指针不变，rear指针移动到数组之外，如下图
而且问题还不止如此，假设这个列队的总个数不超过5个，但是目前继续接着入队，因为数组末尾元素已经被占用，再向后加，就会产生数组越界。而实际上，我们列队的下标0和1的地方还是空闲，这是一种“假溢出”。
循环队列定义
为了解决假溢出问题，当后面满了，就再从头开始，也就是头尾相接的循环。队列的这种头尾相接的顺序存储结构称为循环队列。
继续上面的例子，rear可以改为指向下标为0的位置，这样就不会造成指针指向不明的问题，如下图：
接着入队a6，将它放置于下标为0处，rear指针指向下标为1处，如左图。再入队a7，则rear指针就与front指针重合，同时指向下标为2的位置，如下图
此时问题又来了，因为空列队的时候front等于rear，现在当列队满了，也是front等于rear，那么如何判断此时的队列究竟是空还是满呢？
办法一：设置一个标志变量flag，当front==rear，且flag=0时为队列空，当front==rear，且flag=1时为队列满。
办法二：当队列空时，条件就是front=rear，当队列满时，保留一个元素空间，如下图。也就是说，队列满时，数组中还有一个空闲单元，就认为此队列已经满了，即不允许上图右图情况出现
由于rear可能比front大，也可能比front小，所以尽管它们只相差一个位置时就是满的情况，但也可能是相差整整一圈， 若队列的最大尺寸为QueueSize，队列满的条件是(rear+1)%QueueSize==front
（取模“%”的目的就是为了整合rear与front大小为一个问题）。
比如上面例子中:
QueueSize = 5,当front=0,rear=4,(4+0) % 5=0，此时列队满;
又比如front=2，而rear=1。(1+1)%5=2，此时队列也是满的;
而front=2，rear=0,(0+1)%5=1,1≠2，此时队列并没有满。
另外，当rear>front时，队列的长度为rear-front。当rear<front时，队列长度分为两段，一段是QueueSize-front，另一段是0+rear，加在一起，队列长度为rear-front+Queue。因此通用的计算队列长度公式为：
(rear-front + QueueSize) % QueueSize
循环队列的顺序存储结构
typedef int QElemType;
/* 循环队列的顺序存储结构 */
typedef struct
{
QElemType data[MAXSIZE];
int front; /* 头指针 */
int rear; /* 尾指针，若队列不空，指向队列尾元素的下一个位置 */
}SqQueue;
初始化
/* 初始化一个空队列Q */
Status InitQueue(SqQueue *Q)
{
Q->front=0;
Q->rear=0;
return OK;
}
求队列长度
/* 返回Q的元素个数，也就是队列的当前长度 */
int QueueLength(SqQueue Q)
{
return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}
入队列操作
/* 若队列未满，则插入元素e为Q新的队尾元素 */
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;
}
出队列操作
/* 若队列不空，则删除Q中队头元素，用e返回其值 */
Status DeQueue(SqQueue *Q,QElemType *e)
{
if (Q->front == Q->rear) /* 队列空的判断 */
return ERROR;
*e=Q->data[Q->front]; /* 将队头元素赋值给e */
Q->front=(Q->front+1)%MAXSIZE; /* front指针向后移一位置， */
/* 若到最后则转到数组头部 */
return OK;
}
队列的链式存储结构及实现
队列的链式存储结构就是线性表的单链表，只不过它只能尾进头出，简称为链队列。
将队头指针指向链队列的头结点，队尾指针指向终端结点
空队列时，front和rear都指向头结点
链队列的结构
/* QElemType类型根据实际情况而定，这里假设为int */
typedef int QElemType;
typedef struct QNode /* 结点结构 */
{
QElemType data;
struct QNode *next;
} QNode,*QueuePtr;
typedef struct /* 队列的链表结构 */
{
QueuePtr front,rear; /* 队头、队尾指针 */
} LinkQueue;
入队操作
入队操作时就是在链表尾部插入结点
/* 插入元素e为Q的新的队尾元素 */
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赋值给原队尾结点的后继，见图中1 */
Q->rear=s; /* 把当前的s设置为队尾结点，rear指向s，见图中2 */
return OK;
}
出队操作
出队操作时，就是头结点的后继结点出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩一个元素时，则需将rear指向头结点
/* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
Status DeQueue(LinkQueue *Q,QElemType *e)
{
QueuePtr p;
if(Q->front==Q->rear)
return ERROR;
p=Q->front->next; /* 将欲删除的队头结点暂存给p，见图中1 */
*e=p->data; /* 将欲删除的队头结点的值赋值给e */
Q->front->next=p->next;/* 将原队头结点的后继p->next赋值给头结点后继，见图中2 */
if(Q->rear==p) /* 若队头就是队尾，则删除后将rear指向头结点，见图中3 */
Q->rear=Q->front;
free(p);
return OK;
}
循环队列与链队列
时间上，基本操作都为O(1)，不过循环队列是事先申请好空间，使用期间不释放，而对于链队列，每次申请和释放结点也会存在一些时间开销，如果入队出队频繁，则两者还是有细微差异。
空间上，循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题。而链队列不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但也可以接受。所以在空间上，链队列更加灵活。
在可以确定队列长度最大值的情况下，建议用循环队列，如果无法预估队列的长度时，则用链队列
参考
《大话数据结构》
