数据结构第3章栈和队列

1、机电工程学院机电工程学院程艺苑程艺苑数据结构数据结构教学内容教学内容 绪论绪论第第1 1章章 线性表线性表第第2 2章章 栈和队列栈和队列第第3 3章章 串串第第4 4章章 数组和广义表数组和广义表第第5 5章章 树和二叉树树和二叉树第第6 6章章 图图第第7 7章章 查找查找第第8 8章章 排序排序第第9 9章章3 3.1 .1 栈栈3 3.2 .2 栈的应用举例栈的应用举例3 3.3 .3 队列队列第第3章章 栈和队列栈和队列栈和队列是两种应用非常广泛的数据结构栈和队列是两种应用非常广泛的数据结构，它，它们都来自线性表数据结构，们都来自线性表数据结构，都是都是“操作受限操作受限”的线的线性

2、表性表。与线性表相比，它们的插入和删除操作受更与线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为多的约束和限定，故又称为限定性的线性表结构限定性的线性表结构。u线性表允许在表内线性表允许在表内任一位置任一位置进行插入和删除；进行插入和删除；u栈只允许在栈只允许在表尾一端表尾一端进行插入和删除；进行插入和删除；u队列只允许在队列只允许在表尾一端表尾一端进行进行插入插入，在，在表头一端表头一端进行进行删除删除。3.1 栈栈3.1.1 栈的基本概念栈的基本概念1 栈的概念栈的概念u栈栈(Stack)：是限制在表的一端进行插入和删除是限制在表的一端进行插入和删除操作的线性表。操作的线性表。

3、u也称为后进先出也称为后进先出LIFO (Last In First Out)或先进或先进后出后出FILO (First In Last Out)线性线性表。表。 l 设栈S=(a1，a2，an)，则a1称为栈底元素，an为栈顶元素。 栈中元素按a1，a2，an的次序进栈，出栈的第一个元素应为栈顶元素。即栈的修改是按后进先出的原则进行的。a1a2aian basetop进栈（进栈（push）出栈出栈(pop)u栈顶栈顶(Top)：允许进行插入、删除操作的一端，又允许进行插入、删除操作的一端，又称为称为表尾表尾。用栈顶指针。用栈顶指针(top)来指示栈顶元素来指示栈顶元素。u栈底栈底(Base)

4、：是固定端，又称为是固定端，又称为表头表头。u空栈空栈：当表中没有元素时称为空栈当表中没有元素时称为空栈 例例1：家里吃饭的碗，通常在洗干净后一个一个家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。面的那只碗。 例例2：在建筑工地上，使用的砖块从底往上一层在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地一层地码放，在使用时，将从最上面一层一层地拿取。拿取。ADT Stack数据对象：数据对象：D =

5、 ai|aiElemSet, i=1,2,n，n0 数据关系：数据关系：R =|ai-1，aiD, i=2,3,n 基本操作：基本操作：InitStack(&S) 操作结果：构造一个空栈操作结果：构造一个空栈 S S。DestroyStack(&S)初始条件：栈初始条件：栈 S S 已存在。已存在。操作结果：栈操作结果：栈 S S 被销毁。被销毁。2 栈的抽象数据类型定义栈的抽象数据类型定义 ClearStack(&S)初始条件：栈初始条件：栈 S S 已存在。已存在。操作结果：将操作结果：将 S S 清为空栈。清为空栈。StackEmpty(S)初始条件：栈初始条件：

6、栈 S S 已存在。已存在。操作结果：若栈操作结果：若栈 S S 为空栈，则返回为空栈，则返回TRUETRUE，否则返回，否则返回 FALSEFALSE。StackLength(S)初始条件：栈初始条件：栈 S S 已存在。已存在。操作结果：返回栈操作结果：返回栈 S S 中元素个数，即栈的长度。中元素个数，即栈的长度。 GetTop(S, &e)初始条件：栈初始条件：栈 S S 已存在且非空。已存在且非空。操作结果：用操作结果：用 e e 返回返回S S的栈顶元素。的栈顶元素。 Push(&S, e)初始条件：栈初始条件：栈 S S 已存在。已存在。操作结果：插入元素操作结果

