C

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

顺序队列一次性要分配大量保证够用的空间，效率较高，因为是基于数组的，长度也是固定的。可以实现变长，但是一般代价较高。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

无头指针非循环队列，队列头元素在[0]单元，头元素总在[0]单元，所以不必设头指针。缺点是出列时候要大量移动元素，效率很低

    队列的定义：

struct SqQueuel { QElemType *base; //初始化的动态分配存储空间 int rear; //尾指针，若队列不为空，指向队列尾元素的下一个位置 int queuesize; //当前分配的存储容量(以sizeof(QElemType)为单位) };

基本操作的函数定义：

/*操作结果：构造一个空队列Q。*/ void InitQueue(SqQueuel &Q) /*初始条件：队列已Q存在。*/ /*操作结果：销毁队列Q，Q不再存在。*/ Status DestroyQueue(SqQueuel &Q) /*初始条件：队列已Q存在。*/ /*操作结果：将Q清空为空队列。*/ Status ClearQueue(SqQueuel &Q) /*初始条件：队列Q已存在。*/ /*操作结果：若队列Q为空队列，则返回TRUR；否则返回FALSE。*/ Status QueueEmpty(SqQueuel Q) /*初始条件：队列Q已存在。*/ /*操作结果：返回Q的元素个数，即队列的长度。*/ int QueueLength(SqQueuel Q) /*初始条件：队列Q已存在。*/ /*操作结果：若队列不空，则用e返回Q的队头元素，并返回OK；否则，返回ERROR*/ Status GetHead(SqQueuel Q,QElemType &e) /*初始条件：队列Q已存在。*/ /*操作结果：插入元素e为Q的新的队尾元素。*/ void EnQueue(SqQueuel &Q,QElemType e) /*初始条件：队列Q已存在。*/ /*操作结果：若队列不空，则删除Q的队头元素，用e返回其值，并返回OK;否则,返回ERROR。*/ Status DeQueue(SqQueuel &Q,QElemType &e) /*初始条件：队列Q已存在。*/ /*操作结果：从队头到队尾依次对队列Q中每个元素调用函数vi()*/ void QueueTraverse(SqQueuel Q,void(*vi)(QElemType))

下面是函数的实现

