队列简称队，它也是一种操作受限的线性表，其限制为仅允许在表的一端进行插入操作，而在表的另一端进行删除操作。
把队列的结构类型定义及其基本算法做成头文件
头文件(如果把头文件和程序代码都放在一个工程里，则头文件不能用< >（只有系统头文件才能用），在工程里面的头文件，在主程序调用时，用“”)
顺序
代码语言：javascript复制//<shujujiegou_duilie.h>typedef int ElemType; typedef struct { ElemType date[MaxSize];//存放队中元素 int front,rear;//队头和队尾指针}SqQueue;//环队类型
//队空的条件：q->front=q->rear;/**************初始化队列****************/void chushihua(SqQueue *&q){//构造一个空队列q，将front和rear指针均设置成初始状态，即-1值 q=(SqQueue *)malloc(sizeof(SqQueue)); q->front=q->rear=0; }/*************销毁队列******************/void xiaohui(SqQueue *&q){//释放q占用的存储空间 free(q);}/**************判断队列是否为空**********/bool panduanshifouweikong(SqQueue *q){//为空返回真，否则返回假 return(q->front==q->rear);}/**************进队列*******************/bool jinduilie(SqQueue *&q,ElemType e){ if((q->rear 1)%MaxSize==q->front)//队满上溢出 return false; //返回假 q->rear=(q->rear 1)%MaxSize;//队尾增1 q->date[q->rear]=e;//rear位置插入元素e return true;//返回真}/**************出队列*********************/bool chuduilie(SqQueue *&q,ElemType &e){ if(q->front==q->rear)//队空下溢出 return false; q->front=(q->front 1)%MaxSize; e=q->date[q->front]; return true; }链式队列
代码语言：javascript复制#include <stdlib.h>typedef int ElemType; typedef struct qnode { ElemType date;//存放元素 struct qnode *next;//队头和队尾指针}DataNode;//链队数据结点的类型typedef struct { DataNode *front;//指向队首指针 DataNode *rear;//指向队尾指针}LinkQuNode;//链队结点的类型//队空的条件 ：q->rear==NULL(也可以为q->front==NULL)//元素e的进队操作：新建一个结点存放元素e（由p指向它），将结点p插入作为尾结点//出队操作：取出队首结点的data值并将其删除/**************初始化队列****************/void chushihua(LinkQuNode *&q){ q=(LinkQuNode *)malloc(sizeof(LinkQuNode)); q->front=q->rear=NULL; }/*************销毁队列******************/void xiaohui(LinkQuNode *&q){ DataNode *pre=q->front,*p;//pre指向队首结点 if (pre!=NULL) { p=pre->next;//p指向结点pre的后继结点 while (p!=NULL)//p不空循环 { free(pre);//释放pre结点 pre=p;p=p->next;//pre，p同步后移 } free(pre);//释放最后一个数据结点 } free(q);//释放链队结点}/**************判断队列是否为空**********/bool panduanshifouweikong(LinkQuNode *q){//为空返回真，否则返回假 return(q->rear==NULL);}/**************进队列*******************/bool jinduilie(LinkQuNode *&q,ElemType e){ DataNode *p; p=(DataNode *)malloc(sizeof(DataNode));//创建新结点 p->date=e; p->next=NULL; if (q->rear==NULL) //若链队为空，则新结点既是队首又是队尾结点 { q->front=q->rear=p; } else //若链队不空 { q->rear->next=p;//将结点p链到队尾，并将rear指向它 q->rear=p; }}/**************出队列*********************/bool chuduilie(LinkQuNode *&q,ElemType &e){ DataNode *t; if(q->rear==NULL)//原来队列为空 return false; t=q->front;//t指向首节点 if (q->front==q->rear)//原来队列中只有一个数据结点时 q->front=q->rear=NULL; else //原来队列中有两个或两个以上结点时 q->front=q->front->next; e=t->date; free(t); return true; }通过下面这个运用队列的例子，可以加深印象
利用队列求解报数问题。设有n个人站成一排，从左向右的编号分别为1～n，现在从左往右报数“1,2,1，2，…”，数到“1”的人出列，数到“2”的立即站到队伍的最右端。报数过程反复进行，直到n个人都出列为止。要求给出他们的出列顺序。
代码语言：javascript复制#include <stdio.h>#include <shujujiegou_duilie.h>void number(int n){int i; ElemType e; SqQueue *q;//环形队列指针q chushihua(q);//初始化队列q for (i=1;i<=n;i )//构建初始序列 { jinduilie(q,i); } printf("报数出列顺序："); while (!panduanshifouweikong(q)) //队列不空循环 { chuduilie(q,e);//出队一个元素e printf("%d ",e);//输出元素编号 if (!panduanshifouweikong(q))//队列不空 { chuduilie(q,e);//出队一个元素e jinduilie(q,e);//将刚出队的元素进队 } } printf("n"); xiaohui(q);//销毁队列q}int main(){ int i,n=8; printf("初始队列："); for (i=1;i<=n;i ) { printf("%d ",i); } printf("n"); number(n); return 1;}运行结果
