1. 前言
1.1 定义
队列：一种先进先出(first in first out,缩写 FIFO)的线性表。
队尾：允许插入的一端（rear）
队头：允许删除的一端 (front）
用链表标识的队列简称 链队列
1.2 队列示意图
2. 链队列存储结构和函数说明
2.1 队列结点
typedef struct QNode{QElemType data;struct QNode * next;
}QNode; //定义队列的结点
2.2 队列类型
typedef struct{QNode * front; //队头指针 QNode * rear; //队尾指针int length;
}LinkQueue;
基本操作原型:
Status InitQueue(LinkQueue * queue); /*初始化队列,申请一个头结点的内存*/
void DestroyQueue(LinkQueue *queue); /*销毁队列*/
Status ClearQueue(LinkQueue * queue); //将队列queue清空
Status QueueEmpty(LinkQueue queue); //判断队列是否为空
Status GetHead(LinkQueue queue ,QElemType * e); //获取队列第一个元素
int QueueLength(LinkQueue queue); //返回队列长度
Status EnQueue(LinkQueue * queue, QElemType e); //元素e 插入队列queue
Status DeQueue(LinkQueue * queue ,QElemType * e); //若队列queue不空，则删除Q的队头元素，用e返回其值，并返回 OK；否则返回ERROR
Status QueueTraverse(LinkQueue queue,void (*visit)())//遍历队列，对队列的每个元素调用Visit函数
3. 完整代码
#include <stdio.h>
#include <stdlib.h>#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define MAXSIZE 30typedef int Status;typedef int QElemType; //定义元素类型为整型typedef struct QNode{QElemType data;struct QNode * next;
}QNode; //定义队列的结点typedef struct{QNode * front; //队头指针 QNode * rear; //队尾指针int length;
}LinkQueue; //定义一个队列类型 Status InitQueue(LinkQueue * queue); /*初始化队列,申请一个头结点的内存*/
void DestroyQueue(LinkQueue *queue); /*销毁队列*/
Status ClearQueue(LinkQueue * queue); //将队列queue清空
Status QueueEmpty(LinkQueue queue); //判断队列是否为空
Status GetHead(LinkQueue queue ,QElemType * e); //获取队列第一个元素
int QueueLength(LinkQueue queue); //返回队列长度
Status EnQueue(LinkQueue * queue, QElemType e); //元素e 插入队列queue
Status DeQueue(LinkQueue * queue ,QElemType * e); //若队列queue不空，则删除Q的队头元素，用e返回其值，并返回 OK；否则返回ERROR
Status QueueTraverse(LinkQueue queue,void (*visit)());//遍历队列，对队列的每个元素调用Visit函数/*初始化队列,申请一个头结点的内存*/
Status InitQueue(LinkQueue * queue)
{queue->front = (QNode*) malloc(sizeof(QNode)); //申请一个队列结点作为头结点的内存地址给 队头指针；if(queue->front == NULL)return FALSE;queue->front->next = NULL; queue->rear=queue->front;queue->length=0;return TRUE;
}/*销毁队列*/
void DestroyQueue(LinkQueue *queue)
{ClearQueue(queue);free(queue->front);queue->front = queue->rear=NULL;queue->length=0;
}//将队列queue清空
Status ClearQueue(LinkQueue * queue)
{QNode * curNode;while((curNode = queue->front->next) == NULL){queue->front->next=curNode->next; free(curNode);}queue->rear = queue->front;queue->length = 0;return OK;
}//判断队列是否为空
Status QueueEmpty(LinkQueue queue)
{return queue.front == queue.rear? TRUE:FALSE;
}//获取队列第一个元素
Status GetHead(LinkQueue queue ,QElemType * e)
{if(queue.length == 0)return FALSE;*e=queue.front->next->data;return TRUE;
}//返回队列长度
int QueueLength(LinkQueue queue)
{return queue.length;
}//元素e 插入队列queue
Status EnQueue(LinkQueue * queue, QElemType e)
{QNode * curNode=(QNode*) malloc(sizeof(QNode));if(!curNode)return FALSE;curNode->data=e;curNode->next=NULL;queue->rear->next = curNode;queue->rear =curNode;queue->length++;return TRUE;
}//若队列queue不空，则删除Q的队头元素，用e返回其值，并返回 OK；否则返回ERROR
Status DeQueue(LinkQueue * queue ,QElemType * e)
{QNode * curNode;if(queue->length == 0)return FALSE;curNode = queue->front->next;*e=curNode->data;queue->front->next=curNode->next;free(curNode);queue->length--;return TRUE;
}
void Visit(QElemType e)
{printf("%3d",e);
}
//遍历队列，对队列的每个元素调用Visit函数
Status QueueTraverse(LinkQueue queue,void (*visit)())
{QNode * curNode=queue.front->next;while(curNode){visit(curNode->data);curNode=curNode->next;}
}int main()
{QElemType e;LinkQueue queue;InitQueue(&queue);printf("队头分别插入数字3、4、5后:");EnQueue(&queue,3);EnQueue(&queue,4);EnQueue(&queue,5);QueueTraverse(queue,Visit);printf("\n删除队头数字后:");DeQueue(&queue,&e);QueueTraverse(queue,Visit); printf("\n清空队列");ClearQueue(&queue);printf("\n队列长度:%d\n",QueueLength(queue));DestroyQueue(&queue);getchar();return 0;
}4. 运行结果
