第4章栈和队列

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

2、 数据结构与算法数据结构与算法电子工业出版社电子工业出版社 4.1 引言引言例例4-1 括号匹配问题括号匹配问题 C语言对于算术表达式中括号的配对原则是：右括语言对于算术表达式中括号的配对原则是：右括号号“)”与其前面最近的尚未配对的左括号与其前面最近的尚未配对的左括号“(”相配对。相配对。例如，算术表达式例如，算术表达式(x + 5) * 6 - 38) % 5中的括号没中的括号没有正确配对，多了一个有正确配对，多了一个“)”。 如何判断给定表达式中所含括号是否正确配对呢？如何判断给定表达式中所含括号是否正确配对呢？如果顺序扫描表达式，当扫描到右括号如果顺序扫描表达式，当扫描到右括号“)”时

3、，需时，需要查找已经扫描过的最后一个尚未配对的左括号要查找已经扫描过的最后一个尚未配对的左括号“(”，对于，对于“(”具有最后扫描到最先配对的特点。具有最后扫描到最先配对的特点。如何保存已经扫描过的尚未配对的左括如何保存已经扫描过的尚未配对的左括号号“(”，并对其实施配对操作呢？，并对其实施配对操作呢？数据结构与算法数据结构与算法电子工业出版社电子工业出版社 4.1 引言引言例例4-2 函数的嵌套调用函数的嵌套调用函数的嵌套调用是在函数的执行过程中再调用其他函数的嵌套调用是在函数的执行过程中再调用其他函数。当函数函数。当函数C执行结束时，应该返回到什么位置执行结束时，应该返回到什么位置呢？呢？

4、工作栈是如何保证调用次序的正确性呢？工作栈是如何保证调用次序的正确性呢？数据结构与算法数据结构与算法电子工业出版社电子工业出版社 4.1 引言引言例例4-3 银行排队问题银行排队问题在需要顺序操作但人群众多的场合，排队是现代文在需要顺序操作但人群众多的场合，排队是现代文明的一种表现。例如，储户到银行办理个人储蓄业明的一种表现。例如，储户到银行办理个人储蓄业务，需要领取一张排队单，在排队单上打印了储户务，需要领取一张排队单，在排队单上打印了储户的顺序号以及前面的人数，储户只需坐在椅子上等的顺序号以及前面的人数，储户只需坐在椅子上等待，储蓄窗口会顺次叫号。待，储蓄窗口会顺次叫号。如何实现这种先来先

5、服务的功能呢？如何实现这种先来先服务的功能呢？数据结构与算法数据结构与算法电子工业出版社电子工业出版社 4.1 引言引言例例4-4 打印缓冲区打印缓冲区在计算机系统中，经常会遇到两个设备在处理数据在计算机系统中，经常会遇到两个设备在处理数据时速度不匹配的问题。例如，将计算机内存中的数时速度不匹配的问题。例如，将计算机内存中的数据传送到打印机上打印输出。据传送到打印机上打印输出。如何实现这种先来先服务的功能呢？如何实现这种先来先服务的功能呢？数据结构与算法数据结构与算法电子工业出版社电子工业出版社栈的逻辑结构栈的逻辑结构（a1, a2, , an）p栈：栈：限定仅在限定仅在表的一端表的一端进行插

6、入和删除操作的进行插入和删除操作的线性表线性表。p允许插入和删除的一端称为栈顶，另一端称为栈底。允许插入和删除的一端称为栈顶，另一端称为栈底。p空栈：空栈：不含任何数据元素的栈。不含任何数据元素的栈。 栈顶栈顶栈底栈底 4.2 栈栈数据结构与算法数据结构与算法电子工业出版社电子工业出版社a1a2a3入栈入栈出栈出栈栈底栈底栈顶栈顶插入：入栈、进栈、压栈插入：入栈、进栈、压栈删除：出栈、弹栈删除：出栈、弹栈栈顶栈顶栈顶栈顶栈的逻辑结构栈的逻辑结构 4.2 栈栈数据结构与算法数据结构与算法电子工业出版社电子工业出版社栈的操作特性：栈的操作特性：后进先出后进先出a1a2a3入栈入栈出栈出栈栈底栈底栈

7、顶栈顶插入：入栈、进栈、压栈插入：入栈、进栈、压栈删除：出栈、弹栈删除：出栈、弹栈栈顶栈顶栈的逻辑结构栈的逻辑结构 4.2 栈栈数据结构与算法数据结构与算法电子工业出版社电子工业出版社例：有三个元素按例：有三个元素按a、b、c的次序依次进栈，且每个的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？元素只允许进一次栈，则可能的出栈序列有多少种？栈底栈底栈顶栈顶ab栈顶栈顶c栈顶栈顶 情况情况1：栈的逻辑结构栈的逻辑结构 4.2 栈栈数据结构与算法数据结构与算法电子工业出版社电子工业出版社栈底栈底栈顶栈顶ab栈顶栈顶c栈顶栈顶出栈序列：出栈序列：c出栈序列：出栈序列：c、b出栈序

8、列：出栈序列：c、b、a例：有三个元素按例：有三个元素按a、b、c的次序依次进栈，且每个的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？元素只允许进一次栈，则可能的出栈序列有多少种？栈的逻辑结构栈的逻辑结构 情况情况1： 4.2 栈栈数据结构与算法数据结构与算法电子工业出版社电子工业出版社栈底栈底栈顶栈顶ab栈顶栈顶出栈序列：出栈序列：b 情况情况2：例：有三个元素按例：有三个元素按a、b、c的次序依次进栈，且每个的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？元素只允许进一次栈，则可能的出栈序列有多少种？栈的逻辑结构栈的逻辑结构 4.2 栈栈数据结构与

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

10、工业出版社栈的抽象数据类型定义栈的抽象数据类型定义 ADT StackData 栈中元素具有相同类型及后进先出特性，栈中元素具有相同类型及后进先出特性， 相邻元素具有前驱和后继关系相邻元素具有前驱和后继关系Operation InitStack 前置条件：栈不存在前置条件：栈不存在 输入：无输入：无 功能：栈的初始化功能：栈的初始化 输出：无输出：无 后置条件：构造一个空栈后置条件：构造一个空栈 4.2 栈栈数据结构与算法数据结构与算法电子工业出版社电子工业出版社DestroyStack 前置条件：栈已存在前置条件：栈已存在 输入：无输入：无 功能：销毁栈功能：销毁栈 输出：无输出：无 后置条

11、件：释放栈所占用的存储空间后置条件：释放栈所占用的存储空间Push 前置条件：栈已存在前置条件：栈已存在 输入：元素值输入：元素值x 功能：在栈顶插入一个元素功能：在栈顶插入一个元素x 输出：如果插入不成功，抛出异常输出：如果插入不成功，抛出异常 后置条件：如果插入成功，栈顶增加了一个元素后置条件：如果插入成功，栈顶增加了一个元素栈的抽象数据类型定义栈的抽象数据类型定义 4.2 栈栈数据结构与算法数据结构与算法电子工业出版社电子工业出版社Pop 前置条件：栈已存在前置条件：栈已存在 输入：无输入：无 功能：删除栈顶元素功能：删除栈顶元素 输出：如果删除成功，返回被删元素值，否则，抛出异常输出：

12、如果删除成功，返回被删元素值，否则，抛出异常 后置条件：如果删除成功，栈减少了一个元素后置条件：如果删除成功，栈减少了一个元素GetTop 前置条件：栈已存在前置条件：栈已存在 输入：无输入：无 功能：读取当前的栈顶元素功能：读取当前的栈顶元素 输出：若栈不空，返回当前的栈顶元素值输出：若栈不空，返回当前的栈顶元素值 后置条件：栈不变后置条件：栈不变栈的抽象数据类型定义栈的抽象数据类型定义 4.2 栈栈数据结构与算法数据结构与算法电子工业出版社电子工业出版社Empty 前置条件：栈已存在前置条件：栈已存在 输入：无输入：无 功能：判断栈是否为空功能：判断栈是否为空 输出：如果栈为空，返回输出：

13、如果栈为空，返回1，否则，返回，否则，返回0 后置条件：栈不变后置条件：栈不变endADT栈的抽象数据类型定义栈的抽象数据类型定义 4.2 栈栈数据结构与算法数据结构与算法电子工业出版社电子工业出版社栈的顺序存储结构及实现栈的顺序存储结构及实现 顺序栈顺序栈栈的顺序存储结构栈的顺序存储结构如何改造数组实现栈的顺序存储？如何改造数组实现栈的顺序存储？ 0 1 2 3 4 5 6 7 8a1确定用数组的哪一端表示栈底。确定用数组的哪一端表示栈底。附设指针附设指针top指示栈顶元素在数组中的位置。指示栈顶元素在数组中的位置。 top 4.2 栈栈数据结构与算法数据结构与算法电子工业出版社电子工业出版

14、社出栈：出栈：top减减1进栈：进栈：top加加1栈空：栈空：top= - -1 0 1 2 3 4 5 6 7 8a1topa2topa3top栈满：栈满：top= MAX_SIZE- -1栈的顺序存储结构及实现栈的顺序存储结构及实现 4.2 栈栈数据结构与算法数据结构与算法电子工业出版社电子工业出版社顺序栈的存储结构定义：顺序栈的存储结构定义：const int StackSize = 10; /假定栈元素最多假定栈元素最多10个个typedef int DataType; /DataType为栈元素的数据类型为栈元素的数据类型typedef struct DataType dataSta

15、ckSize; /存放栈元素的数组存放栈元素的数组 int top; /栈顶指针，为栈顶元素在数组中的下标栈顶指针，为栈顶元素在数组中的下标 SeqStack; 4.2 栈栈数据结构与算法数据结构与算法电子工业出版社电子工业出版社顺序栈的实现顺序栈的实现入栈入栈void Push(SeqStack &S, DataType x) if (S.top = StackSize - 1) printf(上溢上溢); exit(-1); S.data+S.top = x;操作接口：操作接口： void Push(SeqStack &S, DataType x);时间复杂度？时间复杂度？

16、data+top = x 4.2 栈栈数据结构与算法数据结构与算法电子工业出版社电子工业出版社顺序栈的实现顺序栈的实现出栈出栈DataType Pop(SeqStack &S) if (S.top = -1) printf(下溢下溢); exit(-1); x = S.dataS.top-; return x;操作接口：操作接口： DataType Pop(SeqStack &S);时间复杂度？时间复杂度？ 4.2 栈栈数据结构与算法数据结构与算法电子工业出版社电子工业出版社两栈共享空间两栈共享空间 解决方案解决方案1：直接解决：为每个栈开辟一个数组空间。直接解决：为每个栈开辟

17、一个数组空间。 解决方案解决方案2： 顺序栈单向延伸顺序栈单向延伸使用一个数组来存储两个栈使用一个数组来存储两个栈在一个程序中需要在一个程序中需要同时同时使用具有使用具有相同相同数据类型的数据类型的两个栈两个栈，如何顺序存储这两个栈？如何顺序存储这两个栈？会出现什么问题？如何解决？会出现什么问题？如何解决？ 4.2 栈栈数据结构与算法数据结构与算法电子工业出版社电子工业出版社两栈共享空间：两栈共享空间：使用一个数组来存储两个栈，让一个使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，两个栈从各自的端点向中间延伸。

18、的末端，两个栈从各自的端点向中间延伸。两栈共享空间两栈共享空间 4.2 栈栈数据结构与算法数据结构与算法电子工业出版社电子工业出版社栈栈1的底固定在下标为的底固定在下标为0的一端；的一端；栈栈2的底固定在下标为的底固定在下标为StackSize-1的一端。的一端。 top1和和top2分别为栈分别为栈1和栈和栈2的栈顶指针；的栈顶指针；Stack_Size为整个数组空间的大小（图中用为整个数组空间的大小（图中用S表示）；表示）；a1 a2 aitop10 1 2 S-1两栈共享空间两栈共享空间 top2bj b2 b1栈栈1底底栈栈2底底 4.2 栈栈数据结构与算法数据结构与算法电子工业出版社

19、电子工业出版社top1= -1什么时候栈什么时候栈1为空？为空？a1 a2 aitop10 1 2 S-1两栈共享空间两栈共享空间 top2bj b2 b1top1 4.2 栈栈数据结构与算法数据结构与算法电子工业出版社电子工业出版社top1= -1什么时候栈什么时候栈1为空？为空？a1 a2 aitop10 1 2 S-1两栈共享空间两栈共享空间 top2bj b2 b1什么时候栈什么时候栈2为空？为空？top2top2= Stack_Size 4.2 栈栈数据结构与算法数据结构与算法电子工业出版社电子工业出版社top1= -1什么时候栈什么时候栈1为空？为空？a1 a2 aitop10 1

20、 2 S-1两栈共享空间两栈共享空间 top2bj b2 b1什么时候栈什么时候栈2为空？为空？top2= Stack_Size什么时候栈满？什么时候栈满？top2= top1+1 4.2 栈栈数据结构与算法数据结构与算法电子工业出版社电子工业出版社两栈共享空间的存储结构定义：两栈共享空间的存储结构定义：const int StackSize = 10; /假设两个栈最多假设两个栈最多10个元素个元素typedef int DataType; / DataType为两个栈的数据类型为两个栈的数据类型typedef struct DataType dataStackSize; /存放两个栈的数组

21、存放两个栈的数组 int top1, top2; /各自栈顶元素在数组中的下标各自栈顶元素在数组中的下标 BothStack; 4.2 栈栈数据结构与算法数据结构与算法电子工业出版社电子工业出版社1. 如果栈满，则抛出上溢异常；如果栈满，则抛出上溢异常；2. 判断是插在栈判断是插在栈1还是栈还是栈2； 2.1 若在栈若在栈1插入，则插入，则 2.1.1 top1加加1; 2.1.2 在在top1处填入处填入x； 2.2 若在栈若在栈2插入，则插入，则 2.2.1 top2减减1; 2.2.2 在在top2处填入处填入x；两栈共享空间的实现两栈共享空间的实现插入插入 操作接口：操作接口：void

22、 Push(int i, DataType x) ; 4.2 栈栈数据结构与算法数据结构与算法电子工业出版社电子工业出版社1. 若是在栈若是在栈1删除，则删除，则 1.1 若栈若栈1为空栈，抛出下溢异常；为空栈，抛出下溢异常； 1.2 删除并返回栈删除并返回栈1的栈顶元素；的栈顶元素；2. 若是在栈若是在栈2删除，则删除，则 2.1 若栈若栈2为空栈，抛出下溢异常；为空栈，抛出下溢异常； 2.2 删除并返回栈删除并返回栈2的栈顶元素；的栈顶元素；两栈共享空间的实现两栈共享空间的实现删除删除 操作接口：操作接口：DataType Pop(int i) ; 4.2 栈栈数据结构与算法数据结构与算法

23、电子工业出版社电子工业出版社栈的链接存储结构及实现栈的链接存储结构及实现 链栈：链栈：栈的链接存储结构栈的链接存储结构firsta1a2anai链栈需要加头结点吗？链栈需要加头结点吗？如何改造链表实现栈的链接存储？如何改造链表实现栈的链接存储？将哪一端作为栈顶？将哪一端作为栈顶？ 将链头作为栈顶，方便操作。将链头作为栈顶，方便操作。链栈不需要附设头结点。链栈不需要附设头结点。 4.2 栈栈数据结构与算法数据结构与算法电子工业出版社电子工业出版社栈的链接存储结构及实现栈的链接存储结构及实现 栈顶栈顶栈底栈底链栈：链栈：栈的链接存储结构栈的链接存储结构topanan-1a1firsta1a2ana

24、i两种示意图在内存中对两种示意图在内存中对应同一种状态，启示？应同一种状态，启示？topa1an-1an栈顶栈顶栈底栈底 4.2 栈栈数据结构与算法数据结构与算法电子工业出版社电子工业出版社void Push(Node *top, DataType x) s = (Node *)malloc(sizeof(Node); s-data = x; s-next = top; top = s;topanan-1a1链栈的实现链栈的实现插入插入 xstop操作接口：操作接口： void Push(DataType x); 为什么没有判断栈满？为什么没有判断栈满？ 4.2 栈栈数据结构与算法数据结构与算

25、法电子工业出版社电子工业出版社DataType Pop(Node *top) if (top = NULL) printf(下溢下溢); exit(-1); x = top-data; p = top; top = top-next; free(p); return x;链栈的实现链栈的实现插入插入操作接口：操作接口： DataType Pop( ); topanan-1a1topp top+可以吗？可以吗？ 4.2 栈栈数据结构与算法数据结构与算法电子工业出版社电子工业出版社顺序栈和链栈的比较顺序栈和链栈的比较时间性能：时间性能：相同，都是常数时间相同，都是常数时间O(1)。空间性能：空间性

26、能：顺序栈：有元素个数的限制和空间浪费的问题。顺序栈：有元素个数的限制和空间浪费的问题。链栈：没有栈满的问题，只有当内存没有可用空链栈：没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针间时才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构性开销。域，从而产生了结构性开销。 总之，当栈的使用过程中元素总之，当栈的使用过程中元素个数变化个数变化较大时，用较大时，用链栈是适宜的，反之，应该采用顺序栈。链栈是适宜的，反之，应该采用顺序栈。 4.2 栈栈数据结构与算法数据结构与算法电子工业出版社电子工业出版社队列的逻辑结构队列的逻辑结构p 队列：队列：只允许在只允

27、许在一端一端进行插入操作，而进行插入操作，而另一端另一端进进行删除操作的线性表。行删除操作的线性表。p 允许插入（也称入队、进队）的一端称为队尾，允许插入（也称入队、进队）的一端称为队尾，允许删除（也称出队）的一端称为队头。允许删除（也称出队）的一端称为队头。p 空队列：空队列：不含任何数据元素的队列。不含任何数据元素的队列。（a1, a2, , an）队尾队尾队头队头 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社队列的操作特性：队列的操作特性：先进先出先进先出a1a2a3入队入队队尾队尾队头队头出队出队队头队头队列的逻辑结构队列的逻辑结构 4.3 队列队列数据结构

28、与算法数据结构与算法电子工业出版社电子工业出版社队列的抽象数据类型定义队列的抽象数据类型定义 ADT Queue Data 队列中元素具有相同类型及先进先出特性，队列中元素具有相同类型及先进先出特性， 相邻元素具有前驱和后继关系相邻元素具有前驱和后继关系Operation InitQueue 前置条件：队列不存在前置条件：队列不存在 输入：无输入：无 功能：初始化队列功能：初始化队列 输出：无输出：无 后置条件：创建一个空队列后置条件：创建一个空队列 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社 DestroyQueue 前置条件：队列已存在前置条件：队列已存在 输

29、入：无输入：无 功能：销毁队列功能：销毁队列 输出：无输出：无 后置条件：释放队列所占用的存储空间后置条件：释放队列所占用的存储空间 EnQueue 前置条件：队列已存在前置条件：队列已存在 输入：元素值输入：元素值x 功能：在队尾插入一个元素功能：在队尾插入一个元素 输出：如果插入不成功，抛出异常输出：如果插入不成功，抛出异常 后置条件：如果插入成功，队尾增加了一个元素后置条件：如果插入成功，队尾增加了一个元素队列的抽象数据类型定义队列的抽象数据类型定义 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社 DeQueue 前置条件：队列已存在前置条件：队列已存在 输入：

30、无输入：无 功能：删除队头元素功能：删除队头元素 输出：如果删除成功，返回被删元素值输出：如果删除成功，返回被删元素值 后置条件：如果删除成功，队头减少了一个元素后置条件：如果删除成功，队头减少了一个元素 GetQueue 前置条件：队列已存在前置条件：队列已存在 输入：无输入：无 功能：读取队头元素功能：读取队头元素 输出：若队列不空，返回队头元素输出：若队列不空，返回队头元素 后置条件：队列不变后置条件：队列不变队列的抽象数据类型定义队列的抽象数据类型定义 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社Empty 前置条件：队列已存在前置条件：队列已存在 输入：无

31、输入：无 功能：判断队列是否为空功能：判断队列是否为空 输出：如果队列为空，返回输出：如果队列为空，返回1，否则，返回，否则，返回0 后置条件：队列不变后置条件：队列不变endADT队列的抽象数据类型定义队列的抽象数据类型定义 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社0 1 2 3 4 入队入队出队出队队列的顺序存储结构及实现队列的顺序存储结构及实现 顺序队列顺序队列队列的顺序存储结构队列的顺序存储结构如何改造数组实现队列的顺序存储？如何改造数组实现队列的顺序存储？例：例：a1a2a3a4依次入队依次入队a1a2a3a4rearrear rear rear入队操

32、作时间性能为入队操作时间性能为O(1) 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社如何改造数组实现队列的顺序存储？如何改造数组实现队列的顺序存储？例：例：a1a2依次出队依次出队队列的顺序存储结构及实现队列的顺序存储结构及实现 0 1 2 3 4 入队入队出队出队a1a2a3a4rear 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社如何改造数组实现队列的顺序存储？如何改造数组实现队列的顺序存储？例：例：a1a2依次出队依次出队队列的顺序存储结构及实现队列的顺序存储结构及实现 0 1 2 3 4 入队入队出队出队a2a3a4rear 4.

33、3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社如何改造数组实现队列的顺序存储？如何改造数组实现队列的顺序存储？例：例：a1a2依次出队依次出队队列的顺序存储结构及实现队列的顺序存储结构及实现 0 1 2 3 4 入队入队出队出队a3a4rear出队操作时间性能为出队操作时间性能为O(n) 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社队列的顺序存储结构及实现队列的顺序存储结构及实现 如何改进出队的时间性能？如何改进出队的时间性能？放宽队列的所有元素必须存储在数组的前放宽队列的所有元素必须存储在数组的前n个单元这一个单元这一条件条件 ，只要求队列的

34、元素存储在数组中连续的位置。，只要求队列的元素存储在数组中连续的位置。设置队头、队尾两个指针设置队头、队尾两个指针 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社队列的顺序存储结构及实现队列的顺序存储结构及实现 0 1 2 3 4 入队入队出队出队例：例：a1a2a3a4依次入队依次入队a1a2a3a4rearrear rear rear入队操作时间性能仍为入队操作时间性能仍为O(1)front rear约定：队头指针约定：队头指针front指向队头元素的前一个位置，指向队头元素的前一个位置， 队尾指针队尾指针rear指向队尾元素。指向队尾元素。 4.3 队列队列数据

35、结构与算法数据结构与算法电子工业出版社电子工业出版社例：例：a1a2依次出队依次出队队列的顺序存储结构及实现队列的顺序存储结构及实现 0 1 2 3 4 入队入队出队出队a1a2a3a4rearfront front front出队操作时间性能提高为出队操作时间性能提高为O(1) 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社例：例：a1a2依次出队依次出队队列的顺序存储结构及实现队列的顺序存储结构及实现 0 1 2 3 4 入队入队出队出队a3a4rearfront队列的移动有什么特点？队列的移动有什么特点？ 4.3 队列队列数据结构与算法数据结构与算法电子工业出版

36、社电子工业出版社例：例：a1a2依次出队依次出队队列的顺序存储结构及实现队列的顺序存储结构及实现 0 1 2 3 4 入队入队出队出队a3a4rearfront整个队列向数组下标较大方向移动整个队列向数组下标较大方向移动单向移动性单向移动性 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社假溢出：假溢出：当元素被插入到数组中下标最大的位置上之当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，尽管此时数组的低端还有后，队列的空间就用尽了，尽管此时数组的低端还有空闲空间，这种现象叫做假溢出。空闲空间，这种现象叫做假溢出。队列的顺序存储结构及实现队列的顺序存储结构

37、及实现 继续入队会出现什么情况？继续入队会出现什么情况？0 1 2 3 4 入队入队出队出队a3a4rearfronta5rear 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社循环队列：循环队列：将存储队列的数组头尾相接。将存储队列的数组头尾相接。队列的顺序存储结构及实现队列的顺序存储结构及实现 如何解决假溢出？如何解决假溢出？0 1 2 3 4 入队入队出队出队a3a4fronta5rearreara6 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社不存在物理的循环结构，用软件方法实现。不存在物理的循环结构，用软件方法实现。求模求模：（：

38、（41）mod 50队列的顺序存储结构及实现队列的顺序存储结构及实现 如何实现循环队列？如何实现循环队列？0 1 2 3 4 入队入队出队出队a3a4frontreara6 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社如何判断循环队列队空？如何判断循环队列队空？队空的临界状态队空的临界状态队列的顺序存储结构及实现队列的顺序存储结构及实现 0 1 2 3 4 入队入队出队出队a3rearfront 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社如何判断循环队列队空？如何判断循环队列队空？执行出队操作执行出队操作队空：队空：front=rear

39、队列的顺序存储结构及实现队列的顺序存储结构及实现 0 1 2 3 4 入队入队出队出队a3front rearfront 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社如何判断循环队列队满？如何判断循环队列队满？队满的临界状态队满的临界状态队列的顺序存储结构及实现队列的顺序存储结构及实现 0 1 2 3 4 入队入队出队出队a3a4fronta5reara6 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社如何判断循环队列队满？如何判断循环队列队满？执行入队操作执行入队操作队满：队满：front=rear队列的顺序存储结构及实现队列的顺序存储结

40、构及实现 0 1 2 3 4 入队入队出队出队a3a4fronta5reara6reara7 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社方法一：方法一：附设一个存储队列中元素个数的变量附设一个存储队列中元素个数的变量num，当当num=0时队空，当时队空，当num=QueueSize时为队满；时为队满；方法二：方法二：修改队满条件，浪费一个元素空间，队满时修改队满条件，浪费一个元素空间，队满时数组中只有一个空闲单元数组中只有一个空闲单元；方法三：方法三：设置标志设置标志flag，当当front=rear且且flag=0时为队时为队空，当空，当front=rear且

41、且flag=1时为队满。时为队满。如何确定不同的队空、队满的判定条件？如何确定不同的队空、队满的判定条件？为什么要将队空和队满的判定条件分开？为什么要将队空和队满的判定条件分开？队列的顺序存储结构及实现队列的顺序存储结构及实现 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社队满的条件：队满的条件：(rear+1) mod QueueSize=front队列的顺序存储结构及实现队列的顺序存储结构及实现 0 1 2 3 4 入队入队rearfronta3a4fronta5reara6出队出队 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社循环队列

42、的存储结构定义：循环队列的存储结构定义：const int QueueSize = 10; /定义数组的最大长度定义数组的最大长度typedef int DataType; / DataType为队列元素的数据类型为队列元素的数据类型typedef struct DataType dataQueueSize; /存放队列元素的数组存放队列元素的数组 int front, rear; /队头和队尾指针队头和队尾指针 CirQueue; 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社void EnQueue(CirQueue &Q, DataType x) if

43、(Q.rear + 1) % QueueSize = Q.front) printf(上溢上溢); exit(-1); Q.rear = (Q.rear + 1) % QueueSize; Q.dataQ.rear = x; 循环队列的实现循环队列的实现入队入队0 1 2 3 4 入队入队出队出队a3a4rearfronta5rear 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社0 1 2 3 4 入队入队a4a5a6出队出队DataType DeQueue(CirQueue &Q) if (Q.rear = Q.front) printf(下溢下溢); e

44、xit(-1); Q.front = (Q.front + 1) % QueueSize; return Q.dataQ.front; 循环队列的实现循环队列的实现出队出队frontrearfronta3 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社DataType GetFront(CirQueue &Q) if (Q.rear = Q.front) printf(下溢下溢); exit(-1); i = (Q.front + 1) % QueueSize; return Q.datai;循环队列的实现循环队列的实现读队头元素读队头元素0 1 2 3 4

45、入队入队a4a5a6出队出队frontreara3 i 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社队列的链接存储结构及实现队列的链接存储结构及实现 链队列：链队列：队列的链接存储结构队列的链接存储结构 队头指针即为链表的头指针队头指针即为链表的头指针firsta1a2an如何改造单链表实现队列的链接存储？如何改造单链表实现队列的链接存储？rearfront 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社队列的链接存储结构及实现队列的链接存储结构及实现 非空链队列非空链队列fronta1a2anrear空链队列空链队列frontrear 4

46、.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社链队列的存储结构定义：链队列的存储结构定义：typedef int DataType; / DataType为队列元素的数据类型为队列元素的数据类型typedef struct Node /定义链队列的结点结构定义链队列的结点结构 DataType data; Node *next; Node;typedef struct /定义链队列定义链队列 Node *front, *rear; LinkQueue; 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社操作接口：操作接口： LinkQueue( )

47、; 算法描述：算法描述：void InitQueue(LinkQueue &Q) s = (Node *)malloc(sizeof(Node); s-next = NULL; Q.front = Q.rear = s; 链队列的实现链队列的实现队列的初始化队列的初始化frontrear 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社 xs链队列的实现链队列的实现入队入队操作接口：操作接口： void EnQueue(DataType x);fronta1anrearrearfront xsrearrear算法描述：算法描述：s-next=NULL;rear-

48、next=s; rear=s;如何没有头结点会怎样？如何没有头结点会怎样？ 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社 xs链队列的实现链队列的实现入队入队操作接口：操作接口： void EnQueue(DataType x);fronta2anrearrear算法描述：算法描述：s-next=NULL;rear-next=s; rear=s;如何没有头结点会怎样？如何没有头结点会怎样？a1 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社链队列的实现链队列的实现入队入队操作接口：操作接口： void EnQueue(DataType x)

49、;front=rear=NULL xsrear算法描述：算法描述：s-next=NULL;rear=s; front=s;如何没有头结点会怎样？如何没有头结点会怎样？front算法描述：算法描述：s-next=NULL;rear-next=s; rear=s; 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社链队列的实现链队列的实现入队入队void EnQueue(LinkQueue &Q, DataType x) s = (Node *)malloc(sizeof(Node); s-data = x; s-next = NULL; Q.rear-next =

50、s; Q.rear = s; 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社链队列的实现链队列的实现出队出队fronta1a2anrearp算法描述：算法描述：p=front-next; front-next=p-next; 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社链队列的实现链队列的实现出队出队fronta1a2anrearp考虑边界情况：队列中只有一个元素？考虑边界情况：队列中只有一个元素？fronta1prearrear算法描述：算法描述：if (p-next = NULL) rear = front;如何判断边界情况？如何判断边界情况？ 4.3 队列队列数据结构与算法数据结构与算法电子工业出版社电子工业出版社DataType DeQueue(LinkQueue &Q)