数据结构之队列

队列是一种先进先出（FIFO)的数据结构，下面是循环队列顺序存储方式

#include<stdio.h>
#include<stdlib.h>
#include<io.h>
#include<math.h>
#include<time.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20

typedef int Status;
typedef int QElemType;

// 循环队列的顺序结构
typedef struct{
QElemType data[MAXSIZE];
int front;
int rear; 
}SqQueue;

Status visit(QElemType c){
printf("%d ", c);
return OK;
}
//初始化一个空队列
Status InitQueue(SqQueue *Q){
Q->front = 0;
Q->rear = 0;
return OK; 
} 

//将Q清空
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;
} 

//返回Q元素的个数
int QueueLength(SqQueue Q){
return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
} 

//用e返回队列的队头元素
Status GetHead(SqQueue Q, QElemType *e){
if(Q.front == Q.rear)
    return ERROR;
*e = Q.data[Q.front];
return OK;
} 

//插入新的元素e
Status EnQueue(SqQueue *Q, QElemType e){
if((Q->rear + 1) % MAXSIZE == Q->front)
    return ERROR;
    Q->data[Q->rear] = e;
    Q->rear = (Q->rear + 1)%MAXSIZE;
    return OK;
} 

//删除队头元素，用e返回
Status DeQueue(SqQueue *Q, QElemType *e){
if(Q->front == Q->rear)
    return ERROR;
*e = Q->data[Q->front];
Q->front = (Q->front + 1) % MAXSIZE;
return OK;
} 

//从队头到队尾依次输出
Status QueueTraverse(SqQueue Q){
int i;
i = Q.front;
while((i + Q.front) != Q.rear){
    visit(Q.data[i]);
    i = (i + 1) % MAXSIZE;
}
printf("\n");
return OK;
} 
int main(){
Status j;
int i = 0, l;
QElemType d;
SqQueue Q;
InitQueue(&Q);
//%u表示无符号的十进制整数 
printf("初始化队列后，队列空否？%u(1:空 0:否)\n",QueueEmpty(Q));
printf("请输入整型队列元素(不超过%d个),-1为提前结束符: ",MAXSIZE-1);
do{
    d = i + 100;
    if(d == -1)
        break;
    i++;
    EnQueue(&Q,d); 
}while(i < MAXSIZE - 1);
printf("队列长度为: %d\n",QueueLength(Q));
printf("现在队列空否？%u(1:空 0:否)\n",QueueEmpty(Q));
printf("连续%d次由队头删除元素,队尾插入元素:\n",MAXSIZE);
for(l = 1; l <= MAXSIZE; l++){
    DeQueue(&Q,&d);
    printf("删除的元素是%d，插入的元素是：%d\n",d,l+1000);
    d = l + 1000;
    EnQueue(&Q, d);
}
l = QueueLength(Q);
printf("现在的队列元素为：\n");
QueueTraverse(Q);
printf("共向队尾插入了%d个元素\n",i+MAXSIZE);
if(l - 2 > 0)
    printf("现在由队头删除了%d个元素\n",l - 2);
while(QueueLength(Q)>2){
    DeQueue(&Q,&d);
    printf("删除的元素为%d\n",d);
}
j = GetHead(Q,&d);
if(j)
    printf("现在队头元素为：%d\n",d);
    ClearQueue(&Q);
    printf("清空队列后，队列空否？%u(1:空 0：否)\n",QueueEmpty(Q));
    return 0;
}   

下面是链队列的代码方式

#include<stdio.h>
#include<stdlib.h>
#include<io.h>
#include<math.h>
#include<time.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20

typedef int Status;
typedef int QElemType;

typedef struct QNode //用于定义链的结点 
{
   QElemType data;//定义结点的数据域 
   struct QNode *next;//定义 结点的指针域 
}QNode,*QueuePtr;//定义一个可以定义结点的名称，定义一个指    向结点的指针 

typedef struct        //定义链表的结构，包含两个结点指针    
{
 QueuePtr front,rear; 
}LinkQueue;

Status visit(QElemType c)//用于访问结点的数据域 
{
printf("%d ",c);
return OK;
}

/* 构造一个空队列Q */
Status InitQueue(LinkQueue *Q)
{ 
Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
//申请大小为结点结构的动态空间，第一个括号为指向结点指针，第二个括号为结点大小 
if(!Q->front)
    exit(OVERFLOW);
//xit(OVERFLOW)的含义就是，退出程序，并返回OVERFLOW的值给主调进程。
//其标准的使用范围为，当程序运算出现上溢时，退出程序并报错给主调进程。
Q->front->next=NULL;//头指针为栈顶 
return OK;
}

