
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的元素个数

由于栈本身就是一个线性表，那么我们在讨论线性表的顺序存储和链式存储，对于栈来说也同样适用

栈的顺序存储结构及实现

栈的顺序存储结构

既然栈线性表的特例，那么栈的顺序存储其实也是线性表顺序存储的简化，我们简称为顺序栈

线性表是用数组来实现的，对于栈来说，我们将下标为0的作为栈底，因为首元素都在栈底，变化最小，所以它作栈底

我们通过定义一个top元素来表示栈顶，若存储栈的长度为StackSize，则栈顶位置top必须小于StackSize，当栈存在一个元素时，top等于0，因此通常把空栈的判定条件定位top等于-1

栈的结构定义


typedef int SElemType;//SElemType类型根据实际情况而定，这里假设为int
//顺序栈结构
typedef struct
{
SElemType data[MAXSIZE];
int top;//用于栈顶指针
}SqStack;

栈的顺序存储结构——进栈操作

对于进栈操作


//插入元素e为新的栈顶元素
Status Push(SqStack *S,SElemType e)
{
if(S->top==MAXSIZE-1)//栈满
return ERROR;
S->top++;//栈顶指针增加1
S->data[s->top]=e;//将新插入元素赋值给栈顶空间
return ok；
}

栈的顺序存储结构——出栈操作


//若栈不空，则删除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；
}

两者没有涉及循环语句，因此时间复杂度均为O(1）。

两栈共享空间

栈的顺序存储很方便，因为它只准栈顶进出元素，所以不存在线性表插入和删除时需要移动元素的问题，不过存在一个很大的缺陷，容易造成空间浪费与空间不足。

我们有两个相同类型的栈，我们为他们各自开辟了数组空间，极可能是第一个栈已经满了，再进栈就溢出了，而另一个栈还有很多存储空间，我们完全可以一个数组来存储两个栈

实现需要一些小技巧：

数组有两个端点，两个栈有两个栈底，让一个栈的栈底维数组的始端，即下标为0，另一个栈为数组的末端，即下标为数组长度n-1处，这样，如果两个栈如果增加元素，就是两端点向中间延伸

关键思路：

它们是在数组的两端，向中间靠拢。top1和top2是栈1和栈2的栈顶指针，可以想象，只要他们俩不见面，两个栈就可以一直使用

栈1为空时，就是top1等于-1时；当top2等于n时，即栈2为空

栈满情况：

1.若栈2为空栈，栈1的top1等于n-1时，就是栈1满了

2.若栈1为空栈，栈2的top等于0时，就是栈2满了

3.若top1+1=top2时，栈也就满了

两栈共享空间结构代码如下：


//两栈共享空间结构
typedef struct
{
SElemType data[MAXSIZE];
int top1;

对于两栈共享空间的push方法，我们除了要插入元素值参数外，还需要有一个判断是栈1还是栈2的栈号参数stackNumber。插入新元素代码如下


//插入元素e为新的栈顶元素
Status Push(SqDoubleStack *S,SElemTyp e,int stackNumber)
{
if(S->top1+1==S->top2)//栈已满，不能再push新的元素
return ERROR;
if(stackNumber==1)//栈1有元素进栈
S->data[++S->top1]=e;//若时栈1则先top+1后给数组元素赋值
else if(stackNumber==2)//栈2有元素进栈
S->data[--S->top2]=e;//若是栈2则先top2-1后给数组元素赋值
return ok；
}

对于两栈共享空间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;
*e=S->data[S->top1--];
}
else if(stackNumber==2){
if(S->top2==n)
return ERROR;
*e=S->data[S->top2++];
}
return ok;
}

注意：

这只是针对于两个具有相同数据类型栈的一个设计上的技巧，如果是不相同数据类型的栈，这种方法不但不能更好地处理问题，反而会使问题变得更加复杂

栈的链式存储结构及实现

栈的链式存储结构

栈的链式存储结构，简称为链栈

由于单链表有头指针，而栈指针也是必须的，所以将二者合二为一，所以比较好的办法就是把栈顶放在单链表的头部，另外栈顶已经在头部了，单链表中比较常用的头结点也就失去了意义

