栈和队列及其应用
在这篇文章将介绍数据结构中的栈和队列及它们的常见应用。在之前写过的文章中或者看本文的读者应该知道有两种存储方式，一种是顺序存储，一种是链式存储，本文将通过这两种存储来实现栈和队列。
栈
栈的基本概念
定义：栈是仅在表尾进行插入或删除操作的
线性表
，又称为后进先除（Last In First Out）线性表。表尾=栈顶（top），表头=栈底（bottom）。不含元素的空表为空栈。
首先这是一个线性表，就具有线性表的特征，假设我现在有5个乒乓球，依次排列。如下图：
那么我现在有一个杯子，杯口只允许一个乒乓球进入，如下图，我已经有两个球在里面了。
那么，现在让a3进入，这个就叫入栈。
再让a3出去，就叫做出栈。
把最下面的叫做栈底，可以理解成杯子底，上面的叫做栈顶，可以理解为乒乓球的位置差不多。我们通常把栈顶的值赋值为
-1
。
栈的基本操作
InitStack(&S)：构造空的栈，分配内存空间
DestroyStack(&S)：销毁栈
StackEmpty(S)：判断栈是否为空
GetTop(S,&x)：读栈顶元素，若S非空，可以理解为查找，不过只查找栈顶元素
Push(&S,x)：入栈，若栈S未满，即将x加入使之成为新栈顶。理解为插入
Pop(&S,&x)：若栈S非空，则弹出栈顶元素，并用x返回。理解为删除
它这里后面三个操作都是对栈顶元素的。
顺序存储
定义：顺序栈——栈的顺序存储结构，利用一组连续的存储单元依次存放自栈底到栈顶的数据的元素。这种栈的大小是固定的，也就是一开始就定义好的数组。下面来看下它的结构。
#define MAXSIZE 1000
typedef struct{
ElemType data[MAXSIZE];//静态数组存放栈中元素
int top;//栈顶指针
}
我们可以通过下图简单来看下顺序栈示意图。
Top指向当前位置
判断栈空
bool StackEmpty(SqStack S){
if(S.top==-1)
return true;
else
return false;
}
这里top一开始指向的是
-1
，才可以判断栈是否为空。
top指针指向栈顶元素
。
入栈
bool Push(SqStack &S,ElemType x){
if(S.top==MAXSIZE-1)
return false;
S.top=S.top+1;//指针前移
S.data[S.top]=x//元素入栈
return true;
}
上面我们说了top是指向栈顶元素，就跟上面那张图一样，MAXSIZE本来是1000，但是数组下标是从0开始，也就是说到999了，其实就已经满了，如果这里
S.top==MAXSIZE-1
就是这么解释的。后面的栈顶指针加1和赋值就很好理解了。
出栈
bool Pop(SqStack &S,ElemType &x){
if(S.top==-1)
return false;
x=S.data[S.top];
S.top=S.top-1;
return true;
}
读栈顶元素
bool GetTop(SqStack S,ElemType &x){
if(S.top==-1)
return false;
x=S.data[S.top];//元素出栈
return true;
}
Top指向下一个插入位置
入栈
bool Push(SqStack &S,ElemType x){
if(S.top==MAXSIZE)
return false;
S.data[S.top]=x//元素入栈
S.top=S.top+1;//指针前移
return true;
}
这里和上面有所区别，因为Top指向的是下一个位置，所以本来指向999应该指向1000了，这里就直接是
MAXSIZE
。然后，后面应该先赋值，再让它指向下一个。
出栈
bool Pop(SqStack &S,ElemType &x){
if(S.top==0)
return false;
S.top=S.top-1;
x=S.data[S.top];
return true;
}
由于
top
指向的是下一个元素的位置，所以如果
top
在0的话，说明其实0是没有插入的，那么栈就是空的。并且
top
需要先指向当前的才能出栈，所以得先让
top-1
。
共享栈
定义：若需要用到两个相同类型的栈，可用一个数组
data[0...MAXSIZE-1]
来实现两个栈，称之为共享栈。具体我们可以看下图。
这里就需要两个栈顶指针，因为有两个栈，一个指向
-1
，一个指向
MAXSIZE
。下面来看一下它的结构体。
typedef struct{
ElemType data[MAXSIZE];//静态数组存放栈中元素
int top1;//1号栈顶指针
int top2;//2号栈顶指针
}ShStack;
下面看一下栈空的条件：
1号栈空：top1==-1
2号栈空：top2==MAXSIZE
栈满条件：
top1==top2-1
从图里看，一号栈是从下面往上面，二号栈是上面往下面，也就是，当一号栈当前的等于二号栈当前-1，那么数组就满了，不太理解的可以手动模拟一下这个过程就理解了。
入栈出栈操作
入1号栈：top1++;data[top1]=x;
入2号栈：top2--;data[top2]=x;
出1号栈：x=data[top1];top1--;
出2号栈：x=data[top2];top2++;
链式存储
定义：采用链式存储结构的栈为链栈，采用单链表来实现，且规定栈的所有操作都是
在单链表的表头进行
，有点是不存在栈满溢出的情况。
链式存储的重点是在表头进行插入，也就是它的操作都在表头进行，这里的链表是没有头结点的，也就是只有头指针，只需要在头指针后面加入就行了。
结构
typedef struct StackNode{
SElemType data;
struct StackNode *next;
}StackNode;
入栈
bool Push(LinkStack &s,SElemType){
StackNode *p;
p=(StackNode *)malloc(sizeof(StackNode));
p->data=e;
p->next=s;
s=p;
return true;
}
插入以后，要让头指针指向插入的结点。
出栈
bool Pop(LinkStack &s,SElemType &e){
StackNode *p;
if(s==NULL)//栈为空
return false;
e=s->data;
p=s;
s=s->next;
free(p);
return true;
}
出栈和入栈不同，链栈中可以一直入栈（理想情况下，不去考虑内存）。而出栈则需要判断栈中是否有东西。
取栈顶元素
SElemType GetTop(LinkStack s){
if(s!=NULL)
return s->data;
}
栈总结
栈的内容大概就是这么多了，当然还有一个公式要记，就是如果n个不同的元素入栈，那么出栈就是卡特兰数：
队列
队列的基本概念
定义：队列是操作受限的线性表，仅允许在表的一端插入，另一端删除，具有点进先出的特点。可以想象成一车道，只允许一部车通过，第二部车只能在第一部车过这个路口后才能再过。也可以理解成食堂排队。
队列的基本操作
InitQueue(&q)：构造空的队列
DestroyQueue(&q)：销毁队列
QueueEmpty(q)：判断队列是否为空
enQueue(&q,e)：去队列，将元素e进队作为队尾元素。
Pop(&q,&e)：出队列，从队列中出队一个元素，并将其赋给e。
顺序存储
定义：顺序队列——队列的顺序存储结构，利用一组地址连续的存储单元依次存放队列的数据元素。从下面三张图来理解下空队，入队，和出队。
空队：队列里什么东西都没有，这时
front==rear
。
front
指向队头，
rear
指向队尾的下一个元素。当它们相等时，队列为空。
这里我们可以看到，进行了依次入队操作，front还是指向原来的，rear因为是指向队尾的下一个，所以它向后移动了一个。
这时进行了出队操作，front就向后移动了，这时候front又等于rear。说明队列为空。
下面来看下结构体。
typedef struct{
QElemType data[MAXSIZE];//静态数组存放队列中元素
int front,rear;//队首和队尾指针
}SqQueue;
来看一下几个操作
队空：q.front==q.rear
队满：q.rear==MaxSize
入队：data[rear]=e;rear++
出队：e=data[front];front++
下面是几个具体的操作代码实现
判断队空
bool QueueEmpty(SqQueue q){
if(q.front==q.rear)
return true;
else
return false;
}
入队
bool enQueue(SqQueue &q,QElemType e){
if(q.rear==MAXSIZE)
return false;
q.data[q.rear]=e;
q.rear++;
return true;
}
这里我们判断队满的条件仅仅是q.rear到MAXSIZE的位置，并没有考虑到如果front也在后面，那front前面就会有几个空的，队列就不是满的，没有利用好空间，后面会引入循环队列来解决这个问题。
出队
bool deQueue(SqQueue &q,QElemType &e){
if(q.front==q.rear)
return false;
e=q.data[q.front];
q.front++;
return true;
}
这里判断
q.front==q.rear
是为了说明队列中有东西才可以出队。
循环队列
上面提到了为了更好的使用空间，那么现在就引入了循环队列，它是将顺序队列在想法上构成了一个环装，也就是我最后一个入队之后，如果第一个位置是空的，那就可以继续入队。
下面来看下队空和队满的条件
q->front==q->rear//队空
(q->rear+1）%MAXSIZE == q->front;//队满
这里队空还是一样，只要它们两个指的是同一个位置就是队空。队满的话举个例子，比如数组大小为4，那么它最大的MAXSIZE应该为4，这时候我数组满了，
(rear+1)%MAXSIZE
其实指向的是
front
的位置。通过下面这张图可以比较好的理解。这里的
rear
是指向队尾元素，而不是队尾元素的下一个。不同时候的
rear
要区分清楚。
循环队列之判断队空
bool QueueEmpty(SqQueue q){
if(q.front==q.rear)
return true;
else
return false;
}
循环队列之入队
bool enQueue(SqQueue &q,QElemType e){
if((q.rear+1)%MAXSIZE==q.front)
return false;
q.data[q.rear]=e;
q.rear=(q.rear+1)%MAXSIZE;
return true;
}
这里值得注意的是，入队的时候不是
q.rear=q.rear+1
，而是要
%MAXSIZE
,要考虑循环队列的条件。
循环队列之出队
bool deQueue(SqQueue &q,QElemType &e){
if(q.front==q.rear)
return false;
e=q.data[q.front];
q.front=(q.front+1)%MAXSIZE;
return true;
}
同样，这里的
q.front
也要
%MAXSIZE
才行。
链式存储
定义：采用链式存储结构的队列为链队列，采用单链表来实现，在单链表表头进行删除/出队操作，在单链表表尾进行插入/入队操作。
可以从上面这张图来理解，所以我们需要两个指针来指向队头和队尾。下面是它的结构体
typedef struct qNode{
QElemType data;
struct qNode *next;
}DataNode;
typedef struct{
DataNode *front,*rear;
}LinkQuNode;
链队入队操作
入队就是插入队尾
void enQueue(LinkQuNode &q,QElemType e){
DataNode *p;
p=(DataNode *)malloc(sizeof(DataNode));
p->data = e;
p->next = NULL;
if(q->rear==NULL)
q->front=p;
q->rear=p;
else{
q->rear->next=p;
q->rear=p
}
}
首先先声明一个p结点，然后给p分配空间，因为插入的结点是最后一个结点，所以得让
p->next
为
NULL
。q是队列，如果队列的
rear
为
NULL
,也就是队列中没有其他东西，那么让队列的
front
和
rear
都指向p。如果队列中有元素，那么就让这个元素的
next
指向p，并且让
p
成为这个队列的队尾，也就是
q->rear=p
。
链队出队操作
bool deQueue(LinkQuNode &q,QElemType &e){
DataNode *t;
if(q->rear==NULL) return false;//队列中没有数据
t=q->front;
if(q->front==q->rear)//这样说明只有一个元素
q->front=q->rear=NULL;
else
q->front=q->front->next;//有两个元素就让front指向它后面一个
e=t->data;
free(t);
return true;
}
这里基本的操作在代码注释里也有详细说明了，就不再讲述了。
双端队列
定义：两端都可以进行进队和出队操作的。
双端队列不同于本来的队列，它的选择比较多，以下三种是常见的双端队列。
1.双端队列
这种队列两边都可以输入和输出，如下图：
2.输出受限的双端队列
这种队列只允许一端输出，但是两端都可以输入，如下图：
3.输入受限的双端队列
这种队列只允许一端输入，但是两端都可以输出，如下图：
总结
在本篇文章中，主要讲了栈和队列，基本涉及到了所有的知识点，栈和队列的应用将单独开一篇文章进行解析，毕竟我觉得一篇文章太长不太好，主要是写着累emmm。好了如果文章中有说明问题或者哪里没有表述的很清晰，欢迎在评论区下面给我留言，一起探讨才有进步。