数据结构：队列

ADT Queue{ 数据对象：D={ai|ai∈ElemSet, i=1,2, …,n, n≥0} 数据关系：R1={<ai-1,ai>|ai-1,ai∈D, i=1,2, …,n }             约定a1为队列头，an为队列尾。 基本操作：     InitQueue( &Q )       操作结果：构造一个空队列Q。     DestroyQueue ( &Q )       初始条件：队列Q已存在。       操作结果：销毁队列Q。     ClearQueue ( &Q )       初始条件：队列Q已存在。       操作结果：将Q清为空队列。     QueueEmpty( Q )       初始条件：队列Q已存在。       操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。     QueueLength( Q )       初始条件：队列Q已存在。       操作结果：返回Q的数据元素个数，即队列的长度。     GetHead( Q, &e )       初始条件：队列Q已存在且非空。       操作结果：用e返回Q的队头元素。     EnQueue( &Q, e )       初始条件：队列Q已存在。       操作结果：插入元素e为Q的新的队尾元素。     DeQueue( &Q, &e )       初始条件：队列Q已存在且非空。       操作结果：删除Q的队头元素，并用e返回其值。 QueueTraverse( Q, visit() )       初始条件：队列Q已存在且非空。       操作结果：从队头到队尾依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。

}ADT Queue

队列有两种实现方法

1. 循环队列

先看看它的原理

进而得到它的代码如下

#include<stdio.h> #include<stdlib.h> #define MAXQSIZE 100//队列的最大长度 #define FALSE 0 #define TRUE 1 #define ERROR -1 #define OVERFLOW -1 #define OK 1 typedef int QElemType; typedef int Status; typedef struct{ QElemType *base; int front;//头指针，若队列不空，指向队列头元素 int rear;//尾指针，若队列不空，指向队列尾元素的下一个位置 }SqQueue; //循环队列的基本操作实现 Status InitQueue(SqQueue*Q) { Q->base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType)); if(!Q->base) return ERROR; Q->front=Q->rear=0; } Status DestroyQueue(SqQueue* Q) { free(Q->base); Q->base=NULL; Q->front=Q->rear=0; return OK; } Status ClearQueue(SqQueue*Q) { Q->front=Q->rear=0; return OK; } Status QueueEmpty(SqQueue Q) { if(Q.front==Q.rear) return TRUE; else return FALSE; } int QueueLength(SqQueue Q) { return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; } Status GetHead(SqQueue Q,QElemType *e) { *e=Q.base[Q.front]; return OK; } Status EnQueue(SqQueue* Q,QElemType e) { if((Q->rear+1)%MAXQSIZE==Q->front) return ERROR;//判断是否满队列 Q->base[Q->rear]=e; Q->rear=(Q->rear+1)%MAXQSIZE; return OK; } Status DeQueue(SqQueue *Q,QElemType *e) { if(Q->front==Q->rear) return ERROR; *e=Q->base[Q->front]; Q->front=(Q->front+1)%MAXQSIZE; return OK; } 2. 链队列

代码如下：

#include<stdio.h> #include<stdlib.h> #define FALSE 0 #define TRUE 1 #define ERROR -1 #define OVERFLOW -1 #define OK 1 typedef int QElemType; typedef int Status; typedef struct QNode{ QElemType data; struct QNode*next; }QNode; typedef struct{ QNode *front;//头指针 QNode * rear;//尾指针， }LinkQueue; //链队列的基本操作实现 Status InitQueue(LinkQueue*Q) { Q->front=Q->rear=(QNode*)malloc(sizeof(QNode)); if(!Q->front) return ERROR; Q->front->next=NULL; } Status DestroyQueue(LinkQueue* Q) { while(Q->front) { Q->rear=Q->front->next; free(Q->front); Q->front=Q->rear; } return OK; } Status ClearQueue(LinkQueue*Q) { QNode *p=Q->front->next,*q; while(p) { q=p->next; free(p); p=q; } Q->rear=Q->front; Q->front->next=NULL; return OK; } Status QueueEmpty(LinkQueue Q) { if(Q.front==Q.rear) return TRUE; else return FALSE; } int QueueLength(LinkQueue Q) { int i=0; QNode* p=Q.front->next; while(p) { i++; p=p->next; } return i; } Status GetHead(LinkQueue Q,QElemType *e) { *e=Q.front->next->data; return OK; } Status EnQueue(LinkQueue* Q,QElemType e) { QNode*s; s=(QNode*)malloc(sizeof(QNode)); if(!s) return ERROR; s->data=e; s->next=NULL; Q->rear->next=s; Q->rear=s; return OK; } Status DeQueue(LinkQueue *Q,QElemType *e) { QNode*p; if(Q->front==Q->rear) return ERROR; p=Q->front->next; *e=p->data; Q->front->next=p->next; if(Q->rear==p) Q->rear=Q->front; free(p); return OK; }