对于空栈来说，链表原定义是头指针向空，那么链表的空气是就是top=NULL


//链栈结构
typedef struct StackNode
{
SElemType data;
struct StackNode*next;
}StackNode,*LinkStackPtr;
 
typedef struct
{
LinkStackPtr top;
int count;
}LinkStack;

栈的链式存储结构——进栈操作

对于栈链的进栈push操作，假设元素值为e的新结点s，top为栈顶指针


//插入元素e为新的栈顶元素
Status Push(LinkStack *S,SElemType e)
{
LinkStackPtr s=(LinkStackptr)malloc(sizeof(StaackNode));
s->data=e;
s->next=S->top;//把当前的栈顶元素赋值给新结点的直接后继
S->top=s;//将新的结点s赋值给栈顶指针
S->count++;
return ok;
}

栈的链式存储结构——出栈操作

至于链栈的出栈pop操作，也是很简单的三句操作

假设变量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)

对比一下顺序栈与链栈，它们的时间复杂度是一样的，均为O(1)，对于空间性能，顺序栈需要事先确定一个固定的长度，可能会造成空间的浪费

但链栈要求每个元素都有指针域，这也同时增加了一些内存，但对于栈的长度无限制

注意：

如果栈的使用过程中元素变化不可预料，有时很小，有时非常大。那么最好是用链栈，反之，如果他的变化在可控范围内，建议使用顺序栈会更好一些

栈的作用

栈的引入简化了程序设计的问题，划分了不同关注层次，使得思考范围缩小，更加聚焦与我们要理解的问题核心。

而像线性表顺序存储结构用到的数组，因为要分散精力去考虑数组的下标增减等细节问题，反而掩盖了问题的本质

栈的应用——递归

栈有一个很重要的应用：在程序设计语言中实现了递归

原来，A镜子里有B镜子的像，B镜子里也有A镜子的像，这样的反反复复，就会产生一连串的“像中像”，这是一种递归现象

先来看一个经典的递归例子：斐波那契数列

斐波那契数列的实现：

斐老说如果兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。假设所有兔子都不死，那么一年以后可以繁殖多少对兔子呢？

所经历的月数	1	2	3	4
兔子对数	1	1	2	3

从表格即可得出规律：前面相邻两项之和构成了后一项

用数学函数定义就是：

n=0时，F(n)=0；

n=1时，F(n)=1；

n>1时，F(n)=F(n-1)+F(n-2)；

我们要实现这样的数列用常规的的迭代办法实现如下


int main()
{
int i;
int a[40];
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]);
}
return 0;
}

斐波那契的递归函数


//斐波那契的递归函数
int Fbi(int i)
{
if(i<2)
return i==0?0:1;
return Fbi(i-1)+Fbi(i-2);//这里就是函数自己，等于在调用自己
}
int main()
{
int i;
printf("递归显示斐波那契数列\n");
for(i=0;i<40;i++)
{
printf("%d",Fbi(i));
return 0;
}

递归的定义：

在高级语言中，调用自己和其他函数并没有本质的不同。我们把一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称为递归函数

当然，写程序最怕的就是陷入永不结束的无穷递归中，所以，每个递归定义必须至少有一个条件，满足

迭代和递归的区别是：

迭代使用的是循环结构，递归使用的是选择结构

递归：

1.递归能使程序的结构更清晰，更简洁，更容易让人理解，从而减少读懂代码的时间

2.大量的递归调用会建立函数的副本，会损耗大量的时间和内存

迭代：

迭代则不需要反复调用函数和占用额外的内存

所以我们应该视情况而定

栈和递归的关系：

简单的说，就是在前进阶段，对于每一层递归，函数的局部变量、参数值一节返回地址都被压入栈中。

在退回阶段，位于栈顶的局部变量、参数值和返回地址呗弹出，用于返回电泳层次中执行代码的其余部分，也就是恢复了调用的状态。

栈的应用——四则运算表达式求值

后缀（逆波兰）表达法的定义

一种不需要括号的后缀表达法，我们也把它称为逆波兰表示

我们先来看看：

正常数学表达式：9+（3-1)X3+10÷2；