7、：插入元素 e e 为新的栈顶元素。为新的栈顶元素。Pop(&S, &e)初始条件：栈初始条件：栈 S S 已存在且非空。已存在且非空。操作结果：删除操作结果：删除 S S 的栈顶元素，并用的栈顶元素，并用 e e 返回其值。返回其值。 StackTraverse(S, visit( )初始条件：栈初始条件：栈 S S 已存在且非空，已存在且非空，visit( )visit( )为元素的为元素的访问函数。访问函数。操作结果：从栈底到栈顶依次对操作结果：从栈底到栈顶依次对S S的每个元素调用函的每个元素调用函数数visit( )visit( )，一旦，一旦visit( )visi

8、t( )失败，则操作失败。失败，则操作失败。 ADT Stack 和线性表类似，栈也有两种存储方法：和线性表类似，栈也有两种存储方法：栈的顺序存储结构栈的顺序存储结构顺序栈；顺序栈；栈的链式存储结构栈的链式存储结构链栈。链栈。3.1.2 栈的表示和实现栈的表示和实现u顺序栈，顺序栈，即栈的顺序存储结构，是利用即栈的顺序存储结构，是利用一组地址一组地址连续的存储单元连续的存储单元依次存放自栈底到栈顶的数据元素。依次存放自栈底到栈顶的数据元素。u设置指针设置指针toptop指向栈顶元素在顺序栈中的位置，通指向栈顶元素在顺序栈中的位置，通常习惯做法是以常习惯做法是以top=0top=0表示空栈表示空

9、栈。u栈在使用的过程中所需最大空间的大小很难估计，栈在使用的过程中所需最大空间的大小很难估计，一般初始化设空栈时不限定栈的最大容量。一般初始化设空栈时不限定栈的最大容量。u一般先分配一个基本容量，然后应用过程中，栈一般先分配一个基本容量，然后应用过程中，栈的空间不够使用时再逐段扩大。的空间不够使用时再逐段扩大。3.1.2.1 栈的顺序存储表示栈的顺序存储表示顺序栈的结构定义：顺序栈的结构定义：#define STACK_INIT_SIZE 100; #define STACK_INIT_SIZE 100; / / 存储空间初始分配量存储空间初始分配量 #define STACKINCREMEN

10、T 10; #define STACKINCREMENT 10; / / 存储空间分配增量存储空间分配增量 typedeftypedef structstruct SElemTypeSElemType * *base; base; / / 存储空间基址存储空间基址 SElemTypeSElemType * *top; top; / / 栈顶指针栈顶指针intint stacksizestacksize; ; / / 当前已分配的存储空间当前已分配的存储空间 SqStackSqStack; ; StacksizeStacksize：栈的当前可使用的最大容量；：栈的当前可使用的最大容量；BaseB

11、ase：栈底指针，顺序栈中始终指向栈底位置，：栈底指针，顺序栈中始终指向栈底位置，basebase的的值为值为NULLNULL，则表明栈结构不存在；，则表明栈结构不存在；TopTop：栈顶指针，初值指向栈底，：栈顶指针，初值指向栈底，当当top=basetop=base时，可以以时，可以以作为栈空的标记作为栈空的标记。非空栈中非空栈中toptop指针始终在栈顶元素的下一指针始终在栈顶元素的下一个位置个位置。top=0123450栈空栈空栈顶指针栈顶指针top,指向实际栈顶指向实际栈顶后的空位置，初值为后的空位置，初值为0top123450进栈进栈Atop出栈出栈栈满栈满BCDEF设数组大小为设

12、数组大小为Mtop=0,栈空，此时出栈，则栈空，此时出栈，则下溢下溢（underflow)top=M,栈满，此时入栈，则栈满，此时入栈，则上溢上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空栈空进栈：进栈：top加加1出栈：出栈：top减减1顺序栈的基本操作：顺序栈的基本操作：void InitStack (SqStack &S); /构造一个空栈构造一个空栈S。void DestroyStack (SqStack &S); /销毁栈销毁栈S，S 不再存在。不再存在。void ClearStack (SqSt

13、ack &S); /将将 S 置为空栈。置为空栈。bool StackEmpty (SqStack S); /若栈若栈 S 为空栈。为空栈。int StackLength (SqStack S); /返回返回S的元素个数，即栈的长度。的元素个数，即栈的长度。bool GetTop (SqStack S, SElemType &e); /若栈不空，则用若栈不空，则用 e 返回返回S的的栈顶元素，并返回栈顶元素，并返回TRUE；否则返回；否则返回 FALSE。bool Push (SqStack &S, SElemType e); /若栈的存储空间不满，则插入若栈的存储空间

