定义
前面学习了栈这种数据结构，我们知道他的特点是数据先进后出。与栈相反，队列的特点时数据先进先出。即first in firsr out,简称FIFO。
队列只允许在表的一端进行数据的插入，在另一端进行数据的删除。这和生活中的排队是一致的，最早进入队列的最先离开。在链表中，允许插入数据的一端叫队尾（rear），允许删除数据的一端叫队头（front）。假设将数据a,b,c,d,e,f输入到一个队列中，那么输入的顺序是a,b,c,d,e,f。输出的顺序也是a,b,c,d,e,f。
基本操作
- 初始化一个队列
Status InitQueue(LinkQueue *q)
- 销毁一个队列
Status DestoryQueue(LinkQueue *q)
- 清空一个队列
Status ClearQueue(LinkQueue *q)
- 判断队列是否为空
Status QueueEmpty(LinkQueue *q)
- 返回队列中可用元素的数量，即队列的长度
int QueueLength(LinkQueue *q)
- 返回队头
Status GetHead(LinkQueue Q, QElemType* e)
- 从队尾添加元素
tatus EnQueue(LinkQueue* Q, QElemType e)
- 将队头元素删除
Status DeQueue(LinkQueue* Q, QElemType* e)
- 队列的遍历
Status QueueTraverse(LinkQueue Q, void (Visit)(QElemType))
基本操作方法的代码实现
- 初始化一个队列
Status InitQueue(LinkQueue* Q) {
if(Q == NULL) {
return ERROR;
}
(*Q).front = (*Q).rear = (QueuePtr) malloc(sizeof(QNode));
if(!(*Q).front) {
exit(OVERFLOW);
}
(*Q).front->next = NULL;
return OK;
}
- 销毁一个队列
Status DestroyQueue(LinkQueue* Q) {
if(Q == NULL) {
return ERROR;
}
while((*Q).front) {
(*Q).rear = (*Q).front->next;
free((*Q).front);
(*Q).front = (*Q).rear;
}
return OK;
}
- 清空一个队列
Status ClearQueue(LinkQueue* Q) {
if(Q == NULL) {
return ERROR;
}
(*Q).rear = (*Q).front->next;
while((*Q).rear) {
(*Q).front->next = (*Q).rear->next;
free((*Q).rear);
(*Q).rear = (*Q).front->next;
}
(*Q).rear = (*Q).front;
return OK;
}
- 判断队列是否为空
Status QueueEmpty(LinkQueue Q) {
if(Q.front == Q.rear) {
return TRUE;
} else {
return FALSE;
}
}
- 返回队列中可用元素的数量，即队列的长度
int QueueLength(LinkQueue Q) {
int count = 0;
QueuePtr p = Q.front;
while(p != Q.rear) {
count++;
p = p->next;
}
return count;
}
- 返回队头
Status GetHead(LinkQueue Q, QElemType* e) {
QueuePtr p;
if(Q.front == NULL || Q.front == Q.rear) {
return ERROR;
}
p = Q.front->next;
*e = p->data;
return OK;
}
- 从队尾添加元素
Status EnQueue(LinkQueue* Q, QElemType e) {
QueuePtr p;
if(Q == NULL || (*Q).front == NULL) {
return ERROR;
}
p = (QueuePtr) malloc(sizeof(QNode));
if(!p) {
exit(OVERFLOW);
}
p->data = e;
p->next = NULL;
(*Q).rear->next = p;
(*Q).rear = p;
return OK;
}
图片演示
- 将队头元素删除
Status DeQueue(LinkQueue* Q, QElemType* e) {
QueuePtr p;
if(Q == NULL || (*Q).front == NULL || (*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;
}
图片演示
- 队列的遍历
Status QueueTraverse(LinkQueue Q, void (Visit)(QElemType)) {
QueuePtr p;
if(Q.front == NULL) {
return ERROR;
}
p = Q.front->next;
while(p != NULL) {
Visit(p->data);
p = p->next;
}
printf("\n");
return OK;
}
该源码实现的是链队列，所以设置了一个并不包含数据的头节点，实际上不设置此节点也能进行队列的操作，只不过添加头节点使得删除遍历灯过程更加的方便易懂
所有代码文件
- 状态码宏定义头文件
Status.h
#ifndef STATUS_H
#define STATUS_H
#include <stdio.h>
/* 状态码 */
#define TRUE 1 // 真/是
#define FALSE 0 // 假/否
#define OK 1 // 通过/成功
#define ERROR 0 // 错误/失败
//系统中已有此状态码定义，要防止冲突
#ifndef OVERFLOW
#define OVERFLOW -2 //堆栈上溢
#endif
//系统中已有此状态码定义，要防止冲突
#ifndef NULL
#define NULL ((void*)0)
#endif
/* 状态码类型 */
typedef int Status;
/* 布尔类型 */
typedef int Boolean;
#endif
- 函数定义头文件
LinkQueue.h
#include <stdio.h>
#include <stdlib.h>
#include "Status.h"
/* 链队元素类型定义 */
typedef int QElemType;
// 队列元素结构
typedef struct QNode {
QElemType data;
struct QNode* next;
} QNode, * QueuePtr;
// 队列结构
typedef struct {
QueuePtr front; // 队头指针
QueuePtr rear; // 队尾指针
} LinkQueue; // 队列的链式存储表示
/*
* 初始化
* 构造一个空的链队。
* 初始化成功则返回OK，否则返回ERROR。
*/
Status InitQueue(LinkQueue* Q);
/*
* 销毁(结构)
* 释放链队所占内存。
*/
Status DestroyQueue(LinkQueue* Q);
/*
* 置空(内容)
* 这里需要释放链队中非头结点处的空间。
*/
Status ClearQueue(LinkQueue* Q);
/*
* 判空
* 判断链队中是否包含有效数据
* 返回值：
* TRUE : 链队为空
* FALSE: 链队不为空
*/
Status QueueEmpty(LinkQueue Q);
/*
* 计数
* 返回链队包含的有效元素的数量。
*/
int QueueLength(LinkQueue Q);
/*
* 取值
* 获取队头元素，将其存储到e中。
* 如果可以找到，返回OK，否则，返回ERROR。
*/
Status GetHead(LinkQueue Q, QElemType* e);
/*
* 入队
* 将元素e添加到队列尾部。
*/
Status EnQueue(LinkQueue* Q, QElemType e);
/*
* 出队
* 移除队列头部的元素，将其存储到e中。
*/
Status DeQueue(LinkQueue* Q, QElemType* e);
/*
* 遍历
* 用visit函数访问队列Q
*/
Status QueueTraverse(LinkQueue Q, void(Visit)(QElemType));
#endif
- 函数实现头文件
LinkQueue.c
#include"LinkQuquq.h"
#include"Status.h"
Status InitQueue(LinkQueue* q)
{
if (q == NULL)
{
return ERROR;
}
(*q).front = (*q).rear = (QueuePtr)malloc(sizeof(QNode));
if (!(*q).front)
{
exit(OVERFLOW);
}
(*q).front->next = NULL;
return OK;
}
//队列的销毁的函数并不是经常的用到
Status DestoryQueue(LinkQueue* q)
{
if (q == NULL)
{
return ERROR;
}
while ((*q).front)
{
(*q).rear = (*q).front->next;
free((*q).front);
(*q).front = (*q).rear;
}
return OK;
}
//内容置空，但是要将中间非头结点的空间释放
Status ClearQueue(LinkQueue* q)
{
if (q = NULL)
{
return ERROR;
}
(*q).rear = (*q).front->next;
while ((*q).rear) {
(*q).front->next = (*q).rear->next;
free((*q).rear);
(*q).rear = (*q).front->next;
}
(*q).rear = (*q).front;
return OK;
}
//判断队列是否为空
Status QueueEmpty(LinkQueue* q)
{
if (q->front == q->rear)
{
return TRUE;
}
else
{
return FALSE;
}
}
//返回队列中有效元素的个数
int QueueLength(LinkQueue* q)
{
int count = 0;
QueuePtr p = q->front;
while (p != q->rear)
{
count++;
p = p->next;
}
return count;
}
//取出队头元素
Status GetHead(LinkQueue* q,int* e)
{
QueuePtr p;
if (q->front == NULL || q->front == q->rear)
{
return ERROR;
}
p = q->front->next;
*e = p->data;
return OK;
}
Status Enter(LinkQueue* q, int e)
{
QueuePtr p;
if (q == NULL || (*q).front == NULL)
{
return ERROR;
}
p = (QueuePtr)malloc(sizeof(QNode));
if (!p)
{
exit(OVERFLOW);
}
p->data = e;
p->next = NULL;
(*q).rear->next = p;
(*q).rear = p;
return OK;
}
//出队列，移除队头的元素
Status Out(LinkQueue* q, int e)
{
QueuePtr p;
if (q == NULL || q->front==NULL || q->front == q->rear)
{
return ERROR;
}
p = (*q).front->next;
e = p->data;
(*q).front->next = p->next;
if ((*q).rear == p)
{
(*q).front = (*q).rear;
}
free(p);
return OK;
}
void QueueTraverse(LinkQueue* q)
{
QueuePtr p;
if (q->front == NULL)
{
return ERROR;
}
p = q->front->next;
while (p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
- 测试主函数
LinkQueue-main.c
#include <stdio.h>
#include "LinkQueue.h" //**03 栈和队列**//
// 测试函数，打印整型
void PrintElem(QElemType e);
int main(int argc, char** argv) {
LinkQueue Q;
int i;
QElemType e;
printf(" 函数 InitQueue \n");
{
printf(" 初始化链队 Q ...\n");
InitQueue(&Q);
}
printf(" 函数 QueueEmpty \n");
{
QueueEmpty(Q) ? printf(" Q 为空！！\n") : printf(" Q 不为空！\n");
}
printf(" 函数 EnQueue \n");
{
for(i = 1; i <= 6; i++) {
EnQueue(&Q, 2 * i);
printf(" 元素 \"%2d\" 入队...\n", 2 * i);
}
}
printf(" 函数 QueueTraverse \n");
{
printf(" Q 中的元素为：Q = ");
QueueTraverse(Q, PrintElem);
}
printf(" 函数 QueueLength \n");
{
i = QueueLength(Q);
printf(" Q 的长度为 %d \n", i);
}
printf(" 函数 DeQueue \n");
{
DeQueue(&Q, &e);
printf(" 队头元素 \"%d\" 出队...\n", e);
printf(" Q 中的元素为：Q = ");
QueueTraverse(Q, PrintElem);
}
printf(" 函数 GetHead \n");
{
GetHead(Q, &e);
printf(" 队头元素的值为 \"%d\" \n", e);
}
printf(" 函数 ClearQueue \n");
{
printf(" 清空 Q 前：");
QueueEmpty(Q) ? printf(" Q 为空！！\n") : printf(" Q 不为空！\n");
ClearQueue(&Q);
printf(" 清空 Q 后：");
QueueEmpty(Q) ? printf(" Q 为空！！\n") : printf(" Q 不为空！\n");
}
printf(" 函数 DestroyQueue \n");
{
printf(" 销毁 Q 前：");
Q.front != NULL && Q.rear != NULL ? printf(" Q 存在！\n") : printf(" Q 不存在！！\n");
DestroyQueue(&Q);
printf(" 销毁 Q 后：");
Q.front != NULL && Q.rear != NULL ? printf(" Q 存在！\n") : printf(" Q 不存在！！\n");
}
return 0;
}
// 测试函数，打印整型
void PrintElem(QElemType e) {
printf("%d ", e);
}