数据结构第三章栈和队列.ppt

3．4 队列 a1 a2 a3 an 入队列 队头 队尾 出队列 队 列 的 示 意 图 队列的特点 先进先出 第一个入队的元素在队头，最后一个入队的元素在队尾， 第一个出队的元素为队头元素， 最后一个出队的元素为队尾元素 3．4 队列 二 队列的基本操作 1）初始化操作 2）销毁操作 3）置空操作 4）判空操作 5）取队头元素操作 6）入队操作 7）出队操作 rear front J1 J2 rear front J2 (b)J1,J2相继入队列 (c)J1出队 (d)J3,J4和J5相继入队之后,J2出队 （a)空队列 rear front -1 0 1 2 3 4 3. 4 队列 rear front J5 J4 J3 front,rear均为整数 用箭头指示只是为了直观 又有J6入队, 怎么办？ 3．4 队列 #define MAX 50 /*数据结构定义*/ struct squeue {elemtype queue[MAX]; int front; int rear;}; 初始化 Init（struct squeue *q) { q-front=-1; q-rear=-1; } int insert_queue(int x，struct squeue *q) /*入队列*/ {if((*q).rear==MAX-1) return(0); q-rear++; q-queue[q-rear]=x ;return(1); } int del_queue(struct squeue *q) /*出队列*/ { if(q-rear==q-front) return(0); q-front++; return(q-queue[q-front]); } 3. 4 队列 3 . 循环队列 front rear J5 J3 J4 3 1 2 4 0 5 rear 5 4 0 3 1 2 front J5 J6 J7 J8 J3 J4 front rear 5 4 0 3 1 2 (b)队空 (c)队满 队空、队满 都有front=rear 如何判断循环队列 队空、队满？ J6 rear 3. 4 队列 有两种方法：1）另设一个标志位以区分队空、队满。2）少用一个存储单元，队满条件:front=rear+1; front 5 4 0 3 1 2 J6 J7 J8 J4 J5 （d） rear 3. 4 队列 1）初始化操作 功能：建一个空队列Q； 算法： struct squeue { elemtype queue[MAX]; int front; int rear; }; int InitQueue_Sq(struct squeue *q) { //构造一个空队列Q q-front=q-rear=0; return (1)} 二 循环队列的基本操作算法 front rear 5 4 0 3 1 2 建一个空队列Q 3. 4 队列 6）入队操作 功能：将元素 x 插入队尾 front rear 5 4 0 3 1 2 J1 J3 J2 x front rear 5 4 0 3 1 2 J1 J3 J2 元素 x 入队前 元素 x 入队后 3. 4 队列 求余运算 3.4.2 循环队列——队列的顺序存储和实现 int insert_queue(int x,struct squeue *q) /*入队列*/ {if((q-rear+1)%MAX==q-front)return(0); q-rear=(q-rear+1)%MAX; q-queue[q-rear]=x; return(1); } 3. 4 队列 7）出队操作 功能：删除队头元素； front rear 5 4 0 3 1 2 J1 J3 J2 出队操作前 front rear 5 4 0 3 1 2 J1 J3 J2 出队操作后 3. 4 队列 int del_queue(struct squeue *q) /*出队列*/{ if(q-rear==q-front) return(0); q-front=(q-front+1)%MAX; return(q-queue[q-front]);} 3