后缀表达式：9 3 1 - 3*+10 2 /+

叫做后缀的原因在于所有的符号都是在运算狮子的后面

后缀表达式的计算结果：

后缀表达式：9 3 1-3*+10 2/+;

规则：

从左到右遍历表达式的每个数字和符号，遇到数字就是进栈，遇到符号就是将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果；

（1）初始化一个空栈。此栈用来对要运算的数字进出使用

（2）后缀表达式中前三个都是数字，所以9、3、1进栈

（3）接下来是“—”,所以将栈中1出栈作为减数，3出栈作为被减数，并运算3-1得到2，再将2进栈

（4）接着是数字3进栈

（5）后面是“*”，也就一位着栈中3和2出栈，2与3相乘，得到6，并将6进栈

（6）下面是“+”，所以栈中6和9出栈，9与6相加，得到15，将15进栈

（7）接着是10与2两个数字进栈

（8）接下来是符号“/”，因此，栈顶的2与10出栈，10与2相除，得到5，将5进栈

（9）最后一个是符号“+”，所以15与5出栈并相加，得到20，将20进栈

（10）结果是20出栈，栈变为空

中缀表达式转后缀表达式：

我们把平时所用的标准四则运算表达式，即“9+（3-1）X3+10÷2”叫做中缀表达式

中缀表达式转化为后缀表达式：

规则：

从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分;

若是符号，则判断其与栈顶符号的优先级，是右括号或优先级不高于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。

（1）初始化一空栈，用来对符号进出栈使用

（2）第一个字符是数字9，输出9，后面是符号“+”，进栈

