数据结构 栈和队列

1、数据结构C语言描述出出 版版 社社第第3章章 栈和队列栈和队列 本章要点：栈和队列两种抽象数据类型的特点。栈用两种存储结构表示时的基本操作算法的实现。栈和队列的应用。数据结构C语言描述出出 版版 社社 线性表的操作允计在表的任何位置进行。线性表的操作允计在表的任何位置进行。 本章介绍的两种特殊的线性表，是操作本章介绍的两种特殊的线性表，是操作受限制的特殊线性表受限制的特殊线性表栈栈(Stack)(Stack)和队列和队列(Queue)(Queue)，其特殊性在于限制了插入和删除等，其特殊性在于限制了插入和删除等运算的位置。运算的位置。数据结构C语言描述出出 版版 社社3.1 栈栈 栈是用来保存

2、一些尚未处理而又等待处理的数据项这些数据项的处理是依据后进先出的规则。因此，经常把栈叫做后进先出线性表。 栈在日常生活中几乎到处可见，如火车进库时，库的一端是堵死的，那么最后入库的火车必须先出来，否则前面的列车都被堵住，无法倒出。栈是这种事务的一种抽象。 数据结构C语言描述出出 版版 社社3.1.1 栈的意义及抽象数据类型栈的意义及抽象数据类型 栈栈是将线性表的插入和删除运算限制为仅在表的一端进行的线性表。通常将表中允许进行插入、删除操作的一端称为栈顶栈顶(Top)。栈顶的当前位置是动态变化的，表的另一端称为栈底栈底(Bottom)。当栈中没有元素时称为空栈空栈。栈的插入操作被形象地称为进栈或

3、入栈，删除操作称为出栈或退栈。不含元素的栈称为空栈。 假设栈s=（a1，a2，an），a1元素所在的位子称为栈底，an元素所在的位子称为栈顶，如图3.1所示。数据结构C语言描述出出 版版 社社 进栈顺序是进栈顺序是a1，a2an，退栈的第一个，退栈的第一个元素是元素是an，最后一个元，最后一个元素是素是a a1 1是按是按“后进先出后进先出”的原则进行的，因此栈的原则进行的，因此栈又称为后进先出（又称为后进先出（Last Last In First OutIn First Out），缩写），缩写为（为（LIFO）的线性表。）的线性表。图图3.1 3.1 栈栈bottomtop ana3a2a1

4、3.1.1 栈的意义及抽象数据类型（续）栈的意义及抽象数据类型（续） 数据结构C语言描述出出 版版 社社进栈进栈出栈出栈图图3.23.2铁路调度栈示意图铁路调度栈示意图 图图3.23.2为铁路调度中栈为铁路调度中栈的应用。在日常生活中还的应用。在日常生活中还有一些类似栈的例子。例有一些类似栈的例子。例如：往箱子里放衣物，这如：往箱子里放衣物，这相当于进栈最先放的衣服相当于进栈最先放的衣服在箱底（栈底），最后放在箱底（栈底），最后放的在箱顶（栈顶），取时的在箱顶（栈顶），取时应先从箱顶开始拿，这相应先从箱顶开始拿，这相当于出栈操作。当于出栈操作。 3.1.1 栈的意义及抽象数据类型（续）栈的意义

5、及抽象数据类型（续） 数据结构C语言描述出出 版版 社社3.1.1 栈的意义及抽象数据类型（续）栈的意义及抽象数据类型（续） 栈的基本操作除了在栈顶进行插入或删除外，还有栈的初栈的基本操作除了在栈顶进行插入或删除外，还有栈的初始化、清空及取栈顶元素等，下面给出栈的抽象数据类型定始化、清空及取栈顶元素等，下面给出栈的抽象数据类型定义：义：ADT ADT stack 数据元素数据元素：可以是任意类型的数据，但必须属于同一个数据：可以是任意类型的数据，但必须属于同一个数据对象。对象。 数据关系数据关系：栈中数据元素之间是线性关系。：栈中数据元素之间是线性关系。 基本操作基本操作： InitStack

6、(SInitStack(S) )：将：将S S初始化为空栈。初始化为空栈。 ClearStack(SClearStack(S) )：栈：栈S S已经存在，将栈已经存在，将栈S S置成空栈。置成空栈。 EmptyStack(SEmptyStack(S) )：栈：栈S S已经存在，判断若已经存在，判断若S S为空，函数值返回为空，函数值返回TRUETRUE，否则返，否则返FALSEFALSE。数据结构C语言描述出出 版版 社社 DestroyStack(S DestroyStack(S) )：栈：栈S S已经存在，销毁栈并释放空间。已经存在，销毁栈并释放空间。 Push(S,x) Push(S,x

7、)：栈：栈S S已经存在，若已经存在，若S S栈未满，将栈未满，将x x插入插入S S栈的栈顶位栈的栈顶位置，函数返回置，函数返回TRUETRUE；若；若S S栈已满，则返回栈已满，则返回FALSEFALSE，表示操作失败。，表示操作失败。 Pop(S, x) Pop(S, x)：栈：栈S S已经存在，在栈已经存在，在栈S S的顶部弹出栈顶元素，并用的顶部弹出栈顶元素，并用x x带回该值；若栈为空，返回值为带回该值；若栈为空，返回值为FALSEFALSE，表示操作失败，否则，表示操作失败，否则返回返回TRUETRUE。 GetTop(S GetTop(S, x), x)：栈：栈S S已经存在，