14、不满，则插入元素元素 e ，并返回，并返回 TRUE；否则返回；否则返回FALSE。bool Pop (SqStack &S, SElemType &e); /若栈不空，则删除若栈不空，则删除S的栈顶元的栈顶元素，用素，用e返回其值，并返回返回其值，并返回TRUE；否则返回；否则返回FALSE。void StackTraverse(SqStack S, Status (*visit()； /依次对依次对S的每个元的每个元素调用函数素调用函数 visit( )，一旦，一旦 visit( )失败，操作失败。失败，操作失败。1 1 栈的初始化栈的初始化Status InitStack

15、 (SqStack &S) / 构造一个空栈构造一个空栈 SS.base=(SElemType *)malloc (STACK_INIT_SIZE*sizeof(SElemType);if(!S.base) exit(OVERFLOW); / 存储分配失败存储分配失败S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK; /InitStack 2 2 取栈顶元素取栈顶元素 Status GetTop (SqStack S, SElemType &e) / 若栈不空，则用若栈不空，则用 e 返回返回S的栈顶元素，并返回的栈顶

16、元素，并返回OKif (S.top = S.base ) return ERROR; / 空栈空栈e = *(S.top-1); / 返回非空栈中栈顶元素返回非空栈中栈顶元素return OK; /GetTop注意：注意： top top栈顶指针始终在栈顶元素的下一个位置上。栈顶指针始终在栈顶元素的下一个位置上。3压栈(元素进栈)lStatus Push (SqStack &S, SElemType e) / 插入元素 e 为新的栈顶元素lif(S.top-S.base=S.stacksize) /栈满，追加存储空间lS.base=(SElemType *)realloc(S.base

17、,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);l if(!S.base) exit(OVERFLOW);/ 存储分配失败lS.top=S.base+S.stacksize;lS.stacksize +=STACKINCREMENT;l*(S.top+) = e; / 插入新的元素lreturn OK;l /Push4 弹栈(元素出栈)lStatus Pop (Stack &S, ElemType &e) / 栈不空，删除S的栈顶元素，用e返回其值，并返回 OK；否则返回 ERRORlif (S.top = S.base) ret

18、urn ERROR;/空栈le = *(-S.top); /返回非空栈中栈顶元素lreturn OK;l /Pop栈的栈的链式存储结构链式存储结构称为链栈，是运算受限的单链表。其插入称为链栈，是运算受限的单链表。其插入和删除操作只能在表头位置上进行。因此，链栈没有必要像和删除操作只能在表头位置上进行。因此，链栈没有必要像单链表那样附加头结点，栈顶指针单链表那样附加头结点，栈顶指针top就是链表的头指针。就是链表的头指针。3.1.2.2 3.1.2.2 栈的链式存储表示栈的链式存储表示空栈空栈top 非空栈非空栈top a4 a3 a1 a2链栈的链栈的结点类型说明如下：结点类型说明如下：typ

19、edef struct Stack_Node ElemType data ; struct Stack_Node *next ; Stack_Node ;入栈算法入栈算法 .栈底栈底toptopxp出栈算法出栈算法top .栈底栈底topq空间性能：空间性能：顺序栈：顺序栈：有元素个数的限制和空间浪费的问题。有元素个数的限制和空间浪费的问题。链栈：链栈：没有栈满的问题，只有当内存没有可用没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个空间时才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构性开销。指针域，从而产生了结构性开销。总之，当栈的使用过程中总之，当栈

20、的使用过程中元素个数变化较大元素个数变化较大时，时，用链栈是适宜的，反之，应该采用顺序栈。用链栈是适宜的，反之，应该采用顺序栈。顺序栈和链栈的比较顺序栈和链栈的比较：3.2 栈的应用栈的应用 由于栈具有的由于栈具有的“后进先出后进先出”的固有特性，因此，栈成的固有特性，因此，栈成为程序设计中常用的工具和数据结构。以下是几个栈应用的为程序设计中常用的工具和数据结构。以下是几个栈应用的例子。例子。1 数制转换数制转换2 括号匹配问题括号匹配问题3 表达式求值表达式求值4 栈与递归调用的实现栈与递归调用的实现3.2.1 数制转换数制转换 十进制整数十进制整数N向其它进制数向其它进制数d(二二、八八、

21、十六十六) )的转换是计算机实现计算的基本问题。的转换是计算机实现计算的基本问题。该转换法则对应于一个简单算法原理该转换法则对应于一个简单算法原理: :N = (N div d)d + N mod d其中：其中：div为整除运算为整除运算, ,mod为求余运算。为求余运算。例如：例如：（1348)1348)1010 = (2504) = (2504)8 8 ，其运算过程如下：，其运算过程如下： 采用顺序栈的方式实现任意一个非负十进制整数转换为与采用顺序栈的方式实现任意一个非负十进制整数转换为与其等值的八进制数。其等值的八进制数。 void conversion () /算法算法3.1InitS