/* 销毁队列Q，就是什么都没有了 ，头结点都释放掉了*/
Status DestroyQueue(LinkQueue *Q)
{
while(Q->front)
{
     Q->rear=Q->front->next;
     //这里的Q->rear当一个临时指针使用取出一个头指针指向的结点free一个 
     free(Q->front);
     Q->front=Q->rear;
}
return OK;
}

/* 将Q清为空队列，头指针尾指针还在，都指向头结点 */
Status ClearQueue(LinkQueue *Q)
{
QueuePtr p,q;
Q->rear=Q->front;//先把尾结点提上来指向头结点 
p=Q->front->next;//把要删除的头结点的下一个给p 
Q->front->next=NULL;//把要头结点指向下一个的指针删除掉 
while(p)//一直到最后一个结点都释放掉 
{
     q=p;
     p=p->next;
     free(q);
}
return OK;
}

/* 若Q为空队列,则返回TRUE,否则返回FALSE */
Status QueueEmpty(LinkQueue Q)
{ 
if(Q.front==Q.rear)//指针相等就是空队列 ，也就是都指向头结点，注意头结点不放数据 
    return TRUE;
else
    return FALSE;
}

/* 求队列的长度 */
int QueueLength(LinkQueue Q)
{ 
int i=0;
QueuePtr p;
p=Q.front;
while(Q.rear!=p)
{
     i++;//用于计数 
     p=p->next;//指针向后 
}
return i;
}

/* 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR */
Status GetHead(LinkQueue Q,QElemType *e)
{ 
QueuePtr p;
if(Q.front==Q.rear)//先判断 
    return ERROR;
p=Q.front->next;
*e=p->data;
return OK;
}


/* 插入元素e为Q的新的队尾元素 */
Status EnQueue(LinkQueue *Q,QElemType e)
{ 
QueuePtr s=(QueuePtr)malloc(sizeof(QNode));
if(!s) /* 存储分配失败 */
    exit(OVERFLOW);
s->data=e;//先设置要插入的结点的数据域 
s->next=NULL;//把这个结点的指针置为空 
Q->rear->next=s;    /* 把拥有元素e的新结点s赋值给原队尾结点的后继，见图中① */
Q->rear=s;        /* 把当前的s设置为队尾结点，rear指向s，见图中② */
return OK;
}

/* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回    ERROR */
Status DeQueue(LinkQueue *Q,QElemType *e)//实际上删除的    队头元素是头结点的下一个！！！ 
{
QueuePtr p;
if(Q->front==Q->rear)
    return ERROR;
p=Q->front->next;        /* 将欲删除的队头结点暂存给p，见图中① */
*e=p->data;                /* 将欲删除的队头结点的值赋值给e */
Q->front->next=p->next;/* 将原队头结点的后继p->next赋值给头结点后继，见图中② */
//上面的语句相当于指针跳过去了 
if(Q->rear==p)        /* 若队头就是队尾，则删除后将rear指向头结点，见图中③ */
    Q->rear=Q->front;
free(p);
return OK;
}

/* 从队头到队尾依次对队列Q中每个元素输出 */
Status QueueTraverse(LinkQueue Q)
{
QueuePtr p;
p=Q.front->next;
while(p)
{
     visit(p->data);
     p=p->next;
}
printf("\n");
return OK;
}

int main()
{
int i;
QElemType d;
LinkQueue q;
i=InitQueue(&q);
if(i)
    printf("成功地构造了一个空队列!\n");
printf("是否空队列？%d(1:空 0:否)  ",QueueEmpty(q));
printf("队列的长度为%d\n",QueueLength(q));
EnQueue(&q,-5);
EnQueue(&q,5);
EnQueue(&q,10);
printf("插入3个元素(-5,5,10)后,队列的长度为%d\n",QueueLength(q));
printf("是否空队列？%d(1:空 0:否)  ",QueueEmpty(q));
printf("队列的元素依次为：");
QueueTraverse(q);
i=GetHead(q,&d);
if(i==OK)
 printf("队头元素是：%d\n",d);
DeQueue(&q,&d);
printf("删除了队头元素%d\n",d);
i=GetHead(q,&d);
if(i==OK)
    printf("新的队头元素是：%d\n",d);
ClearQueue(&q);
printf("清空队列后,q.front=%u q.rear=%u q.front->next=%u\n",q.front,q.rear,q.front->next);
DestroyQueue(&q);
printf("销毁队列后,q.front=%u q.rear=%u\n",q.front, q.rear);

return 0;
}