8、取栈已经存在，取栈S S的栈顶元素，其余不变。的栈顶元素，其余不变。(8)Stacklenth(S)(8)Stacklenth(S)栈栈S S已经存在，返回栈中元素个数。已经存在，返回栈中元素个数。 ADT ADT stack3.1.1 栈的意义及抽象数据类型（续）栈的意义及抽象数据类型（续） 数据结构C语言描述出出 版版 社社3.1.2 栈操作的实现栈操作的实现 与线性表一样，栈的存储方式也有两种：顺序存储和链表存与线性表一样，栈的存储方式也有两种：顺序存储和链表存储方式。储方式。 3.1.2.1 栈的顺序存储结构栈的顺序存储结构 栈的顺序存储结构即顺序栈是分配一块连续的存储区域栈的顺序存储

9、结构即顺序栈是分配一块连续的存储区域依次存放自栈底到栈顶的数据元素，同时设指针依次存放自栈底到栈顶的数据元素，同时设指针toptop来动态来动态地指示栈顶元素的当前位置。空栈地指示栈顶元素的当前位置。空栈top=0top=0或或 top=-1top=-1表示。下表示。下面的顺序栈，采用的是面的顺序栈，采用的是toptop指向栈顶元素的后一个元素位置指向栈顶元素的后一个元素位置的方式来描述，当空栈时的方式来描述，当空栈时top=0top=0。顺序栈的存储结构可以用。顺序栈的存储结构可以用C C语言中的一维数组来表示。栈的顺序存储结构定义如下：语言中的一维数组来表示。栈的顺序存储结构定义如下：数据

10、结构C语言描述出出 版版 社社define Stack-Size 50define Stack-Size 50typedef structtypedef struct elemtype elemStackelemtype elemStack-Size-Size； /*存放栈元素的一维数组*/intint top top； /*存放栈顶元素的下标*/ SeqStack SeqStack； 若若s s为为SeqStackSeqStack类型变量，则类型变量，则s.elem0s.elem0存放栈中第一个元素，存放栈中第一个元素，s.elems.top-1s.elems.top-1为最后一个元素（栈顶

11、元素）。当为最后一个元素（栈顶元素）。当s.top=s.top= Stack-SizeStack-Size时为时为栈满，此时若再有元素入栈则将产生越界的错误，称为栈上溢栈满，此时若再有元素入栈则将产生越界的错误，称为栈上溢(overflow)(overflow)，反之反之,top=0 ,top=0 时为栈空，这时若执行出栈操作则产生下溢的错误时为栈空，这时若执行出栈操作则产生下溢的错误(underflow)(underflow)。图图3.33.3表示了顺序栈中数据元素和栈顶指针之间的对应关系。表示了顺序栈中数据元素和栈顶指针之间的对应关系。 3.1.2 栈操作的实现（续）栈操作的实现（续） 数

12、据结构C语言描述出出 版版 社社(a) (a) 空栈空栈 (b) A(b) A进栈进栈 (c) B(c) B进栈进栈 (d) C(d) C、D D、E E、进栈、进栈 图图3.3 3.3 栈顶指针和栈中元素之间的关系栈顶指针和栈中元素之间的关系top=0top=1top=2top=5ABABAEDC3.1.2 栈操作的实现（续）栈操作的实现（续） 数据结构C语言描述出出 版版 社社顺序栈中几种操作算法的实现。顺序栈中几种操作算法的实现。进栈进栈/ /* *在在S S栈中插入元素栈中插入元素x x，成功返回真失败返回假，成功返回真失败返回假* */ /int Push(SeqStack int

13、Push(SeqStack * *S, elemtypeS, elemtype x) x) if(S-top = Stack-Size)if(S-top = Stack-Size) return FALSE return FALSE ； / /* *栈满不能插入元素返回假值栈满不能插入元素返回假值* */ / S-elem S-elemS-topS-top=x=x； S-top+S-top+； return TRUEreturn TRUE； / /* *成功将元素入栈，返回真值成功将元素入栈，返回真值* */ / 3.1.2 栈操作的实现（续）栈操作的实现（续） 数据结构C语言描述出出 版版

14、社社出栈出栈/ /* * 将栈将栈S S的栈顶元素弹出，放到的栈顶元素弹出，放到x x所指的存储空间中所指的存储空间中 * */ / int Pop(SeqStack int Pop(SeqStack * * S, elemtype S, elemtype * *x)x) if(S-top=0) return FALSE if(S-top=0) return FALSE； / /* *栈为空返回假值栈为空返回假值* */ / elseelse S-top-S-top-； / /* *修改栈顶指针修改栈顶指针* */ / * *x= S-elemSx= S-elemS-top-top； retu