22、tack(S); / 构造空栈构造空栈scanf(“%d”,N);/ 输入一个十进制数输入一个十进制数while(N) Push(S,N%8);/ “余数余数”入栈入栈 N = N/8;/ 非零非零“商商”继续运算继续运算 while (!StackEmpty(s)/ 和和“求余求余”所得相逆的顺序输出八进制的各位数所得相逆的顺序输出八进制的各位数Pop(S,e);printf(“%d”,e); / while / conversion3.2.2 括号匹配问题括号匹配问题 在文字处理软件或编译程序设计时，常常需要检查一在文字处理软件或编译程序设计时，常常需要检查一个字符串或一个表达式中的括号是

23、否相匹配个字符串或一个表达式中的括号是否相匹配?匹配思想：匹配思想：从左至右扫描一个字符串从左至右扫描一个字符串(或表达式或表达式)，则，则每个右每个右括号将与最近遇到的那个左括号相匹配括号将与最近遇到的那个左括号相匹配。则可以在从左至右。则可以在从左至右扫描过程中把所遇到的左括号存放到堆栈中。每当遇到一个扫描过程中把所遇到的左括号存放到堆栈中。每当遇到一个右括号时，就将它与栈顶的左括号右括号时，就将它与栈顶的左括号(如果存在如果存在)相匹配，同时相匹配，同时从栈顶删除该左括号。从栈顶删除该左括号。算法思想：算法思想：设置一个栈，当读到左括号时，左括号进栈。当设置一个栈，当读到左括号时，左括号

24、进栈。当读到右括号时，则从栈中弹出一个元素，与读到的左括号进读到右括号时，则从栈中弹出一个元素，与读到的左括号进行匹配，若匹配成功，继续读入；否则匹配失败，返回行匹配，若匹配成功，继续读入；否则匹配失败，返回FLASE。283.2.3 表达式求值表达式求值l表达式的组成表达式的组成操作数操作数(operand)(operand)：常数、变量。常数、变量。运算符运算符(operator)(operator)：算术运算符、关系运算符和逻辑运算符。算术运算符、关系运算符和逻辑运算符。界限符界限符(delimiter) (delimiter) ：左右括弧和表达式结束符。左右括弧和表达式结束符。l算术运

25、算的规则算术运算的规则先乘除后加减先乘除后加减先左后右先左后右先括弧内后括弧外先括弧内后括弧外例如：例如：4+24+2* *3-10/5=4+6-10/53-10/5=4+6-10/5 =10-10/5 =10-10/5 =10-2 =10-2 =8 =8算法的思想：算法的思想：设置两个工作栈设置两个工作栈l运算符栈运算符栈OPTROPTR，运算符栈的栈底为表达式的起始符运算符栈的栈底为表达式的起始符# #。l操作数栈操作数栈OPNDOPND，操作数栈为空栈。操作数栈为空栈。依次读入表达式中的每个字符依次读入表达式中的每个字符l若是若是操作数则进操作数则进OPNDOPND栈栈；l若是若是运算符

26、，则和运算符，则和OPTROPTR中的栈顶元素做比较再操作中的栈顶元素做比较再操作。若若运算符优先级高于运算符优先级高于OPTROPTR中的栈顶元素中的栈顶元素，则运算符入栈；则运算符入栈；若若运算符优先级低于运算符优先级低于OPTROPTR中的栈顶元素中的栈顶元素，则从则从OPNDOPND栈顶弹出两栈顶弹出两个操作数，与个操作数，与OPTROPTR中的栈顶元素做运算，并将运算结果入中的栈顶元素做运算，并将运算结果入OPNDOPND；若若运算符优先级等于运算符优先级等于OPTROPTR中的栈顶元素中的栈顶元素，则将则将OPTROPTR中的栈顶元中的栈顶元素出栈。素出栈。直至直至表达式求置完毕表

27、达式求置完毕。计算计算 2+4-3*6操作数操作数运算符运算符-12操作数操作数运算符运算符24#+操作数操作数运算符运算符6#-操作数操作数运算符运算符6#36*-操作数操作数运算符运算符6#18-3.2.4 栈与递归调用的实现栈与递归调用的实现 栈的另一个重要应用是在程序设计语言中实现递归调用。栈的另一个重要应用是在程序设计语言中实现递归调用。 递归调用：递归调用：一个函数一个函数( (或过程或过程) )直接或间接地调用自己本身，直接或间接地调用自己本身，简称递归简称递归(Recursive)。 递归递归是程序设计中的一个强有力的工具。因为递归函数结是程序设计中的一个强有力的工具。因为递归

28、函数结构清晰，程序易读，正确性很容易得到证明。构清晰，程序易读，正确性很容易得到证明。 例如：求例如：求n!Fact(n)=1 当当n=0时时 终止条件终止条件n*fact(n-1) 当当n0时时 递推规则递推规则l当一个函数在运行期间调用另一个函数时，在运行该被当一个函数在运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三件事：调用函数之前，需先完成三件事：将所有的将所有的实在参数、返回地址实在参数、返回地址等信息传递给等信息传递给被调用函数保存被调用函数保存；为被调用函数的为被调用函数的局部变量分配存储区局部变量分配存储区；将控制转移到被调用函数的入口将控制转移到被调用函数的入口

29、。l而从被调用函数返回调用函数之前，应该完成：而从被调用函数返回调用函数之前，应该完成：保存保存被调函数的被调函数的计算结果计算结果；释放释放被调函数的被调函数的数据区数据区；依照被调函数保存的返回地址将依照被调函数保存的返回地址将控制转移到调用函数控制转移到调用函数。l由于函数的运行规则是：后调用先返回，因此各函数占由于函数的运行规则是：后调用先返回，因此各函数占有的存储管理应实行有的存储管理应实行 栈式管理栈式管理 。r主程序主程序srrrs子过程子过程1rst子过程子过程2rst子过程子过程3 有有A,B,C三个塔座，三个塔座，A上套有上套有n个直径不同的圆盘，按直径从小到大叠个直径不同

30、的圆盘，按直径从小到大叠放，形如宝塔放，形如宝塔,编号编号1,2,3n。要求将要求将n个圆盘从个圆盘从A移到移到C，叠放顺序叠放顺序不变，移动过程中遵循下列原则：不变，移动过程中遵循下列原则：v每次只能移一个圆盘；每次只能移一个圆盘；v圆盘可在三个塔座上任意移动；圆盘可在三个塔座上任意移动；v任何时刻，每个塔座上不能将大盘压到小盘上。任何时刻，每个塔座上不能将大盘压到小盘上。Tower of HanoiTower of Hanoi问题问题l问题描述问题描述ABCl解决方法：解决方法：n=1n=1时，直接把圆盘从时，直接把圆盘从A A移到移到C C。n1n1时时l把上面把上面n-1n-1个圆盘从

31、个圆盘从A A移到移到B Bl然后将然后将n n号盘从号盘从A A移到移到C Cl将将n-1n-1个盘从个盘从B B移到移到C C。即把求解即把求解n n个圆盘的个圆盘的HanoiHanoi问题转化为求解问题转化为求解n-1n-1个圆盘的个圆盘的HanoiHanoi问题，依次类推，直至转化成只有一个圆盘的问题，依次类推，直至转化成只有一个圆盘的HanoiHanoi问题。问题。ABC1 1 队列的基本概念队列的基本概念 队列队列(Queue)：也是运算受限的线性表。是一种也是运算受限的线性表。是一种先进先进先出先出(First In First Out ，简称，简称FIFO)的线性表。只允许在的

32、线性表。只允许在表的一端进行插入，而在另一端进行删除表的一端进行插入，而在另一端进行删除。u 队首队首(front) ：允许进行删除的一端称为队首。允许进行删除的一端称为队首。u 队尾队尾(rear) ：允许进行插入的一端称为队尾。允许进行插入的一端称为队尾。3.3 队队 列列3.3.1 队列及其基本概念队列及其基本概念例例1 1：到医院看病，首先需要到挂号处挂号，然到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。后，按号码顺序救诊。例例2 2：乘坐公共汽车，应该在车站排队，车来后，乘坐公共汽车，应该在车站排队，车来后，按顺序上车。按顺序上车。例例3 3：在在WindowsWindow

33、s这类多任务的操作系统环境中，这类多任务的操作系统环境中，每个应用程序响应一系列的每个应用程序响应一系列的“消息消息”，像用户点，像用户点击鼠标；拖动窗口这些操作都会导致向应用程序击鼠标；拖动窗口这些操作都会导致向应用程序发送消息。为此，系统将为每个应用程序创建一发送消息。为此，系统将为每个应用程序创建一个队列，用来存放发送给该应用程序的所有消息，个队列，用来存放发送给该应用程序的所有消息，应用程序的处理过程就是不断地从队列中读取消应用程序的处理过程就是不断地从队列中读取消息，并依次给予响应。息，并依次给予响应。 队列中没有元素时称为空队列。在空队列中依次加入元素a1, a2, , an之后，

34、a1是队首元素，an是队尾元素。显然退出队列的次序也只能是a1, a2, , an ，即队列的修改是依先进先出的原则进行的。a1 , a2 , , an出队出队入队入队队尾队尾rear队首队首front2 队列的抽象数据类型定义队列的抽象数据类型定义ADT Queue 数据对象：数据对象：D = ai|aiElemSet, i=1, 2, , n, n = 0 数据关系：数据关系：R = | ai-1, aiD, i=2,3,n 约定约定a1端为队首，端为队首，an端为队尾。端为队尾。基本操作：基本操作： InitQueueInitQueue(&Q)(&Q) 操作结果：构造一个

35、空队列操作结果：构造一个空队列 Q Q。 DestroyQueueDestroyQueue(&Q)(&Q) 初始条件：队列初始条件：队列 Q Q 已存在。已存在。 操作结果：队列操作结果：队列 Q Q 被销毁，不再存在。被销毁，不再存在。 ClearQueueClearQueue(&Q)(&Q) 初始条件：队列初始条件：队列 Q Q 已存在。已存在。 操作结果：将操作结果：将 Q Q 清为空队列。清为空队列。 QueueEmptyQueueEmpty(Q)(Q)初始条件：队列初始条件：队列 Q Q 已存在。已存在。操作结果：若操作结果：若 Q Q 为空队列，则返

36、回为空队列，则返回TRUETRUE，否则返回，否则返回 FALSEFALSE。QueueLengthQueueLength(Q)(Q)初始条件：队列初始条件：队列 Q Q 已存在。已存在。操作结果：返回操作结果：返回 Q Q 的元素个数，即队列的长度。的元素个数，即队列的长度。 GetHeadGetHead( (Q,&eQ,&e) )初始条件：初始条件：Q Q 为非空队列。为非空队列。操作结果：用操作结果：用 e e 返回返回Q Q的队头元素。的队头元素。 EnQueueEnQueue(&(&Q,eQ,e) )初始条件：队列初始条件：队列 Q Q 已存在。已存在

37、。操作结果：插入元素操作结果：插入元素 e e 为为 Q Q 的新的队尾元素。的新的队尾元素。DeQueueDeQueue(&(&Q,&eQ,&e) )初始条件：初始条件：Q Q 为非空队列。为非空队列。操作结果：删除操作结果：删除 Q Q 的队头元素，并用的队头元素，并用 e e 返回其值。返回其值。QueueTraverseQueueTraverse( (Q,visitQ,visit( )( )初始条件：队列初始条件：队列 Q Q 已存在且非空，已存在且非空，visit( )visit( )为元素的访为元素的访 问函数。问函数。操作结果：依次对操作结果：依次

38、对 Q Q 的每个元素调用函数的每个元素调用函数 visit( )visit( )， 一旦一旦 visit( ) visit( ) 失败则操作失败。失败则操作失败。 ADT Queue ADT Queue1 队列的链式存储表示队列的链式存储表示 队列的链式存储结构简称为队列的链式存储结构简称为链队列链队列，它是限制仅在表，它是限制仅在表头进行删除操作和表尾进行插入操作的单链表。头进行删除操作和表尾进行插入操作的单链表。 需要两类不同的结点需要两类不同的结点：数据元素结点数据元素结点，队列的队首指队列的队首指针和队尾指针的结点针和队尾指针的结点。3.3.2 队列的链式表示和实现队列的链式表示和实

39、现数据元素结点数据元素结点data指针结点指针结点front rear数据结点类型定义：数据结点类型定义：typedef struct QNodeQelemType data ;struct QNode *next ;QNode, *QueuePtr;指针结点类型定义：指针结点类型定义：typedef struct link_queue QNode *front ； QNode *rear ;Link_Queue ;队头队头队尾队尾Q.frontQ.reardata next2链队运算及指针变化 链队的操作实际上是单链表的操作，只不过是删除在表头进行，插入在表尾进行。插入、删除时分别修改不同的

40、指针。链队运算及指针变化如图所示。(a) 空队列空队列front rear(b) x入队入队 x front rear(c) y再入队再入队 y front rear x(d) x出队出队 y xfront rear3 链队列的基本操作链队列的基本操作 链队列的初始化链队列的初始化Status InitQueue (LinkQueue &Q) / 构造一个空队列构造一个空队列 Q Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode); if (!Q.front) exit(OVERFOLW);/ 存储分配失败存储分配失败 Q.front-next=

41、NULL; return OK; 链队列的入队操作链队列的入队操作 在已知队列的队尾插入一个元素在已知队列的队尾插入一个元素e e ，即修改队，即修改队尾指针尾指针( (Q.rearQ.rear) )。Status EnQueue(LinkQueue &Q, QElemType e)/ 在当前队列的尾元素之后，插入元素在当前队列的尾元素之后，插入元素 e 为新的队列尾元素为新的队列尾元素p=(QueuePtr)malloc(sizeof(QNode);if (!p) exit(OVERFLOW);/ 存储分配失败存储分配失败p-data=e; p-next = NULL;Q.rear-

42、next=p;/ 修改尾结点的指针修改尾结点的指针Q.rear=p; / 移动队尾指针移动队尾指针 链队列的出队操作链队列的出队操作Status DeQueue(LinkQueue &Q, QElemType &e)/ / 若队列不空，则删除队列若队列不空，则删除队列 Q Q 的队头元素，用的队头元素，用 e e 返回其值，并返返回其值，并返回回OKOK；否则返回；否则返回ERRORERRORif(Q.front=Q.rear) return ERROR;/ / 链队列空链队列空p = Q.front-next;e = p-data;/ / 返回被删元素的值返回被删元素的值Q.

43、front-next=p-next; / / 修改队头结点指针修改队头结点指针if(Q.rear=p) Q.rear=Q.front; free(p);/ / 释放被删结点释放被删结点return OK; / DeQueue3.3.3 队列的顺序表示和实现队列的顺序表示和实现 利用一组利用一组连续的存储单元连续的存储单元(一维数组一维数组) 依次存放从队首依次存放从队首到队尾的各个元素，称为到队尾的各个元素，称为顺序队列顺序队列。静态顺序队列静态顺序队列，其类型定义如下：，其类型定义如下：#define MAX_QUEUE_SIZE 100typedef struct queue ElemTy

44、pe Queue_arrayMAX_QUEUE_SIZE ;int front ;int rear ;SqQueue;3.3.2.1 队列的顺序队列的顺序存储结构存储结构设立一个设立一个队首指针队首指针front ，一个，一个队尾指针队尾指针rear ，分，分别指向队首和队尾元素别指向队首和队尾元素。 初始化：初始化：front=rear=0。 入队入队：将新元素插入将新元素插入rear所指的位置，然后所指的位置，然后rear加加1。 出队出队：删去删去front所指的元素，然后所指的元素，然后front加加1并返回被并返回被删元素。删元素。 队列为空队列为空：front=rear。 队满：队

45、满：rear=MAX_QUEUE_SIZE-1或或front=rear。 在非空队列里，队首指针始终指向队头元素，而队尾指针始终指向队尾元素的下一位置。 顺序队列中存在“假溢出”现象。因为在入队和出队操作中，头、尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际元素个数可能远远小于数组大小，但可能由于尾指针巳超出向量空间的上界而不能做入队。操作。该现象称为假溢出。如图所示是数组大小为5的顺序队列中队首、队尾指针和队列中元素的变化情况：(a) 空队列空队列Q.frontQ.rear(b) 入队入队3个元素个元素a3a2a1Q.frontQ.rear(c) 出队出队3个

46、元素个元素Q.frontQ.rear(d) 入队入队2个元素个元素a5a4Q.frontQ.rear3.3.2.2 循环队列循环队列 为充分利用向量空间，克服上述为充分利用向量空间，克服上述“假溢出假溢出”现象的方法现象的方法是：将为队列分配的向量空间看成为一个是：将为队列分配的向量空间看成为一个首尾相接的圆环首尾相接的圆环，并称这种队列为并称这种队列为循环队列循环队列(Circular Queue)。 在循环队列中进行出队、入队操作时，队首、队尾指针在循环队列中进行出队、入队操作时，队首、队尾指针仍要加仍要加1，朝前移动。只不过当队首、队尾指针指向向量上，朝前移动。只不过当队首、队尾指针指向

47、向量上界界(MAX_QUEUE_SIZE-1)时，其加时，其加1操作的结果是指向向量操作的结果是指向向量的下界的下界0。这种循环意义下的加这种循环意义下的加1操作可以描述为：操作可以描述为：if (i+1=MAX_QUEUE_SIZE) i=0;else i+ ;其中：其中： i代表队首指针代表队首指针(front)或队尾指针或队尾指针(rear)用模运算可简化为：i=(i+1)%MAX_QUEUE_SIZE ;l 显然，为循环队列所分配的空间可以被充分利用，除非向量空间真的被队列元素全部占用，否则不会上溢。因此，真正实用的顺序队列是循环队列。 例 ： 设 有 循 环 队 列 Q U 0 ，

48、5 ， 其 初 始 状 态 是front=rear=0，各种操作后队列的头、尾指针的状态变化情况如下图所示。 123450(a) 空队列空队列frontrear123450(b) d, e, b, g入入队队frontdebgrear123450(c) d, e出队出队bgfrontrearl 入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，无法通过front=rear来判断队列“空”还是“满”。解决此问题的方法是：约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满。即： rear所指的单元始终为空。 循环队列为空：front=

49、rear 。 循环队列满：(rear+1)%MAX_QUEUE_SIZE =front。123450(d) i, j, k入入队队bgfrontijkrear123450(e) b, g出队出队ijkrearfront123450(f) r, p, s, t入队入队ijkfrontrprear循环队列的基本操作1 循环队列的初始化：Status InitQueue (SqQueue &Q)/ 构造一个空队列 QQ.base = (QElemType *)malloc(MAXQSIZE*sizeof(QElemType); / 为循环队列分配存储空间if (!Q.base) exit(OVERFLOW);/ 存储分配失败Q.front = Q.rear = 0;return OK; / InitQueue2 求队列的长度求队列的长度int QueueLength (SqQueue Q)/ 返回队列返回队列Q中元素个数，即队列的长度中元素个数，即队列的长度 return (Q.rear-Q.front+MAXQSIZE) % MAXQSIZE); 3 入队操作入队操作Status EnQueue (Sq