第4章栈和队列

数据结构与算法作者：胡明王红梅出版社：电子工业出版社邮箱：wanghm@第4章栈和队列本章的基本内容是：两种特殊的线性表——栈和队列从数据结构角度看，栈和队列是操作受限的线性表，他们的逻辑结构相同。从抽象数据类型角度看，栈和队列是两种重要的抽象数据类型。

4.1引言例4-1括号匹配问题C语言对于算术表达式中括号的配对原则是：右括号“)”与其前面最近的尚未配对的左括号“(”相配对。例如，算术表达式((x+5)*6-38))%5中的括号没有正确配对，多了一个“)”。如何判断给定表达式中所含括号是否正确配对呢？如果顺序扫描表达式，当扫描到右括号“)”时，需要查找已经扫描过的最后一个尚未配对的左括号“(”，对于“(”具有最后扫描到最先配对的特点。如何保存已经扫描过的尚未配对的左括号“(”，并对其实施配对操作呢？

4.1引言例4-2函数的嵌套调用函数的嵌套调用是在函数的执行过程中再调用其他函数。当函数C执行结束时，应该返回到什么位置呢？工作栈是如何保证调用次序的正确性呢？

4.1引言例4-3银行排队问题在需要顺序操作但人群众多的场合，排队是现代文明的一种表现。例如，储户到银行办理个人储蓄业务，需要领取一张排队单，在排队单上打印了储户的顺序号以及前面的人数，储户只需坐在椅子上等待，储蓄窗口会顺次叫号。如何实现这种先来先服务的功能呢？

4.1引言例4-4打印缓冲区在计算机系统中，经常会遇到两个设备在处理数据时速度不匹配的问题。例如，将计算机内存中的数据传送到打印机上打印输出。如何实现这种先来先服务的功能呢？栈的逻辑结构（a1,a2,……,an）栈：限定仅在表的一端进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶，另一端称为栈底。空栈：不含任何数据元素的栈。

栈顶栈底

4.2栈a1a2a3入栈出栈栈底栈顶插入：入栈、进栈、压栈删除：出栈、弹栈栈顶栈顶栈的逻辑结构

4.2栈栈的操作特性：后进先出a1a2a3入栈出栈栈底栈顶插入：入栈、进栈、压栈删除：出栈、弹栈栈顶栈的逻辑结构

4.2栈例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈底栈顶ab栈顶c栈顶情况1：栈的逻辑结构

4.2栈栈底栈顶ab栈顶c栈顶出栈序列：c出栈序列：c、b出栈序列：c、b、a例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈的逻辑结构情况1：

4.2栈栈底栈顶ab栈顶出栈序列：b情况2：例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈的逻辑结构

4.2栈栈底a出栈序列：b出栈序列：b、c出栈序列：b、c、ac栈顶栈顶注意：栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈的逻辑结构情况2：

4.2栈栈的抽象数据类型定义ADTStackData

栈中元素具有相同类型及后进先出特性，相邻元素具有前驱和后继关系Operation

InitStack

前置条件：栈不存在输入：无功能：栈的初始化输出：无后置条件：构造一个空栈

4.2栈DestroyStack

前置条件：栈已存在输入：无功能：销毁栈输出：无后置条件：释放栈所占用的存储空间Push

前置条件：栈已存在输入：元素值x

功能：在栈顶插入一个元素x

输出：如果插入不成功，抛出异常后置条件：如果插入成功，栈顶增加了一个元素栈的抽象数据类型定义

4.2栈Pop

前置条件：栈已存在输入：无功能：删除栈顶元素输出：如果删除成功，返回被删元素值，否则，抛出异常后置条件：如果删除成功，栈减少了一个元素GetTop

前置条件：栈已存在输入：无功能：读取当前的栈顶元素输出：若栈不空，返回当前的栈顶元素值后置条件：栈不变栈的抽象数据类型定义

4.2栈Empty

前置条件：栈已存在输入：无功能：判断栈是否为空输出：如果栈为空，返回1，否则，返回0

后置条件：栈不变endADT栈的抽象数据类型定义

4.2栈栈的顺序存储结构及实现顺序栈——栈的顺序存储结构如何改造数组实现栈的顺序存储？

012345678a1确定用数组的哪一端表示栈底。附设指针top指示栈顶元素在数组中的位置。

top

4.2栈出栈：top减1进栈：top加1栈空：top=-1

012345678a1topa2topa3top栈满：top=MAX_SIZE-1栈的顺序存储结构及实现

4.2栈顺序栈的存储结构定义：constintStackSize=10;//假定栈元素最多10个typedefintDataType;//DataType为栈元素的数据类型typedefstruct{DataTypedata[StackSize];//存放栈元素的数组

inttop;//栈顶指针，为栈顶元素在数组中的下标}SeqStack;

4.2栈顺序栈的实现——入栈voidPush(SeqStack&S,DataTypex){if(S.top==StackSize-1){printf("上溢");exit(-1);}S.data[++S.top]=x;}操作接口：

voidPush(SeqStack&S,DataTypex);时间复杂度？data[++top]=x

4.2栈顺序栈的实现——出栈DataTypePop(SeqStack&S){if(S.top==-1){printf("下溢");exit(-1);}x=S.data[S.top--];returnx;}操作接口：

DataTypePop(SeqStack&S);时间复杂度？

4.2栈两栈共享空间解决方案1：直接解决：为每个栈开辟一个数组空间。解决方案2：

顺序栈单向延伸——使用一个数组来存储两个栈在一个程序中需要同时使用具有相同数据类型的两个栈，如何顺序存储这两个栈？会出现什么问题？如何解决？

4.2栈两栈共享空间：使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，两个栈从各自的端点向中间延伸。两栈共享空间

4.2栈栈1的底固定在下标为0的一端；栈2的底固定在下标为StackSize-1的一端。

top1和top2分别为栈1和栈2的栈顶指针；Stack_Size为整个数组空间的大小（图中用S表示）；a1

a2…aitop1012…

…S-1两栈共享空间top2bj

……b2

b1栈1底栈2底

4.2栈top1=-1什么时候栈1为空？a1

a2…aitop1012…

…S-1两栈共享空间top2bj

……b2

b1top1

4.2栈top1=-1什么时候栈1为空？a1

a2…aitop1012…

…S-1两栈共享空间top2bj

……b2

b1什么时候栈2为空？top2top2=Stack_Size

4.2栈top1=-1什么时候栈1为空？a1

a2……aitop1012…

…S-1两栈共享空间top2bj

……b2

b1什么时候栈2为空？top2=Stack_Size什么时候栈满？top2=top1+1

4.2栈两栈共享空间的存储结构定义：constintStackSize=10;//假设两个栈最多10个元素typedefintDataType;//DataType为两个栈的数据类型typedefstruct{DataTypedata[StackSize];//存放两个栈的数组

inttop1,top2;//各自栈顶元素在数组中的下标}BothStack;

4.2栈1.如果栈满，则抛出上溢异常；2.判断是插在栈1还是栈2；2.1若在栈1插入，则2.1.1top1加1;

2.1.2在top1处填入x；2.2若在栈2插入，则2.2.1top2减1;

2.2.2在top2处填入x；两栈共享空间的实现——插入操作接口：voidPush(inti,DataTypex);

4.2栈1.若是在栈1删除，则

1.1若栈1为空栈，抛出下溢异常；

1.2删除并返回栈1的栈顶元素；2.若是在栈2删除，则

2.1若栈2为空栈，抛出下溢异常；

2.2删除并返回栈2的栈顶元素；两栈共享空间的实现——删除操作接口：DataTypePop(inti);

4.2栈栈的链接存储结构及实现链栈：栈的链接存储结构firsta1a2an∧ai链栈需要加头结点吗？如何改造链表实现栈的链接存储？将哪一端作为栈顶？将链头作为栈顶，方便操作。链栈不需要附设头结点。

4.2栈栈的链接存储结构及实现栈顶栈底链栈：栈的链接存储结构topanan-1a1∧firsta1a2an∧ai两种示意图在内存中对应同一种状态，启示？topa1an-1an∧栈顶栈底

4.2栈voidPush(Node*top,DataTypex){s=(Node*)malloc(sizeof(Node));s->data=x;s->next=top;top=s;}topanan-1a1∧链栈的实现——插入xstop操作接口：voidPush(DataTypex);

为什么没有判断栈满？

4.2栈DataTypePop(Node*top){if(top==NULL){printf("下溢");exit(-1);}x=top->data;p=top;top=top->next;free(p);returnx;}链栈的实现——插入操作接口：DataTypePop();

topanan-1a1∧topp

top++可以吗？

4.2栈顺序栈和链栈的比较时间性能：相同，都是常数时间O(1)。空间性能：顺序栈：有元素个数的限制和空间浪费的问题。链栈：没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构性开销。

总之，当栈的使用过程中元素个数变化较大时，用链栈是适宜的，反之，应该采用顺序栈。

4.2栈队列的逻辑结构队列：只允许在一端进行插入操作，而另一端进行删除操作的线性表。允许插入（也称入队、进队）的一端称为队尾，允许删除（也称出队）的一端称为队头。空队列：不含任何数据元素的队列。（a1,a2,……,an）队尾队头

4.3队列队列的操作特性：先进先出a1a2a3入队队尾队头出队队头队列的逻辑结构

4.3队列队列的抽象数据类型定义ADTQueueData

队列中元素具有相同类型及先进先出特性，相邻元素具有前驱和后继关系Operation

InitQueue

前置条件：队列不存在输入：无功能：初始化队列输出：无后置条件：创建一个空队列

4.3队列

DestroyQueue

前置条件：队列已存在输入：无功能：销毁队列输出：无后置条件：释放队列所占用的存储空间

EnQueue

前置条件：队列已存在输入：元素值x

功能：在队尾插入一个元素输出：如果插入不成功，抛出异常后置条件：如果插入成功，队尾增加了一个元素队列的抽象数据类型定义

4.3队列

DeQueue

前置条件：队列已存在输入：无功能：删除队头元素输出：如果删除成功，返回被删元素值后置条件：如果删除成功，队头减少了一个元素

GetQueue

前置条件：队列已存在输入：无功能：读取队头元素输出：若队列不空，返回队头元素后置条件：队列不变队列的抽象数据类型定义

4.3队列Empty

前置条件：队列已存在输入：无功能：判断队列是否为空输出：如果队列为空，返回1，否则，返回0

后置条件：队列不变endADT队列的抽象数据类型定义

4.3队列01234入队出队队列的顺序存储结构及实现顺序队列——队列的顺序存储结构如何改造数组实现队列的顺序存储？例：a1a2a3a4依次入队a1a2a3a4rearrearrearrear入队操作时间性能为O(1)

4.3队列如何改造数组实现队列的顺序存储？例：a1a2依次出队队列的顺序存储结构及实现01234入队出队a1a2a3a4rear

4.3队列如何改造数组实现队列的顺序存储？例：a1a2依次出队队列的顺序存储结构及实现01234入队出队a2a3a4rear

4.3队列如何改造数组实现队列的顺序存储？例：a1a2依次出队队列的顺序存储结构及实现01234入队出队a3a4rear出队操作时间性能为O(n)

4.3队列队列的顺序存储结构及实现如何改进出队的时间性能？放宽队列的所有元素必须存储在数组的前n个单元这一条件，只要求队列的元素存储在数组中连续的位置。设置队头、队尾两个指针

4.3队列队列的顺序存储结构及实现01234入队出队例：a1a2a3a4依次入队a1a2a3a4rearrearrearrear入队操作时间性能仍为O(1)frontrear约定：队头指针front指向队头元素的前一个位置，队尾指针rear指向队尾元素。

4.3队列例：a1a2依次出队队列的顺序存储结构及实现01234入队出队a1a2a3a4rearfrontfrontfront出队操作时间性能提高为O(1)

4.3队列例：a1a2依次出队队列的顺序存储结构及实现01234入队出队a3a4rearfront队列的移动有什么特点？

4.3队列例：a1a2依次出队队列的顺序存储结构及实现01234入队出队a3a4rearfront整个队列向数组下标较大方向移动单向移动性

4.3队列假溢出：当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，尽管此时数组的低端还有空闲空间，这种现象叫做假溢出。队列的顺序存储结构及实现继续入队会出现什么情况？01234入队出队a3a4rearfronta5rear

4.3队列循环队列：将存储队列的数组头尾相接。队列的顺序存储结构及实现如何解决假溢出？01234入队出队a3a4fronta5rearreara6

4.3队列不存在物理的循环结构，用软件方法实现。求模：（4＋1）mod5＝0队列的顺序存储结构及实现如何实现循环队列？01234入队出队a3a4frontreara6

4.3队列如何判断循环队列队空？队空的临界状态队列的顺序存储结构及实现01234入队出队a3rearfront

4.3队列如何判断循环队列队空？执行出队操作队空：front=rear队列的顺序存储结构及实现01234入队出队a3frontrearfront

4.3队列如何判断循环队列队满？队满的临界状态队列的顺序存储结构及实现01234入队出队a3a4fronta5reara6

4.3队列如何判断循环队列队满？执行入队操作队满：front=rear队列的顺序存储结构及实现01234入队出队a3a4fronta5reara6reara7

4.3队列方法一：附设一个存储队列中元素个数的变量num，当num=0时队空，当num=QueueSize时为队满；方法二：修改队满条件，浪费一个元素空间，队满时数组中只有一个空闲单元；方法三：设置标志flag，当front=rear且flag=0时为队空，当front=rear且flag=1时为队满。如何确定不同的队空、队满的判定条件？为什么要将队空和队满的判定条件分开？队列的顺序存储结构及实现

4.3队列队满的条件：(rear+1)modQueueSize=front队列的顺序存储结构及实现01234入队rear<fronta3a4fronta5reara6出队01234入队rear>fronta3a4fronta5reara6出队

4.3队列循环队列的存储结构定义：constintQueueSize=10;//定义数组的最大长度typedefintDataType;//DataType为队列元素的数据类型typedefstruct{DataTypedata[QueueSize];//存放队列元素的数组

intfront,rear;//队头和队尾指针}CirQueue;

4.3队列voidEnQueue(CirQueue&Q,DataTypex){if((Q.rear+1)%QueueSize==Q.front){printf("上溢");exit(-1);}Q.rear=(Q.rear+1)%QueueSize;Q.data[Q.rear]=x;}循环队列的实现——入队01234入队出队a3a4rearfronta5rear

4.3队列01234入队a4a5a6出队DataTypeDeQueue(CirQueue&Q){if(Q.rear==Q.front){printf("下溢");exit(-1);}Q.front=(Q.front+1)%QueueSize;returnQ.data[Q.front];}

循环队列的实现——出队frontrearfronta3

4.3队列DataTypeGetFront(CirQueue&Q){if(Q.rear==Q.front){printf("下溢");exit(-1);}i=(Q.front+1)%QueueSize;

returnQ.data[i];}循环队列的实现——读队头元素01234入队a4a5a6出队frontreara3i

4.3队列队列的链接存储结构及实现链队列：队列的链接存储结构队头指针即为链表的头指针firsta1a2an∧如何改造单链表实现队列的链接存储？rearfront

4.3队列队列的链接存储结构及实现非空链队列fronta1a2an∧rear空链队列front∧rear

4.3队列链队列的存储结构定义：typedefintDataType;//DataType为队列元素的数据类型typedefstructNode//定义链队列的结点结构{DataTypedata;Node*next;}Node;typedefstruct//定义链队列{Node*front,*rear;}LinkQueue;

4.3队列操作接口：

LinkQueue();

算法描述：voidInitQueue(LinkQueue&Q){s=(Node*)malloc(sizeof(Node));s->next=NULL;Q.front=Q.rear=s;}链队列的实现——队列的初始化front∧rear

4.3队列xs链队列的实现——入队操作接口：

voidEnQueue(DataTypex);fronta1an∧rear∧rearfrontxs∧∧rearrear算法描述：s->next=NULL;rear->next=s;rear=s;如何没有头结点会怎样？

4.3队列xs链队列的实现——入队操作接口：

voidEnQueue(DataTypex);fronta2an∧rear∧rear算法描述：s->next=NULL;rear->next=s;rear=s;如何没有头结点会怎样？a1

4.3队列链队列的实现——入队操作接口：

voidEnQueue(DataTypex);front=rear=NULLxs∧rear算法描述：s->next=NULL;rear=s;front=s;如何没有头结点会怎样？front算法描述：s->next=NULL;rear->next=s;rear=s;

4.3队列链队列的实现——入队voidEnQueue(LinkQueue&Q,DataTypex){s=(Node*)malloc(sizeof(Node));s->data=x;s->next=NULL;Q.rear->next=s;

Q.rear=s;}

4.3队列链队列的实现——出队fronta1a2an∧rearp算法描述：