15、rn TRUEreturn TRUE； / /* *成功出栈，返回真值成功出栈，返回真值* */ / 3.1.2 栈操作的实现（续）栈操作的实现（续） 数据结构C语言描述出出 版版 社社3.1.2 栈操作的实现（续）栈操作的实现（续） 取栈顶元素取栈顶元素 / /* * 将栈将栈S S的栈顶元素弹出，的栈顶元素弹出， 放到放到x x所指的存储空间中所指的存储空间中* */ / int GetTop int GetTop（SeqStack S, elemtypeSeqStack S, elemtype * *x x） if(S-top= if(S-top=) return FALSE) retu

16、rn FALSE； / /* *栈为空，结束返回假值栈为空，结束返回假值* */ / else else * *x = S-elemSx = S-elemS-top -top - ； / /* *取栈顶数据，存放在取栈顶数据，存放在x x中中* */ / return TRUE return TRUE ； 数据结构C语言描述出出 版版 社社3.1.2 栈操作的实现（续）栈操作的实现（续） (4) (4)求栈中元素个数求栈中元素个数 int Stacklength(SeqStackint Stacklength(SeqStack S) S) / /* *返回栈中当前元素的个数返回栈中当前元素的个

17、数 * */ / return S-top; return S-top; 数据结构C语言描述出出 版版 社社3.1.2 栈操作的实现（续）栈操作的实现（续） 在栈的共享技术中最常用的是两个栈的共享技术：如图在栈的共享技术中最常用的是两个栈的共享技术：如图3.43.4所示，两个栈共享空间所示，两个栈共享空间, ,它主要利用了栈它主要利用了栈“栈底位置不变，栈底位置不变，而栈顶位置动态变化而栈顶位置动态变化”的特性。的特性。 首先为两个栈申请一个首先为两个栈申请一个共享的一维数组空间共享的一维数组空间SMSM，将两个栈的栈底分别放在一维数，将两个栈的栈底分别放在一维数组的两端，分别是组的两端，分别

18、是0 0，M-1M-1。由于两个栈顶动态变化，这样可。由于两个栈顶动态变化，这样可以形成互补，使得每个栈可用的最大空间与实际使用的需求以形成互补，使得每个栈可用的最大空间与实际使用的需求有关。有关。 0 top0 top1 M-1 top0 top1 M-1图图3.4 3.4 二栈共享空间二栈共享空间数据结构C语言描述出出 版版 社社3.1.2 栈操作的实现（续）栈操作的实现（续） 由此可见，两栈共享比两个栈分别申请由此可见，两栈共享比两个栈分别申请M/2M/2的空的空间利用率高。两栈共享的数据结构定义如下：间利用率高。两栈共享的数据结构定义如下： define M 100define M 1

19、00 typedef structtypedef struct elemtypeelemtype StackM StackM； / /* *存储两个栈的数据元素存储两个栈的数据元素* */ / int int top2 top2； / /* *toptop数组为两个栈顶数组为两个栈顶* */ / DseqStack DseqStack；数据结构C语言描述出出 版版 社社3.1.2 栈操作的实现（续）栈操作的实现（续）下面是二栈共享的一些操作算法。下面是二栈共享的一些操作算法。 初始化操作初始化操作void InitStack(DseqStackvoid InitStack(DseqStack

20、* *S)S) S-top0= 0 S-top0= 0； / /* *第一个栈的栈顶初值为第一个栈的栈顶初值为* */ / S-top1=M-1 S-top1=M-1； / /* *第二个栈的栈顶初值为第二个栈的栈顶初值为M-1M-1* */ / 数据结构C语言描述出出 版版 社社3.1.2 栈操作的实现（续）栈操作的实现（续） 进栈操作进栈操作/ /* *将数据元素将数据元素x x压入压入i i号堆栈，图号堆栈，图3.43.4中中 i=0 i=0 、1 1分别表示两个栈。分别表示两个栈。* */ /int Push(DseqStack int Push(DseqStack * *S, ele

21、mtype x, intS, elemtype x, int i) i) if(S-top0+1=S-top1-1) / if(S-top0+1=S-top1-1) /* *栈满栈满* */ / return FALSEreturn FALSE； switch(i) switch(i) case 0: S-Stack case 0: S-StackS-topS-top0 0=x=x； / /* *从第一个入栈从第一个入栈* */ / S-top S-top0 0+； breakbreak； case 1: S-Stackcase 1: S-StackS-topS-top1 1=x=x； / /