 构造一个空队列Q

/*操作结果：构造一个空队列Q。*/ void InitQueue(SqQueuel &Q) { Q.base=(QElemType*)malloc(QUEUE_INIT_SIZE*sizeof(QElemType)); if(!Q.base){ printf("构造队列失败!程序退出!\n"); exit(0); }else{ Q.rear=0; //空队列，尾指针为0 Q.queuesize=QUEUE_INIT_SIZE; //初始存储容量 } } 销毁队列Q

/*初始条件：队列已Q存在。*/ /*操作结果：销毁队列Q，Q不再存在。*/ Status DestroyQueue(SqQueuel &Q) { free(Q.base); //释放存储空间 Q.base=NULL; Q.rear=Q.queuesize=0; return OK; } 清空为空队列

/*初始条件：队列已Q存在。*/ /*操作结果：将Q清空为空队列。*/ Status ClearQueue(SqQueuel &Q) { Q.rear=0; return OK; }

队列进行判空

/*初始条件：队列Q已存在。*/ /*操作结果：若队列Q为空队列，则返回TRUR；否则返回FALSE。*/ Status QueueEmpty(SqQueuel Q) { if(Q.rear==0) return TRUE; else return FALSE; } 返回队列个数

/*初始条件：队列Q已存在。*/ /*操作结果：返回Q的元素个数，即队列的长度。*/ int QueueLength(SqQueuel Q) { return Q.rear; } 返回队列头元素

/*初始条件：队列Q已存在。*/ /*操作结果：若队列不空，则用e返回Q的队头元素，并返回OK；否则，返回ERROR*/ Status GetHead(SqQueuel Q,QElemType &e) { if(Q.rear) { e=*Q.base; return OK; }else{ return ERROR; } } 插入到队尾元素

/*初始条件：队列Q已存在。*/ /*操作结果：插入元素e为Q的新的队尾元素。*/ void EnQueue(SqQueuel &Q,QElemType e) { if(Q.rear==Q.queuesize) //当前存储空间已满 //增加新的存储空间 Q.base=(QElemType*)realloc(Q.base,(Q.queuesize+QUEUE_INCREMENT)*sizeof(QElemType)); if(!Q.base) //分配失败 { printf("分配异常!退出操作!\n"); exit(0); }else{ Q.queuesize+=QUEUE_INCREMENT; //增加存储容量 Q.base[Q.rear++]=e; //入队新元素，尾指针+1 } } 删除队头元素

/*初始条件：队列Q已存在。*/ /*操作结果：若队列不空，则删除Q的队头元素，用e返回其值，并返回OK;否则,返回ERROR。*/ Status DeQueue(SqQueuel &Q,QElemType &e) { int i; if(Q.rear) //队列不为空 { e=*Q.base; for(i=1;i<Q.rear;i++) Q.base[i-1]=Q.base[i]; //依次前移队列元素 Q.rear--; //尾指针前移 return OK; }else{ return ERROR; } } 正序打印队列

/*初始条件：队列Q已存在。*/ /*操作结果：从队头到队尾依次对队列Q中每个元素调用函数vi()*/ void QueueTraverse(SqQueuel Q,void(*vi)(QElemType)) { int i; for(i=0;i<Q.rear;i++) vi(Q.base[i]); printf("\n"); }

嗯下面就是在VC中的测试：

//非循环队列，队列头元素在[0]位置 #include<stdio.h> #include<stdlib.h> #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define QUEUE_INIT_SIZE 10 //队列存储空间的初始化分配量 #define QUEUE_INCREMENT 2 //队列存储空间的分配增量 typedef int QElemType; typedef int Status; struct SqQueuel { QElemType *base; //初始化的动态分配存储空间 int rear; //尾指针，若队列不为空，指向队列尾元素的下一个位置 int queuesize; //当前分配的存储容量(以sizeof(QElemType)为单位) }; void vi(QElemType e) { printf("%d ",e); } void printf(QElemType i) { printf("%d",i); } /*操作结果：构造一个空队列Q。*/ void InitQueue(SqQueuel &Q) { Q.base=(QElemType*)malloc(QUEUE_INIT_SIZE*sizeof(QElemType)); if(!Q.base){ printf("构造队列失败!程序退出!\n"); exit(0); }else{ Q.rear=0; //空队列，尾指针为0 Q.queuesize=QUEUE_INIT_SIZE; //初始存储容量 } } /*初始条件：队列已Q存在。*/ /*操作结果：销毁队列Q，Q不再存在。*/ Status DestroyQueue(SqQueuel &Q) { free(Q.base); //释放存储空间 Q.base=NULL; Q.rear=Q.queuesize=0; return OK; } /*初始条件：队列已Q存在。*/ /*操作结果：将Q清空为空队列。*/ Status ClearQueue(SqQueuel &Q) { Q.rear=0; return OK; } /*初始条件：队列Q已存在。*/ /*操作结果：若队列Q为空队列，则返回TRUR；否则返回FALSE。*/ Status QueueEmpty(SqQueuel Q) { if(Q.rear==0) return TRUE; else return FALSE; } /*初始条件：队列Q已存在。*/ /*操作结果：返回Q的元素个数，即队列的长度。*/ int QueueLength(SqQueuel Q) { return Q.rear; } /*初始条件：队列Q已存在。*/ /*操作结果：若队列不空，则用e返回Q的队头元素，并返回OK；否则，返回ERROR*/ Status GetHead(SqQueuel Q,QElemType &e) { if(Q.rear) { e=*Q.base; return OK; }else{ return ERROR; } } /*初始条件：队列Q已存在。*/ /*操作结果：插入元素e为Q的新的队尾元素。*/ void EnQueue(SqQueuel &Q,QElemType e) { if(Q.rear==Q.queuesize) //当前存储空间已满 //增加新的存储空间 Q.base=(QElemType*)realloc(Q.base,(Q.queuesize+QUEUE_INCREMENT)*sizeof(QElemType)); if(!Q.base) //分配失败 { printf("分配异常!退出操作!\n"); exit(0); }else{ Q.queuesize+=QUEUE_INCREMENT; //增加存储容量 Q.base[Q.rear++]=e; //入队新元素，尾指针+1 } } /*初始条件：队列Q已存在。*/ /*操作结果：若队列不空，则删除Q的队头元素，用e返回其值，并返回OK;否则,返回ERROR。*/ Status DeQueue(SqQueuel &Q,QElemType &e) { int i; if(Q.rear) //队列不为空 { e=*Q.base; for(i=1;i<Q.rear;i++) Q.base[i-1]=Q.base[i]; //依次前移队列元素 Q.rear--; //尾指针前移 return OK; }else{ return ERROR; } } /*初始条件：队列Q已存在。*/ /*操作结果：从队头到队尾依次对队列Q中每个元素调用函数vi()*/ void QueueTraverse(SqQueuel Q,void(*vi)(QElemType)) { int i; for(i=0;i<Q.rear;i++) vi(Q.base[i]); printf("\n"); } int main() { int i; int k; int ch; Status j; QElemType d; SqQueuel Q; InitQueue(Q); printf("成功构造非循环队列!\n"); printf("请输入构造时队列数据个数："); scanf("%d",&k); printf("请依次输入数据元素:\n"); for(i=1;i<=k;i++) { scanf("%d",&d); EnQueue(Q,k); //依次入队k个元素 } printf("****************************\n"); printf("1、增加元素\n2、判空队列\n3、队列长度\n"); printf("4、队头元素\n5、队头出列\n6、清空队列\n"); printf("7、打印队列\n8、销毁队列\n0、退出操作\n"); printf("****************************\n"); printf("请选择要进行的操作："); while(scanf("%d",&ch)&&ch!=0) { if(ch==1){ printf("请输入要进队的元素:"); scanf("%d",&k); EnQueue(Q,k); printf("%d元素成功进入队头!\n"); } if(ch==2){ if(QueueEmpty(Q)) printf("这是一个空队列!\n"); else printf("这不是一个空队列!\n"); } if(ch==3){ printf("队列的长度为：%d\n",QueueLength(Q)); } if(ch==4){ if(GetHead(Q,d)) printf("队头元素是%d\n",d); else printf("这是一个空队列!\n"); } if(ch==5){ if(DeQueue(Q,d)) printf("队头元素%d成功出列!\n",DeQueue(Q,d)); else printf("操作失败!\n"); } if(ch==6){ if(ClearQueue(Q)) printf("队列成功清空!\n"); } if(ch==7){ printf("队列中的元素为："); QueueTraverse(Q,printf); } if(ch==8) { if(DestroyQueue(Q)) { printf("队列成功销毁，操作退出!\n"); exit(0); } } printf("请选择要进行的操作："); } printf("成功退出操作!\n"); return 0; }