华中科技大学：《数据结构》课程教学资源（PPT课件讲稿）第三章 栈和队列 3.4 队列（排队,queue）

的 华中科技大学 计算机学院(5) 2001-3-26

2001-3-26 华中科技大学 数据结构 计算机学院(5)

3.4队列(排队, queue) 3.4.2链式队列:用带表头结点的单链表表示队列 般形式 (1)空队列: Q front data next Q. rear ///∧ 表头结点 (2)非空队列: data next Q. front an Q rear 表头结点队头结点 队尾结点 其中:Q. front队头(首)指针,指向表头结点 rear一 队尾指针,指向队尾结点 Q. front->data不放元素。 Q. front->next指向队首结点a1

3.4 队列（排队,queue) 3.4.2 链式队列: 用带表头结点的单链表表示队列 1.一般形式 (1)空队列: (2) 非空队列: 其中： Q.front----队头(首)指针,指向表头结点。 Q.rear----队尾指针，指向队尾结点。 Q.front->data 不放元素。 Q.front->next 指向队首结点a1。 /// ∧ data next 表头结点 /// data next 表头结点 a1 队头结点 an ∧ 队尾结点 ... Q.front Q.rear Q Q.front Q.rear Q

2.定义结点类型 (1)存放元素的结点类型 typedef struct Qnode i Elem Type data; //data为抽象元素类型 struct Qnode*next;//next为指针类型 } Qnode,* QueuePtr;/结点类型,指针类型 其中: Qnode-结点类型 data next QueuePtr-指向 Qnode的指针类型 (2)由头、尾指针组成的结点类型 typedef struct Qnode* front;/头指针 front Qnode*rear;/尾指针 rear } LinkQueue;//链式队列类型

2.定义结点类型 (1)存放元素的结点类型 typedef struct Qnode { ElemType data； //data为抽象元素类型 struct Qnode *next； //next为指针类型 }Qnode，*QueuePtr； //结点类型, 指针类型 其中：Qnode----结点类型 QueuePtr----指向Qnode的指针类型 (2)由头、尾指针组成的结点类型 typedef struct { Qnode *front； //头指针 Qnode *rear； //尾指针 }LinkQueue； //链式队列类型 data next front rear

3生成空队列算法 # define leng sizeof( Qnode)/求结点所占的单元数 LinkQueue InitQueue() //生成仅带表头结点的空队列Q i LinkQueue Q: //说明变量Q Q. front=Q.rear=( Queueptr)ma1loc(LENG);//生成表头结点 Q. front->next=NUI //表头结点的next为空指针 return Q; //返回Q的值 main LinkQueue que /*定义一个队列* que=InitQueueo

3.生成空队列算法 #define LENG sizeof(Qnode) //求结点所占的单元数 LinkQueue InitQueue( ) //生成仅带表头结点的空队列Q { LinkQueue Q； //说明变量Q Q.front=Q.rear=(QueuePtr)malloc(LENG)；//生成表头结点 Q.front->next=NULL； //表头结点的next为空指针 return Q； //返回Q的值 } main() { LinkQueue que; /*定义一个队列*/ que=InitQueue(); ……… }

4.(空队列时)插入新元素x data next Q. front 新结点X ///∧ rear 表头结点 Q front /// ∧ rear 表头结点 队头(尾)结点 (非空队列时)插入新元素y data next Q. front x|∧ y Q. rear 表头结点↑队头(尾) ---新结点 Q. front ∧ Q rear 表头结点队头结点′队尾结点

/// ∧ data next 表头结点 Q.front Q.rear Q x 新结点X /// 表头结点 Q.front Q.rear x ∧ X 队头(尾）结点 P 4.（空队列时）插入新元素x P /// 表头结点 Q.front Q.rear x ∧ 队头(尾） y data next /// 表头结点 Q.front Q.rear x 队头结点 y ∧ 新结点y 队尾结点 X （非空队列时）插入新元素y

插入新元素e的的算法(1) LinkQueue En Queue LinkQueue Q, ElemType e) I Qnode *p 说明变量p )=( Qnode*)ma1loc(LENG);//生成新元素结点 p->data=e //装入元素e p->next=NULL; //为队尾结点 Q. rear->next=p //插入新结点 Q rear=p; /修改尾指针 return Q: //返回Q的新值 main LinkQueue que 米定义一个队列来/ que=InitQueueo que=EnQueue(que) 10)