（3）第三个字符是“(”，依然是符号，因其只是左括号，还未配对，故进栈

（4）第四个字符是数字3，输出，总表达式为9 3，接着是“—”，进栈

（5）接下来是数字1，输出，总表达式为9 3 1，后面是符号“)”，此时，我们需要去匹配此前的“(”，所以栈顶依次出栈，并输出，直到“(”出栈为止。此时左括号上方只有“—”，因此输出“—”。总的输出表达式为9 3 1—。

（6）紧接着是符号“X”，因为此时的栈顶符号为“+”，优先级低于“X”，因此不输出，“*”进栈。接着是数字3，输出，总的表达式为9 3 1 -3

（7）之后是符号“+”，此时当前栈顶元素“*”比这个“+”的优先级高，因此栈中元素出栈并输出（没有比“+”更低的优先级，所以全部出栈），总输出表达式为9 3 1-3 * +。然后将当前这个符号“+”进栈。也就是说，前6张图的栈底的“+”是指栈中缀表达式中开头的9后面那个“+”，而现在指的是最后一个“+”。

（8）紧接着数字10，输出，总表达式变为9 3 1 * + 10.后面是符号“÷”，所以“/”进栈

（9）最后一个数字2，输出，总的表达式为9 3 1 -3 * + 10 2

（10）因为已经到最后，所以将栈中符号全部出栈并输出。最终输出的后缀表达式结果为9 3 1 - 3 * + 10 2 / +

从刚才的推导中能发现，要想让计算机具有处理我们通常的标准（中缀）表达式的能力，最重要的就是一下两步：

（1）将中缀表达式转化为后缀表达式（栈用来进出运算的符号）

（2）将后缀表达式进行运算得出结果（栈用来进出运算的数字）

队列的定义

队列是指允许在一段进行插入操作，而在另一端进行删除操作的线性表

队列是一种先进先出的线性表，简称FIFO。允许插入一段称为队尾，允许删除的一段称为队头。

假设队列q=（a1,a2,...,an），那么a1就是队头元素，而an是队尾元素。

队列的抽象数据类型

同样是线性表，队列也有类似于线性表的各种操作，不同的就是插入数据只能在队尾进行，删除数据只能在队头进行。


ADT (Queue)
Data
//同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系
Operation
InitQueue(*Q)://初始化操作，建立一个空队列Q
DestroyQueue(*Q)://若队列Q存在，则销毁它
ClearQueue(*Q)://将队列Q清空
QueueEmpty(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)

为何要全部移动元素呢，也就是说，队头不需要一定在下标为0的位置

为了避免当只有一个元素时，队头和队尾重合使处理变得麻烦，所以引进两个指针，front指针指向队头元素，rear指针指向队尾元素的下一个位置，这样当front等于rear时，此时队列不是还剩一个元素，而是空队列

假设是长度为5的数组，初始状态为空队列，front与rear指针均指向下标为0的位置。然后入队a1、a2、a3、a4,front指针依然指向下标为0位置，而rear指针指向下标为4的位置

出队a1、a2,则front指针指向下标为2的位置，rear不变，如再入队a5，此时front指针不变，rea指针移动到数组之外，会产生数组越界的错误，可实际上，我们的队列在下标为0和1的地方还是空闲。我们把这种现象叫做“假溢出”。

循环队列的定义：

为了解决假溢出，就再从头开始，也就是头尾相接的循环

我们把队列的这种头尾相接的顺序存储结构称为循环结构

继续刚才的例子，把rear改为指向下标为0的位置，这样就不会造成指针指向不明的问题

接着入队a6，将它放置于下标为0处，rear指针指向下标为1处，若再将a7入队，则rear指针就与front重合，同时指向下标为2的位置

1.问题又出来了，我们刚才说，空队列时，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大小为一个问题）。

另外，当rear>front时，此时队列的长度为rear—front。但当rear<front时，队列长度分成两端，一段时间QueueSize—front，另一段时0+rear，加在一起，队列长度为rear—front+QueueSize。

此时通用的计算队列长度的公式为：

（rear-front+QueueSize）%QueueSize

循环结构的顺序存储结构代码如下;


typedef int QElemType;//QElemType类型根据实际情况而定，这里假设为int
//循环队列的顺序存储结构
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;
Q->rear=(Q->rear+1)%MAXSIZE;//rear指针向后移一位，若到最后则转到数组头部
return ok;
}

循环队列的出队列操作代码如下：


//若队列不空，则删除Q中队头元素，用e返回其值
Status DeQueue(SqQueue *Q,QElemType *e)
{
if(Q->rear==Q->front)
return ERROR;
*e=Q->data[Q->front];
Q->front=(Q->front+1)%MAXSIZE;
return ok;
}

队列的链式存储结构及实现

队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。

为了方便操作，我们将队头指针指向链队列的头结点，而队尾指针指向终端结点

空队列时，front和rear都只想头结点

链队列的结构代码：


typedef struct QNode{//结点结构
QElemType data;
struct QNode*next;
}QNode,*QueuePtr;
 
typedef struct//队列的链表结构
{
QueuePtr front,rear;//队头，队尾指针
}LinkQueue;

队列的链式存储结构——入队操作：


//插入元素e为Q的新的队尾元素
Status EnQueue(LingkQueue*Q,QElemType e)
{
QueuePtr s=(QueuePtr)malloc(sizeof(QNode));
if(!s)
exit(-1);
s->data=e;
s->next=NULL;
Q->rear->next=s;
Q->rear=s;
return ok;
}

队列的链式存储结构——出栈操作：


//若队列不空，删除Q的队头元素，用e返回其值，并返回ok，否则返回false
Status DeQueue(LingkQueue *Q,QElemType *e)
{
QueuePtr p;
if(Q->front==Q->rear)
return ERROR;
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;
}

总的来说，在可以确定对猎场丢最大值的情况下，建议用循环队列，如果无法预估队列的长度，则用链队列。

总结回顾

栈：是限定尽在表尾进行插入和删除操作的线性表

队列：是指匀速在一段进行插入操作，而在另一端惊醒删除操作的线性表

它们均可以通过线性表的顺序存储结构来实现，但都存在着顺序存储的一些弊端

对于栈来说，如果是两个相同的数据类型的栈，则可以用数组的两端作栈底的方法来让两个栈共享数据，这就可以最大化地利用数组空间

对于队列来说，为了避免数组插入和删除时需要移动数据，于是引进了循环队列，使得队头和队尾可以再数组中循环变化。解决了移动数据的时间损耗，使得本来插入和删除时O(n)的时间复杂度变为O(1)

它们也都可以通过链式存储结构来实现，原则上与线性表基本相同

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/557506