第二章 线性数据结构 ch2_3队列 《软件技术知识基础》 .pptVIP

* * 第二章 线性结构 一、队列的定义和运算 二、顺序队列 三、链式队列 四、队列的应用 五、小结 第 3 节 队列 一、队列的定义和基本运算 队列的定义 ? 队列是限定在表的一端进行插入，在表的另一端进行删除的线性表。 a1 , a2 , a3 , a4 , ………… an-1 , an 出队 入队 队头 队尾 ? 特点：先进先出（FIFO） 队尾(rear):允许插入的一端。 对头(front)：允许删除的一端 ? 队列的存储结构：顺序和链式 一、队列的定义和基本运算 2. 队列的基本运算 (1) 队列初始化 　 构造一个空队列。 (2) 入队 对已存在的队列Q，在队尾插入一个新的元素。 (3) 出队 对已存在的队列Q，删除队头元素，并返回其值。 (4 ) 判队空 对已存在的队列Q，若为空队，则返回1，否则返回0。 实现：用一维数组实现sq[M] front=-1 rear=-1 1 2 3 4 5 0 队空 1 2 3 4 5 0 front J1,J2,J3入队 J1 J2 J3 rear rear 1 2 3 4 5 0 J4,J5,J6入队 J4 J5 J6 front 设两个指针front,rear,约定： rear指示队尾元素； front指示队头元素前一位置 初值front=rear=-1 空队列条件：front==rear 入队列：sq[++rear]=x; 出队列：x=sq[++front]; rear rear front rear 1 2 3 4 5 0 J1,J2,J3出队 J1 J2 J3 front front front 二、顺序队列 若有J7还能入队吗？ 解决方案： ? 　循环队列——基本思想： 把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0;　 0 M-1 1 front rear …... …... 二、顺序队列 存在问题：设数组sq[M]，长度为M则： 当front=-1,rear=M-1时，再有元素入队发生溢出——真溢出 当front?-1,rear=M-1时，再有元素入队发生溢出——假溢出 0 1 2 3 4 5 rear front 1 3 0 2 4 5 J4 J5 J6 rear front J8 J7 解决方案： 1.另外设一个标志num以区别队空、队满： 出队:当num=Max时队满 入队:当num=0时队空 书74页(部分代码修改) 2.少用一个元素空间： 队空：front==rear 队满：(rear+1)%Max==front 1.队列初始化 SeQueue *init( ) 2.判队空 int Empty_SeQ( SeQueue *q ) 3.判队满 int Full_SeQ( SeQueue *q ) 4.入队 int In_SeQ( SeQueue *q , datatype x ) 5.出队 int Out_SeQ( SeQueue *q , datatype *x ) 二、顺序队列 ? 循环队列运算 循环队列类型定义 typedef struct { datatype data[Max] ; int front ; int rear ; int num; } SeQueue; 1.队列初始化 SeQueue *init( ) { SeQueue *q ; q=(SeQueue *)malloc( sizeof ( SeQueue )); q-front = q-rear = -1 ; q-num=0 ; return q ; } 二、顺序队列 ? 循环队列运算 循环队列类型定义 typedef struct { datatype data[Max] ; int front ; int rear ; int num; } SeQueue; q-front=-1 q-rear=-1 1 2 . . Max-1 0 空队 2.判队空 int Empty_SeQ(SeQueue *q) { if ( q- num==0 ) return 1; else return 0; } 二、顺序队列 ? 循环队列运算 循环队列类型定义 typedef struct { datatype data[Max] ; int front ; int rear ; int num; } SeQueue; 3.判队满 int Full_SeQ(SeQueu