电子科技大学 软件技术基础 3.3f 主讲教师：刘民岷 A■ 航空航天学院 软件技术基础课程组
软件技术基础 3.3 堆栈和队列 主讲教师：刘民岷 航空航天学院 软件技术基础课程组
2Ni VQueue 队列是一种特殊的线性表，它只允许在表的前端（front) 进行删除操作，而在表的后端（rear)进行插入操作。 进行插入操作的端称为队尾，进行删除操作的端称为队头。 队列中没有元素时，称为空队列。 ·队列具有先进先出(FFO)【 的特点。 队列空的条件：front=rear 0 队列满的条件： rear MaXSIze 出队 入队 删除 a1a2.… an 插入 front rear 电子科技大学刘民岷 堆栈和队列 2
电子科技大学 刘民岷 2 2 队列Queue 堆栈和队列 • 队列是一种特殊的线性表，它只允许在表的前端（front） 进行删除操作，而在表的后端（rear）进行插入操作。 • 进行插入操作的端称为队尾，进行删除操作的端称为队头。 • 队列中没有元素时，称为空队列。 • 队列具有先进先出（FIFO）的特点。 • 队列空的条件： front = rear • 队列满的条件： rear = MAXSIZE a1 a2 … an 入队 插入 出队 删除 front rear
2.1 V Y SETNULL(Q){置空队列：将队列初始化为空； EMPTY(Q){队列判空}：若队列为空，返回true,否则返回false: ENTER(Q,X){入队列}：在队列尾加入元素x,x成为新对尾元素； DELETE(Q){出队列：删除队列头元素； GETHEAD(Q){取头元素}：返回对头数据元素。 电子科技大学刘民岷 堆栈和队列 3
电子科技大学 刘民岷 3 2.1 队列的基本操作 堆栈和队列 • SETNULL(Q){置空队列}:将队列初始化为空； • EMPTY(Q){队列判空}:若队列为空，返回true，否则返回false; • ENTER(Q,X){入队列}:在队列尾加入元素x，x成为新对尾元素； • DELETE(Q){出队列}:删除队列头元素； • GETHEAD(Q){取头元素}:返回对头数据元素
2.2 队列的结构描述如下： 入队 define struct elemtype queue[MAXNUM+1]; /数组第一个元素是queue[O] int front; int rear; a /结构定义 rear queuetype; queuetype Q; /定义一个队列Q a1-1 ●队头指针front总是指向队头元素的 。。 前一个位置； 2 a2 ●队尾指针rear总是指向队尾元素的位 a 队头 置。 0 ●出队操作都是： Front front=front+1 出队 x queue [front ] 电子科技大学刘民岷 堆栈和队列 4
电子科技大学 刘民岷 4 2.2 队列的顺序存储结构 堆栈和队列 … ai ai-1 … a2 a1 rear 队头 Front n i 1 2 0 出队 •队列的结构描述如下： 入队 define struct {elemtype queue[MAXNUM+1]; //数组第一个元素是queue[0] int front; int rear; }queuetype; //结构定义 queuetype Q; //定义一个队列Ｑ 队头指针front总是指向队头元素的 前一个位置； 队尾指针rear总是指向队尾元素的位 置。 出队操作都是： front = front +1 ； x = queue [front ]；
2.2V 1)顺序队列的出、入对操作 (a)空队列 front rear (b)A、B、C、D、E入队 入队时，rear在变 A BC D E front rear (c)A、B、C出队 出队时，front在变 D E 电子科技大学刘民岷 front 堆栈和队ear 5
电子科技大学 刘民岷 5 2.2 队列的顺序存储结构 堆栈和队列 1）顺序队列的出、入对操作 （a）空队列 （b）A、B、C、D、E入队 （c）A、B、C出队 A B C D E front rear front rear D E front rear 入队时，rear在变 出队时，front在变
2.2V CT 1)顺序队列的出、入对操作 (d)F、G、H入队 D E F GH front 1 rear (e)D、E、F、G、H出队，出现假“溢出” front 1 rear 注：一方面队列中是空的，另一方面又出现溢出。显然，这是逻 辑设计上的问题。 解决办法--一引入循环队列（首尾相连的队列) 电子科技大学刘民岷 堆栈和队列 6
电子科技大学 刘民岷 6 2.2 队列的顺序存储结构 堆栈和队列 1）顺序队列的出、入对操作 （d）F、G、H入队 （e）D、E、F、G、H出队，出现假“溢出” 注：一方面队列中是空的，另一方面又出现溢出。显然，这是逻 辑设计上的问题。 • 解决办法---- 引入循环队列（首尾相连的队列） front D E F G H rear front rear
2.2V CI 2)循环队列 2 3 >队空条件 front rear MAXSIZE front >队满条件 rear front rear+1 3 2 front rear MAXSIZE +1 83 4 (%---求模运算符) a MAXSIZE a 1 81+1 i+1 front rear 电子科技大学刘民岷 堆栈和队列 7
电子科技大学 刘民岷 7 2.2 队列的顺序存储结构 堆栈和队列 2）循环队列 队空条件 front = rear ； 队满条件 front = rear+1 front = rear % MAXSIZE +1 (%----求模运算符) rear front 1 2 3 MAXSIZE ... 1 2 3 4 ... i rear i+1 front ... MAXSIZE a1 a2 a3 ai ai+1
2.2V CT 3)顺序队列入队算法 00001:/顺序队列的入队算法 00002: 00003: 三三三三三=三三三发三三=三发三三三发三三三三三三三三学 00004:define true 1 oooos:define false o 0o006:int enter(queuetype *q,elemtype x) 00007: if(g->rear>=MAXNUM) 线源清况之一飘列赏 00008: return(false); 00009: else 00010: 00011: q->rear++; 00012: q->queue[q->rear]=x; 00013: return(true); 00014: 00015: 电子科技大学刘民岷 堆栈和队列 8
电子科技大学 刘民岷 8 2.2 队列的顺序存储结构 堆栈和队列 3）顺序队列入队算法
2.2V CT 4)顺序队列出队算法 00001:/顺序队'列的出对算法 00002: 00003: /================= 00004: 00005: elemtype delete(queuetype *q) 00006: if(q->front==q->rear) /川飘列空 00007: return(NIL); 00008: else 00009: 00010: q->front++; 00011: return(q->queue[q->front]); 00012: 00013: 电子科技大学刘民岷 堆栈和队列 9
电子科技大学 刘民岷 9 2.2 队列的顺序存储结构 堆栈和队列 4）顺序队列出队算法
2.3V 用带头结点的单链表作为队列的存储结构，称为队列的链 式存储结构。 data next 数据域指针域 。存储结构的C语言描述， struct node (elemtype data; struct node *next; Struct qtype node *front: node *rear;) 电子科技大学刘民岷 堆栈和队列 10
电子科技大学 刘民岷 10 2.3 队列的链式存储结构 堆栈和队列 • 用带头结点的单链表作为队列的存储结构，称为队列的链 式存储结构。 • 存储结构的C语言描述， struct node {elemtype data; struct node *next;} Struct qtype {node *front; node *rear;} data next 数据域 指针域