22、* *从第二个入栈从第二个入栈* */ / S-top1- S-top1-；breakbreak； default: return FALSEdefault: return FALSE； / /* *参数错误参数错误* */ / return TRUE return TRUE ； 数据结构C语言描述出出 版版 社社3.1.2 栈操作的实现（续）栈操作的实现（续） 出栈操作出栈操作int Pop(DseqStack int Pop(DseqStack * *S, elemtype S, elemtype * *x, intx, int i) i) / /* * 从从i i 号堆栈中弹出栈顶元素并

23、送到号堆栈中弹出栈顶元素并送到x x中中 * */ / switch(i)switch(i) case 0:if(S-top0= case 0:if(S-top0=) return FALSE) return FALSE； / /* *从左边出栈从左边出栈* */ / * *x=S-StackS-top0-1x=S-StackS-top0-1； S-top0- -S-top0- -； breakbreak； case 1:if(S-top1=M-1) return FALSEcase 1:if(S-top1=M-1) return FALSE；/ /* *从右边出栈从右边出栈* */ / *

24、*x=S-StackS-top1+1x=S-StackS-top1+1； S-topS-top1 1+； breakbreak； default:return FALSEdefault:return FALSE； / /* *参数错误参数错误* */ / return TRUEreturn TRUE； 数据结构C语言描述出出 版版 社社3.1.2 栈操作的实现（续）栈操作的实现（续）3.1.2.2栈的链式存储结构栈的链式存储结构栈的链式存储结构如图栈的链式存储结构如图3.53.5所示，是一个单链表结构。栈顶指针是链表的的所示，是一个单链表结构。栈顶指针是链表的的第一个结点，栈底指针指向链表的最

25、后一个结点。类型说明如下：第一个结点，栈底指针指向链表的最后一个结点。类型说明如下：typedef structtypedef struct node node elemtypeelemtype data data； / /* *数据域数据域 * */ / struct struct node node * *nextnext；/ /* *指针域指针域 * */ / * *LinkStackLinkStack； 栈顶栈顶 S1 S2 Sn 图图3.5 栈的链式存储结构栈的链式存储结构栈底栈底数据结构C语言描述出出 版版 社社3.1.2 栈操作的实现（续）栈操作的实现（续） 对于链式结构一般不会

26、有溢出，只有内存可用空间都被占满，对于链式结构一般不会有溢出，只有内存可用空间都被占满，mallocmalloc()()过程无法实现才会产生上溢。因此过程无法实现才会产生上溢。因此, ,多个链栈共享空间很容易。多个链栈共享空间很容易。下面给出链链式栈的基本操作算法：下面给出链链式栈的基本操作算法： 进栈操作进栈操作int Push(LinkStack top, elemtypeint Push(LinkStack top, elemtype x) x) / /* * 将数据元素将数据元素x x压入栈顶为压入栈顶为toptop的链式栈中的链式栈中 * */ / temp=(LinkStack)m

