03数据结构栈与队列2.docVIP

第三节 队列 一、逻辑结构 　　只能在一端(队尾rear)插入，在另一端(队头front)删除的线性表。 　　先进先出表FIFO(First In First Out) 基本操作：进/出队列 判别队列满/空 队列的应用背景：排队模型。排队问题无处不在，各种服务行业、甚至生产管理中都存在排队问题。 二、链式存储结构 Typedef struct queuenode //队列中的结点类型 { ElemType data; struct Node *link; }QueueNode; typedef struct //队列类型 { QueueNode *front,*rear; }LinkQueue; LinkQueue Q; 初始化空队列： Q.front==NULL Q.rear==NULL 1、入队列 Status LinkQueue_Enter(LinkQueue Q, ElemType e) { QueueNode *p; p=(QueueNode *)malloc(sizeof(QueueNode)); if(!p) return(OVERFLOW); p-data=e; p-link=NULL; if(Q.front==NULL) Q.front=Q.rear=p; else { Q.rear-link=p; Q.rear=p; } return(OK); } 2、出队列 Status LinkQueue_Leave(LinkQueue Q,ElemType e) { QueueNode *p; if(Q.front==NULL) return(UNDERFLOW); p=Q.front; Q.front=p-link; if(Q.rear==p) Q.rear=NULL; e=p-data; free(p); return(OK); } 3、销毁队列 void LinkQueue_Destroy(LinkQueue Q) { QueueNode *p; while(Q.front) { p=Q.front; Q.front=p-link; free(p); } Q.rear=NULL; } 三、顺序存储结构 动态顺序存储结构： #define QUEUE_SIZE 100 //初始化时分配的空间 typedef struct { ElemType *base; //存储空间的起始地址 int front,rear; } SqQueue; SqQueue Q; //定义一个队列结构 rear为下一个进队列元素的位置。 front在队列不空时，指向首元素； 在队列为空时，等于rear。 1、初始化队列 Status SqQueue_Init(SqQueue Q) { Q.base=malloc(QUEUE_SIZE*sizeof(ElemType)); if(!Q.base) return(OVERFLOW); Q.front=Q.rear=0; return(OK); } 队列空： Q.front==Q.rear 进队列：*(Q.base+Q.rear)=e; Q.rear++; 出队列：e=*(Q.base+Q.front); Q.front++; 队列满： Q.rear==QUEUE_SIZE =》假溢出 进队列：Q.rear =(Q.rear +1) % QUEUE_SIZE 出队列：Q.front=(Q.front+1) % QUEUE_SIZE 队列空：Q.front==Q.rear 当队列中有QUEUE_SIZE个元素时： Q.front==Q.rear =》必须浪费一个结点空间 队列满：(Q.rear +1) % QUEUE_SIZE == Q.front 2、入队列 Status SqQueue_Enter(SqQueue Q,ElemType e) { if((Q.rear +1) % QUEUE_SIZE==Q.front) return(OVERFLOW); *(Q.base+Q.rear)=e; Q.rear=(Q.rear +1) % QUEUE_SIZE; return(OK); } 3、出队列 Status SqQueue_Leave(SqQueue Q,ElemType e) { if(Q.rear==Q.front) return(UNDERFLOW); e=*(Q.ba