目录
前言
之前我们了解到栈是一种特殊的线性表，现在我们来介绍另外一种特殊的线性表队列，队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。
一、队列
队列：只允许在 一端进行插入数据操作 ，在 另一端进行删除数据操作 的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
实际中我们有时还会使用一种队列叫循环队列。操作系统中生产者消费者模型 时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。
二、队列的实现
队列也可以数组和链表的结构实现，使用 链表 的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
主要接口：
typedef int QDataType;
//队列节点
typedef struct QueueNode {
QDataType data;
struct QueueNode* next;
}QNode;
//队列结构
typedef struct Queue {
QNode* phead;//头节点
QNode* ptail;//尾节点
int sz;
}Queue;
//初始化队列
void QueueInit(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);
//销毁队列
void QueueDestroy(Queue* pq);2.1 队列结构
由于我们用链表来实现队列，为了更好的完成队列操作，我们定义了一个结构体来表示队列的队头和队尾。
//队列结构
typedef struct Queue {
QNode* phead;//头节点
QNode* ptail;//尾节点
int sz;
}Queue;2.2 队列的初始化
void QueueInit(Queue* pq) {
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->sz = 0;
}
我们把队列的头和尾都置为空，队长置为零。
2.4 入队列
void QueuePush(Queue* pq, QDataType x) {
assert(pq);
//创建新节点
QNode* newNode = (QNode*)malloc(sizeof(QNode));
if (newNode == NULL)
{
perror("malloc fail");
}
newNode->data = x;
newNode->next = NULL;
//从队尾插入
if (pq->phead == NULL)
{
pq->phead = pq->ptail = newNode;
}
else
{
pq->ptail->next= newNode;
pq->ptail = newNode;
}
//长度加一
pq->sz++;
}我们先创建要插入的新的节点，然后从队列的队尾插入(即链表的尾插)，最后队列长度加一。
2.5 出队列
void QueuePop(Queue* pq) {
assert(pq);
assert(pq->phead != NULL);//队列不为空
if (pq->phead == pq->ptail)
{
free(pq->ptail);
pq->phead = pq->ptail = NULL;
}
else
{
QNode* next = pq->phead->next;;
free(pq->phead);
pq->phead = next;
}
pq->sz--;
}出队列从队头开始出去，但是我们这里需要分成两种情况讨论，第一种就是队列只有一个元素，我们要把头尾同时置为空，不然有野指针出现。第二种就是链表的头删操作。
2.6 获取队列尾部元素
QDataType QueueBack(Queue* pq) {
assert(pq);
assert(pq->phead != NULL);
return pq->ptail->data;
}我们先判断队列是否为空，然后直接返回尾部节点元素即可。
2.7 获取队列头部元素
QDataType QueueFront(Queue* pq) {
assert(pq);
assert(pq->phead != NULL);
return pq->phead->data;
}我们先判断队列是否为空，然后直接返回头部节点元素即可。
2.8 获取队列有效元素个数
int QueueSize(Queue* pq) {
assert(pq);
return pq->sz;
}
我们先判断队列是否为空，直接返回队列结构中的大小即可。
2.9 判断队列是否为空
bool QueueEmpty(Queue* pq) {
assert(pq);
return pq->phead == NULL;
}直接返回，如果头节点等于空，即返回true，反之返回false。
2.10 销毁队列
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->sz = 0;
}和链表销毁差不多，我们要依次销毁每一个创建的节点。
三、完整代码实现
Queue.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>
typedef int QDataType;
//队列节点
typedef struct QueueNode {
QDataType data;
struct QueueNode* next;
}QNode;
//队列结构
typedef struct Queue {
QNode* phead;//头节点
QNode* ptail;//尾节点
int sz;
}Queue;
//初始化队列
void QueueInit(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);
//销毁队列
void QueueDestroy(Queue* pq);Queue.c
#include"Queue.h"
//初始化队列
void QueueInit(Queue* pq) {
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->sz = 0;
}
//入队列(队尾)
void QueuePush(Queue* pq, QDataType x) {
assert(pq);
//创建新节点
QNode* newNode = (QNode*)malloc(sizeof(QNode));
if (newNode == NULL)
{
perror("malloc fail");
}
newNode->data = x;
newNode->next = NULL;
if (pq->phead == NULL)
{
pq->phead = pq->ptail = newNode;
}
else
{
pq->ptail->next= newNode;
pq->ptail = newNode;
}
//长度加一
pq->sz++;
}
//出队列(队头)
void QueuePop(Queue* pq) {
assert(pq);
assert(pq->phead != NULL);
if (pq->phead == pq->ptail)
{
free(pq->ptail);
pq->phead = pq->ptail = NULL;
}
else
{
QNode* next = pq->phead->next;;
free(pq->phead);
pq->phead = next;
}
pq->sz--;
}
//获取队列头部元素
QDataType QueueFront(Queue* pq) {
assert(pq);
assert(pq->phead != NULL);
return pq->phead->data;
}
//获取队列尾部元素
QDataType QueueBack(Queue* pq) {
assert(pq);
assert(pq->phead != NULL);
return pq->ptail->data;
}
//获取队列有效元素个数
int QueueSize(Queue* pq) {
assert(pq);
return pq->sz;
}
//判断队列是否为空
bool QueueEmpty(Queue* pq) {
assert(pq);
return pq->phead == NULL;
}
//销毁队列
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->sz = 0;
}test.c
#include"Queue.h"
int main() {
Queue pq;
QueueInit(&pq);
QueuePush(&pq, 1);
QueuePush(&pq, 2);
QueuePush(&pq, 3);
int data = QueueFront(&pq);
printf("%d ", data);
QueuePop(&pq);
QueuePush(&pq, 4);
QueuePush(&pq, 5);
while (!QueueEmpty(&pq)) {
int data = QueueFront(&pq);
printf("%d ", data);
QueuePop(&pq);
}
QueueDestroy(&pq);
}总结
以上我们讲了队列一种特殊的线性表，讲了队列的概念和具体实现，希望对你有所帮助。