27、alloc(sizeof(struct temp=(LinkStack)malloc(sizeof(struct node) node)；/ /* *创建结点创建结点* */ / if(temp=NULL) return FALSE if(temp=NULL) return FALSE；/ /* *申请空间失败结束，返回假值申请空间失败结束，返回假值* */ / temp-data=x temp-data=x； temp-next=toptemp-next=top； / /* * 新结点压入栈顶新结点压入栈顶 * */ / top=temp top=temp； / /* * 修改当前栈顶指针修

28、改当前栈顶指针 * */ / return TRUEreturn TRUE； 数据结构C语言描述出出 版版 社社3.1.2 栈操作的实现（续）栈操作的实现（续） 出栈操作出栈操作int Pop(LinkStack top, elemtypeint Pop(LinkStack top, elemtype * *x)x) / /* *将链栈的栈顶将链栈的栈顶toptop元素弹出，存储到元素弹出，存储到x x* */ / temp=top temp=top； / /* * 将栈顶指针存入将栈顶指针存入temptemp中中* */ / if(temp=NULL) return FALSE if(tem

29、p=NULL) return FALSE；/ /* *栈空，返回假值栈空，返回假值* */ / top=temp-nexttop=temp-next； / /* *栈顶指针下移栈顶指针下移* */ / * *x=temp-datax=temp-data； / /* *栈顶元素赋值给栈顶元素赋值给x x* */ / free temp free temp； / /* * 释放存储空间释放存储空间 * */ / return TRUE return TRUE； 数据结构C语言描述出出 版版 社社3.1.2 栈操作的实现（续）栈操作的实现（续） 栈是一种操作上受限制的线性表，插入栈是一种操作上受限制

30、的线性表，插入和删除不能随机进行（只能在一端）。从线和删除不能随机进行（只能在一端）。从线性表顺序和链式存储结构的特点看，栈的顺性表顺序和链式存储结构的特点看，栈的顺序存储结构的操作与实现比链式存储结构有序存储结构的操作与实现比链式存储结构有较大的优势。当多栈共享空间时，可以使用较大的优势。当多栈共享空间时，可以使用静态链表结构，能较好地解决问题。读者可静态链表结构，能较好地解决问题。读者可以自己分析。以自己分析。 数据结构C语言描述出出 版版 社社3.2 队列队列 在我们的生活中经常有这样的数据一端作为进端，在我们的生活中经常有这样的数据一端作为进端，另一端作为出端，如另一端作为出端，如:排

31、队等车。这种数据也是一种排队等车。这种数据也是一种线性结构，但操作上不同于线性表，下面我们介绍线性结构，但操作上不同于线性表，下面我们介绍这种数据结构。这种数据结构。3.2.1 3.2.1 队列及其抽象数据类型队列及其抽象数据类型 队列队列是一种操作受限的线性表，所有的插入都在是一种操作受限的线性表，所有的插入都在表的一端进行，所有的删除都在表的另一端进行。表的一端进行，所有的删除都在表的另一端进行。进行删除的一端叫队列的头（进行删除的一端叫队列的头（front）称为）称为队头队头，进，进行插入的一端叫队列的尾（行插入的一端叫队列的尾（rear）称为）称为队尾队尾。 ，如，如图图3.8数据结构

32、C语言描述出出 版版 社社3.2.1 3.2.1 队列及其抽象数据类型（续）队列及其抽象数据类型（续） 队列同现实生活中买东西排队相仿。后来的总是加入到队尾，每次离开的总是在队列头进行的。因此队列也称“先进先出线性表（First In First Out）。 队头队头 队尾队尾 a1 a2 an 出队出队 入队入队 图图3.8 3.8 队列示意图队列示意图 数据结构C语言描述出出 版版 社社3.2.1 3.2.1 队列及其抽象数据类型（续）队列及其抽象数据类型（续） 队列在程序设计中也经常出现。一个最队列在程序设计中也经常出现。一个最典型的例子就是操作系统中的作业排队。在典型的例子就是操作系统

33、中的作业排队。在多道程序运行的计算机系统中，同时有几个多道程序运行的计算机系统中，同时有几个作业运行。如果运行结果都需要通过通道输作业运行。如果运行结果都需要通过通道输出，那就要按请求输出的先后次序排队。凡出，那就要按请求输出的先后次序排队。凡是请求输出的作业都是从队尾进入队列的。是请求输出的作业都是从队尾进入队列的。 队列的操作与栈的操作类似，下面给出队列的操作与栈的操作类似，下面给出队列的抽象数据类型定义：队列的抽象数据类型定义：数据结构C语言描述出出 版版 社社ADT Queue数据元素数据元素D：可以是任意类型的数据，但必须属于同一个数据：可以是任意类型的数据，但必须属于同一个数据 对

34、象。对象。数据关系数据关系R：队列中数据元素之间是线性关系。：队列中数据元素之间是线性关系。 基本操作基本操作： (1)(1) InitQueue(QInitQueue(Q) )：初始化操作。：初始化操作。 设置一个空队列。设置一个空队列。(2)(2) EmptyQueue(QEmptyQueue(Q) )：判空操作。若队列为空则返：判空操作。若队列为空则返TRUETRUE，否则，否则 FALSEFALSE。(3)(3) ClearQueue(QClearQueue(Q) )：队列置空操作。将队列：队列置空操作。将队列Q Q置为空队列。置为空队列。(4) DestroyQueue(Q(4) D

35、estroyQueue(Q) )：队列销毁操作。释放队列的空间。：队列销毁操作。释放队列的空间。(5)(5) GetHeadGetHead（Q, xQ, x）：取队头元素操作。用）：取队头元素操作。用x x取得队元素的值。取得队元素的值。 操作成功，返回值为操作成功，返回值为TRUETRUE，否则返回值为，否则返回值为FALSEFALSE。数据结构C语言描述出出 版版 社社3.2.1 3.2.1 队列及其抽象数据类型（续）队列及其抽象数据类型（续）(6)(6) QueueLengthQueueLength (Q): (Q): 队列队列Q Q已经存在，队列返回中元素个数。已经存在，队列返回中元素

36、个数。(7)(7) EnterQueue(QEnterQueue(Q，x)x)：进队操作。在队列：进队操作。在队列Q Q的队尾插入的队尾插入x x。 操作成功，返回值为操作成功，返回值为TRUETRUE， 否则返回值为否则返回值为FALSEFALSE。 (8)(8) DeleteQueue(QDeleteQueue(Q, x), x)：出队操作，并用：出队操作，并用x x返回值。成功，返返回值。成功，返TRUETRUE，否则，否则FALSEFALSE。 ADT Queue 队列也可以有两种存储形式，即顺序存储表示和链式存队列也可以有两种存储形式，即顺序存储表示和链式存储表示，下面先来看队列的链

37、式存储结构的形式及操作。储表示，下面先来看队列的链式存储结构的形式及操作。 数据结构C语言描述出出 版版 社社3.2.2 3.2.2 队列的链式存储结构队列的链式存储结构 我们知道，对于使用中数据元素变动较大的数据结构，采用链式存储结构比顺序存储结构更有利。链队列就是这样一种数据结构。 用链表表示的队列需要两个指针，分别指示队头和队尾。如图3.9所示。 队头 Q1 Q2 Q n 队尾 图图3.9 链队列示意图链队列示意图数据结构C语言描述出出 版版 社社3.2.2 3.2.2 队列的链式存储结构（续）队列的链式存储结构（续） 为了操作方便，和单链表一样，我们也给链队列添加一个哨兵结点，为了操作

38、方便，和单链表一样，我们也给链队列添加一个哨兵结点，并令队头指针指向哨兵结点。队尾指针指向当前最后一个元素。由此，并令队头指针指向哨兵结点。队尾指针指向当前最后一个元素。由此，空的队列的判别条件为头指针和尾指针均指向哨兵结点。下面给出链队空的队列的判别条件为头指针和尾指针均指向哨兵结点。下面给出链队列数据类型：列数据类型：typedef structtypedef struct Node Node elemtypeelemtype data; / data; /* *数据域数据域* */ / structstruct Node next; / Node next; /* *指针域指针域* */

39、 / LinkQueueNodeLinkQueueNode; ; typedef structtypedef struct LinkQueueNodeLinkQueueNode * *front;front; LinkQueueNodeLinkQueueNode * *rear;rear; * *LinkQueueLinkQueue; ; 数据结构C语言描述出出 版版 社社3.2.2 3.2.2 队列的链式存储结构（续）队列的链式存储结构（续） 链队列的操作与单链表操作极为相似，只是插入、删除链队列的操作与单链表操作极为相似，只是插入、删除分别修改头指针、尾指针。一般来说，只要可用空间不被占分

40、别修改头指针、尾指针。一般来说，只要可用空间不被占满，链队列不会发生上溢情况。图满，链队列不会发生上溢情况。图3.10所示描述了一个带哨所示描述了一个带哨兵结点队列的创建、插入、删除操作过程。兵结点队列的创建、插入、删除操作过程。(a)初始化带哨兵空队初始化带哨兵空队 (b)申请新结点申请新结点 (c)在空队列中插入元素在空队列中插入元素e 3.10 建队操作过程建队操作过程front rearQesfront front rearrearesQ数据结构C语言描述出出 版版 社社3.2.2 3.2.2 队列的链式存储结构（续）队列的链式存储结构（续）队列基本操作算法如下：队列基本操作算法如下：

41、(1).(1).初始化操作。初始化操作。 int InitQueue(LinkQueueint InitQueue(LinkQueue * *Q)Q)/ /* * 将将Q Q初始化为一个带哨兵的空链队初始化为一个带哨兵的空链队 * */ / * *Q-front=(LinkQueueNode Q-front=(LinkQueueNode * *)malloc(sizeof(LinkQueueNode)malloc(sizeof(LinkQueueNode);); / /* *开辟哨兵开辟哨兵* */ / if( if(* *Q-front!=NULL)Q-front!=NULL) * *Q-r

42、ear=Q-rear=* *Q-front;Q-front; / /* *队头、队尾都指向哨兵结点！队头、队尾都指向哨兵结点！* */ / * *Q-front-next=NULL;Q-front-next=NULL; return OK;return OK; else return FALSE ; /else return FALSE ; /* *哨兵结点开辟失败！哨兵结点开辟失败！* */ / 数据结构C语言描述出出 版版 社社3.2.2 3.2.2 队列的链式存储结构（续）队列的链式存储结构（续）(2). 入队操作入队操作 int EnterQueue(LinkQueue int Ent

43、erQueue(LinkQueue * *Q, elemtypeQ, elemtype e) e) / /* * 将数据元素将数据元素e e插入到带哨兵队列插入到带哨兵队列Q Q中中 * */ / NewNode=(LinkQueueNode NewNode=(LinkQueueNode * * )malloc(sizeof(LinkQueueNode )malloc(sizeof(LinkQueueNode);); / /* *开辟新结点开辟新结点* */ / if(NewNode if(NewNode!= NULL)!= NULL) NewNodeNewNode-data=e;-data=

44、e; / /* *将新结点中赋将新结点中赋e e值值* */ / NewNodeNewNode-next=NULL;-next=NULL; * *Q-rear-next=NewNodeQ-rear-next=NewNode; ; / /* * 插入队尾插入队尾 * */ / * *Q-rear=NewNodeQ-rear=NewNode; ; return TRUE ;return TRUE ; else return FALSE ; /else return FALSE ; /* * 没开辟出新结点没开辟出新结点* */ / 数据结构C语言描述出出 版版 社社3.2.2 3.2.2 队列的链

45、式存储结构（续）队列的链式存储结构（续） (3).(3). 出队操作出队操作 int DeleteQueue(LinkQueue int DeleteQueue(LinkQueue * * Q, Elemtype Q, Elemtype * *e)e) / /* * 将队列将队列Q Q的队头元素出队，的队头元素出队， 并存放到并存放到e e所指的存储空间中所指的存储空间中 * */ / LinkQueueNode LinkQueueNode * *p;p; if(if(* *Q-front=Q-front=* *Q-rear) Q-rear) return FALSE; / return FA

46、LSE; /* *空队列取队尾失败空队列取队尾失败* */ / p= p= * *Q-front-next;Q-front-next; / /* * 从队头取出结点从队头取出结点p p * */ / * *Q-front-next=p-next; /Q-front-next=p-next; /* * 队头元素队头元素p p出队出队 * */ / if(if(* *Q-rear=p) /Q-rear=p) /* *如果队中只有一个元素如果队中只有一个元素p p，则，则p p出队后成为空队出队后成为空队* */ / * *Q-rear=Q-rear=* *Q-front;Q-front; * *e

47、=p-data;e=p-data; / /* * 结果作为变参返回结果作为变参返回* */ / free(p); return TRUE; free(p); return TRUE; 其他算法，如队列的长度、取队头元素等，如何实现？。其他算法，如队列的长度、取队头元素等，如何实现？。数据结构C语言描述出出 版版 社社3.2.3 3.2.3 队列的顺序存储结构队列的顺序存储结构-循环队列循环队列 虽然链队列很方便，但由于每个结点都有指针域，因此比虽然链队列很方便，但由于每个结点都有指针域，因此比顺序存储多占用内存空间。所以在有些情况下仍需要用顺序顺序存储多占用内存空间。所以在有些情况下仍需要用顺

48、序存储结构来表示队列。存储结构来表示队列。 在队列的顺序存储结构中，可以用一组地址连续的存储单在队列的顺序存储结构中，可以用一组地址连续的存储单元依次存放从队头到队尾的元素，还要设置两个指针分别指元依次存放从队头到队尾的元素，还要设置两个指针分别指向队头元素和队尾元素的位置，并约定队头指针指示队列中向队头元素和队尾元素的位置，并约定队头指针指示队列中第一个元素的位置，尾指针指示队尾元素位置的后一个位置。第一个元素的位置，尾指针指示队尾元素位置的后一个位置。如图如图3.11所示。由于队列中队头和队尾的位置都是动态变化所示。由于队列中队头和队尾的位置都是动态变化的，如果不加以约束，队头和队尾在数组

49、中的位置是不断移的，如果不加以约束，队头和队尾在数组中的位置是不断移动的如图动的如图3.11(b)、3.11(c)。图。图3.11(d)当队尾移动到最后位置当队尾移动到最后位置时，不能再入队。但队头为时，不能再入队。但队头为3前面还有单元是空的。如果将前面还有单元是空的。如果将顺序的数组看成一个环状的空间，即最后一个单元的后继为顺序的数组看成一个环状的空间，即最后一个单元的后继为第一个单元。因此顺序存储的队列中，将所开辟空间地址的第一个单元。因此顺序存储的队列中，将所开辟空间地址的首、尾位置是连接起来形成一个环状结构称为循环队列，如首、尾位置是连接起来形成一个环状结构称为循环队列，如图图3.1

50、23.12所示。所示。 数据结构C语言描述出出 版版 社社3.2.3 3.2.3 队列的顺序存储结构队列的顺序存储结构-循环队列（续）循环队列（续）(a) 空队列空队列 (b) a b c d 依次依次入队入队 (c) a b c 出队出队 (d) e f 进队进队图图3.11 队列的顺序存储结构队列的顺序存储结构q.rearq.front543210q.rearq.front543 d2 c1 b0 aq.rearq.front543 d2 1 0 q.rearq.front5 f 4 e3 d2 1 0 (a) 空队列空队列(b) 队列满队列满(c) 一般情况一般情况图图3.12 循环队列

51、循环队列012354rearfront012354e6e7e8e3e4e5012354frontreare3e4e5frontrear数据结构C语言描述出出 版版 社社 假设开辟了假设开辟了MAXSIZEMAXSIZE个空间个空间, ,初始化队列时，令初始化队列时，令frontfrontrearrear0 0；入队时，直接将新元素送入尾指针；入队时，直接将新元素送入尾指针rearrear所指的单元，所指的单元，然后尾指针增然后尾指针增1,1,出队时，直接取出队头指针出队时，直接取出队头指针frontfront所指的元素，所指的元素，然后头指针增然后头指针增1 1。显然，在非空顺序队列中，队头指

52、针始终指。显然，在非空顺序队列中，队头指针始终指向当前的队头元素，而队尾指针始终指向真正队尾元素后面的向当前的队头元素，而队尾指针始终指向真正队尾元素后面的单元。随着入队和出队的进行当单元。随着入队和出队的进行当frontfrontrearrear时，循环队列有时，循环队列有两种情况，一种为队满；一种为队空。可见，两种情况，一种为队满；一种为队空。可见，frontfrontrearrear无无法判别队列的状态是法判别队列的状态是“空空”还是还是“满满”。 对于这个问题，有两种处理方法：对于这个问题，有两种处理方法： 3.2.3 3.2.3 队列的顺序存储结构队列的顺序存储结构-循环队列（续）循

53、环队列（续）数据结构C语言描述出出 版版 社社 一种方法是少用一个元素存储空间。当队尾指针所指向的空单元的后继单元是队头元素所在的单元时，则停止入队。这样一来，队尾指针永远追不上队头指针，所以队满时不会有frontrear。这时队列“满”的条件为(rear十1)mod MAXSIZEfront。判队空的条件不变，仍为rearfront。 另一种方法是增设一个标志量的方法，以区别队列是“空”还是“满”。3.2.3 3.2.3 队列的顺序存储结构队列的顺序存储结构-循环队列（续）循环队列（续）数据结构C语言描述出出 版版 社社循环队列的类型定义如下：循环队列的类型定义如下： define MAXS

54、IZE 50 / *队列的最大长度队列的最大长度* / typedef structtypedef struct elemtype elem elemtype elem MAXSIZE;/ MAXSIZE;/* *队列的元素空间队列的元素空间* */ / int int front,rear; / front,rear; /* *头、尾指针头、尾指针* */ / SeqQueueSeqQueue; ; 基本操作实现：基本操作实现： 前面我们介绍了入队时，队满队空状态的两种前面我们介绍了入队时，队满队空状态的两种处理方法，下面采用多用一个空闲空间的方法。处理方法，下面采用多用一个空闲空间的方法。

55、 3.2.3 3.2.3 队列的顺序存储结构队列的顺序存储结构-循环队列（续）循环队列（续）数据结构C语言描述出出 版版 社社(1)(1) 入队操作入队操作int EnterQueue(SeqQueue int EnterQueue(SeqQueue * *Q, elemtypeQ, elemtype e) e) / /* *将元素将元素e e加入队列加入队列Q Q* */ / if(Q-rear+1)%MAXSIZE=Q-front) if(Q-rear+1)%MAXSIZE=Q-front) return FALSE; / return FALSE; /* * 队列满，返回假值结束队列满，

56、返回假值结束* */ / Q-elemQ-elem Q-rearQ-rear=e; /=e; /* * 将将e e加入队尾加入队尾* */ / Q-rear=(Q-rear+1)%MAXSIZE; / Q-rear=(Q-rear+1)%MAXSIZE; /* * 重新设置队尾指针重新设置队尾指针 * */ / return TRUE ; / return TRUE ; /* * 操作成功操作成功* */ / 3.2.3 3.2.3 队列的顺序存储结构队列的顺序存储结构-循环队列（续）循环队列（续）数据结构C语言描述出出 版版 社社（2）出队操作）出队操作 int DeleteQueue(Se

57、qQueue int DeleteQueue(SeqQueue * *Q, elemtypeQ, elemtype * *e)e) / /* *队列队列Q Q的队头元素出队，的队头元素出队， 用用e e返回其值返回其值* */ / ifif（Q-front=Q-rearQ-front=Q-rear） return FALSE; /return FALSE; /* *队列为空，返回假值结束队列为空，返回假值结束* */ / * *e=Q-eleme=Q-elem Q-frontQ-front; ; Q-front=(Q-front+1)%MAXSIZE;/Q-front=(Q-front+1)%

58、MAXSIZE;/* *重新设置队头指针重新设置队头指针* */ /return TRUE; /return TRUE; /* *操作成功操作成功* */ / 3.2.3 3.2.3 队列的顺序存储结构队列的顺序存储结构-循环队列（续）循环队列（续）数据结构C语言描述出出 版版 社社除了上述队列外，还有一种限定性数据结构，是双端队列除了上述队列外，还有一种限定性数据结构，是双端队列（Deque）如图）如图3.13所示所示 。双端队列是限定插入、删除在表的两端进行的线性表。这两端双端队列是限定插入、删除在表的两端进行的线性表。这两端分别称作端点，分别称作端点， 记作记作end1和和end2。可以

59、用一个铁轨转轨网。可以用一个铁轨转轨网络来比喻双端队列，如图络来比喻双端队列，如图3.13 (a)所示。所示。端点端点1 端点端点2a1 a2 an入队入队 出队出队 出队入队出队入队 (b)(b)图图3.13 3.13 双端队列双端队列(a)(a) 尽管双端队列尽管双端队列看起来似乎比栈和看起来似乎比栈和队列更灵活，但实队列更灵活，但实际上在程序系统中，际上在程序系统中，不如栈和队列应用不如栈和队列应用广泛，故在此不作广泛，故在此不作详细讨论。详细讨论。 3.2.3 3.2.3 队列的顺序存储结构队列的顺序存储结构-循环队列（续）循环队列（续）数据结构C语言描述出出 版版 社社3.3 栈和队

60、列的应用栈和队列的应用1 1、数制转换、数制转换 假设要将十进制数假设要将十进制数N N转换为转换为d d进制数，一个简单的进制数，一个简单的转换算法是重复下述两步，直到转换算法是重复下述两步，直到N N等于零。等于零。步骤一：步骤一：X = N mod d (X = N mod d (其中其中modmod为求余运算为求余运算) )步骤二：步骤二：N = N div d (N = N div d (其中其中divdiv为整除运算为整除运算) )算法如下：算法如下：数据结构C语言描述出出 版版 社社void Conversion(int N,intvoid Conversion(int N,int d) d)/ /* *将将N N进制数，进制数， 转换为转换为d d进制数进制数* */ / Stack S Stack S； intint x x； /