数据结构之队列
目录
引言
队列的概念与结构
队列的实现
定义
初始化
销毁
入队
判断队列是否为空
出队
获取队头元素
获取队尾元素
检测队列中有效元素个数
元素访问
源代码
queue.h
queue.c
test.c
引言
数据结构之路经过栈后，就来到了与栈联系紧密的兄弟——队列（Queue）
队列的概念与结构
队列： 只允许在一端进行插入数据操作，在另一端进行删除数据操作 的特殊线性表，队列具有 先进先出 FIFO(First In First Out)入队列： 进行插入操作的一端称为 队尾出队列： 进行删除操作的一端称为 队头
队列的实现
队列 也可以 数组和链表的结构 实现 ，使用 链表的结构实现更优 一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
定义
队列的实现，需要定义两个结构体，一个代表节点的信息，另一个代表队列的信息，因为队列的特性要在一端入，另一端出，所以要记录头尾指针（要不然找尾效率太低了） ，而size代表当前队列元素个数（可加可不加，加上更好）
初始化
头尾指针置为NULL，size置为0
销毁
队列的销毁，本质上就是链表的销毁 ，创建cur变量，循环释放每一个节点，直到cur为空，最后再将头尾指针置为NULL，size置为0
入队
入队时 ，先生成新节点（因为这里只有入队用到生成新节点，所以不用抽离成函数），再要分空链表和非空链表进行讨论
空链表判断时，加入assert断言，防止外部操作错误，造成头指针不为空，尾指针为空
链表为空时，则头尾指针都指向新节点；链表不为空时，则正常尾插
判断队列是否为空
专门写一个函数判断，增强复用性和可读性 。如果size为0，则队列为空，返回真；反之，则不为空，返回假
出队
出队时，先判断队列是否为空（保证phead不为NULL，防止为空指针的解引用），再分单个节点和多个节点来讨论
单个节点，则释放头指针指向的节点后，头尾指针置为NULL；多个节点，则正常头删
获取队头元素
获取队尾元素
检测队列中有效元素个数
这里很多函数实现都很简单，有些操作直接外部对结构体都可以直接实现，但最后还是写成函数封装，防止别人使用时对该数据结构不够熟悉，导致使用错误
元素访问
队列中元素访问（打印），不是用函数实现。因为它的特殊结构，决定了它的元素不能从任意位置访问 ，必须符合先进先出原则才可以。所以，我们通常用循环的方式进行访问，同时每访问一个元素，就将它弹出队列，再进行下一个元素的访问。
运行结果
队列与栈有所不同，因为它先进先出的特性，导致顺序只能是1 2 3 4
这样我们就实现了队列的增删等功能
源代码
queue.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int QDataType;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);
//入队
void QueuePush(Queue* pq, QDataType x);
//出队
void QueuePop(Queue* pq);
//获取队头元素
QDataType QueueFront(Queue* pq);
//获取队尾元素
QDataType QueueBack(Queue* pq);
//检测队列中有效元素个数
int QueueSize(Queue* pq);
//检测队列是否为空
bool QueueEmpty(Queue* pq);queue.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"queue.h"void QueueInit(Queue* pq)
{assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->data = x;newnode->next = NULL;if (pq->ptail == NULL){assert(pq->phead == NULL);pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->phead->next == NULL){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}QDataType QueueFront(Queue* pq)
{assert(pq);return pq->phead->data;
}QDataType QueueBack(Queue* pq)
{assert(pq);return pq->ptail->data;
}int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"queue.h"void TestQueue1()
{Queue q;//初始化QueueInit(&q);//入队QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);//打印while (!QueueEmpty(&q)){printf("%d ", QueueFront(&q));QueuePop(&q);}//销毁QueueDestroy(&q);
}int main()
{TestQueue1();return 0;
}