插入新元素e的的算法(1) LinkQueue EnQueue(LinkQueue Q, ElemType e) { Qnode *p； //说明变量p p=(Qnode *)malloc(LENG)； //生成新元素结点 p->data=e； //装入元素e p->next=NULL； //为队尾结点 Q.rear->next=p； //插入新结点 Q.rear=p； //修改尾指针 return Q； //返回Q的新值 } main() { LinkQueue que; /*定义一个队列*/ que=InitQueue(); que=EnQueue(que,10); }

插入新元素e的的算法{ int EnQueue(LinkQuelue *Q, ElemType e) i Qnode *p; //说明变量p p=( Qnode *)mallOc(LENG; //生成新元素结点 if(!p){ printf(“ OVERFLOW);//新结点生成失败 return ERROR p->data=e //装入元素e p->next=NULL //为队尾结点 Q->>next=p //插入新结点 Q->rear=p /修改尾指针 return OK: //成功返回 main LinkQueue que /*定义一个队列来/ que=InitQueueo EnQueue &que, 1o)

插入新元素e的的算法(2) int EnQueue(LinkQueue *Q, ElemType e) { Qnode *p； //说明变量p p=(Qnode *)malloc(LENG)； //生成新元素结点 if (!p) {printf(“OVERFLOW”); //新结点生成失败 return ERROR;} p->data=e； //装入元素e p->next=NULL； //为队尾结点 Q->rear->next=p； //插入新结点 Q->rear=p； //修改尾指针 return OK； //成功返回 } main() { LinkQueue que; /*定义一个队列*/ que=InitQueue(); EnQueue(&que,10); }

5.出队一删除队头结点 (1)若原队列有2个或2个以上的结点 P Q front a rear 表头结点队头结点 (a)执行:Q. front->next=p->next; Q. front Q rear 目 al 表头结点队头结点 (b)执行:free(p); Q. fron rear 目L a2+ 表头结点队头结点

5.出队----删除队头结点 (1)若原队列有2个或2个以上的结点 /// 表头结点 a1 队头结点 Q.front a2 ... Q.rear P /// 表头结点 a1 队头结点 Q.front a2 ... Q.rear P (a)执行：Q.front->next=p->next； (b)执行：free(p)； /// 表头结点 队头结点 Q.front a2 ... Q.rear P X

(2)若原队列只有1个结点 Q front Q rear ///∧ a1∧ 表头结点 队头结点 (a)执行:Q. front->next=p->next; Q front Q. 日 ∧ ∧ rear 表头结点队头结点 (b)执行:free(p); Q. front rear ∧ 表头结点 (c)执行:Q.rear=Q. front; Q. front Q s rear 表头结点

(2)若原队列只有1个结点 /// ∧ 表头结点 a1 ∧ 队头结点 Q.front Q.rear P (a)执行：Q.front->next=p->next； /// ∧ 表头结点 a1 ∧ 队头结点 Q.front Q.rear P (b)执行：free(p)； /// ∧ 表头结点 Q.front Q.rear P /// ∧ 表头结点 Q.front Q.rear (c)执行：Q.rear=Q.front； X X X X

出队算法 LinkQueue DelQueue (LinkQueue Q, Elem Type *e) I Qnode *p; //说明变量p if (Q front==Q rear) /若原队列为空 exit(" Empty quege");//退出去 p=Q. front->next //P指向队头结点 (来e)=p-data; //取出元素,e指向它 Q. front->next=p->next //删除队头结点 f( Q rear=p) //若原队列只有1个结点 Q rear=Q->front /修改尾指针 free(p /释放被删除结点的空间 return Q: //返回出队后的Q

出队算法: LinkQueue DelQueue(LinkQueue Q, ElemType *e) { Qnode *p； //说明变量p if (Q.front==Q.rear) //若原队列为空 exit("Empty queqe")； //退出去 p=Q.front->next； //P指向队头结点 (*e)=p->data； //取出元素,e指向它 Q.front->next=p->next； //删除队头结点 if (Q.rear==p) //若原队列只有1个结点 Q.rear=Q->front； //修改尾指针 free(p)； //释放被删除结点的空间 return Q； //返回出队后的Q }