这里写目录标题
- 一、队列的概念及结构
- 二、队列的实现(使用VS2022的C语言)
- 1.初始化、销毁
- 2.入队、出队
- 3.返回队头元素、返回队尾元素、判空、返回有效元素个数
- 三、完整 Queue.c 源代码
一、队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 的原则。
入队列：进行插入操作的一端称为队尾。
出队列：进行删除操作的一端称为队头。
第一次入队：
正常入队：
正常出队：
只剩最后一个元素时出队：
二、队列的实现(使用VS2022的C语言)
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
队列常用的接口包括：
1.初始化、销毁
2.入队、出队
3.返回队头元素、返回队尾元素、判空、返回有效元素个数
在 Queue.h 中：
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef int QDataType;
typedef struct QListNode
{
QDataType data; // 数据
struct QListNode* next; // 保存下一元素地址的指针变量
} QListNode, * pQListNode;
typedef struct Queue
{
pQListNode front; // 队头指针变量
pQListNode rear; // 队尾指针变量
int size; // 有效元素个数
} Queue, * pQueue;
// 初始化、销毁
void QueueInit(pQueue pque);
void QueueDestroy(pQueue pque);
// 入队、出队
void QueuePush(pQueue pque, QDataType x);
void QueuePop(pQueue pque);
// 返回队头元素、返回队尾元素
QDataType QueueFront(pQueue pque);
QDataType QueueBack(pQueue pque);
// 判空、返回有效元素个数
bool QueueEmpty(pQueue pque);
int QueueSize(pQueue pque);
1.初始化、销毁
// 初始化、销毁
void QueueInit(pQueue pque)
{
assert(pque);
pque->size = 0;
pque->front = pque->rear = NULL;
}
void QueueDestroy(pQueue pque)
{
assert(pque);
// 从队头开始删数据
while (pque->front)
{
pQListNode temp = pque->front->next;
free(pque->front);
pque->front = temp;
}
pque->rear = NULL;
pque->size = 0;
}
2.入队、出队
// 入队、出队
void QueuePush(pQueue pque, QDataType x)
{
assert(pque);
pQListNode newNode = (pQListNode)malloc(sizeof(QListNode));
newNode->data = x;
newNode->next = NULL;
if (pque->front == NULL) // 队列为空时，修改队头队尾
{
pque->front = newNode;
pque->rear = newNode;
}
else // 只修改队尾
{
pque->rear->next = newNode;
pque->rear = newNode;
}
++pque->size;
}
void QueuePop(pQueue pque)
{
assert(pque);
assert(pque->front && pque->rear);
pQListNode temp = pque->front->next;
free(pque->front);
pque->front = temp;
if (pque->front == NULL) // 若队头删除数据后为空
{
pque->rear = NULL;
}
}
3.返回队头元素、返回队尾元素、判空、返回有效元素个数
// 返回队头元素、返回队尾元素
QDataType QueueFront(pQueue pque)
{
assert(pque && pque->front);
return pque->front->data;
}
QDataType QueueBack(pQueue pque)
{
assert(pque && pque->rear);
return pque->rear->data;
}
// 判空、返回有效元素个数
bool QueueEmpty(pQueue pque)
{
assert(pque);
return pque->front == NULL;
}
int QueueSize(pQueue pque)
{
assert(pque);
return pque->size;
}
三、完整 Queue.c 源代码
#include "Queue.h"
// 初始化、销毁
void QueueInit(pQueue pque)
{
assert(pque);
pque->size = 0;
pque->front = pque->rear = NULL;
}
void QueueDestroy(pQueue pque)
{
assert(pque);
// 从队头开始删数据
while (pque->front)
{
pQListNode temp = pque->front->next;
free(pque->front);
pque->front = temp;
}
pque->rear = NULL;
pque->size = 0;
}
// 入队、出队
void QueuePush(pQueue pque, QDataType x)
{
assert(pque);
pQListNode newNode = (pQListNode)malloc(sizeof(QListNode));
newNode->data = x;
newNode->next = NULL;
if (pque->front == NULL) // 队列为空时，修改队头队尾
{
pque->front = newNode;
pque->rear = newNode;
}
else // 只修改队尾
{
pque->rear->next = newNode;
pque->rear = newNode;
}
++pque->size;
}
void QueuePop(pQueue pque)
{
assert(pque);
assert(pque->front && pque->rear);
pQListNode temp = pque->front->next;
free(pque->front);
pque->front = temp;
if (pque->front == NULL) // 若队头删除数据后为空
{
pque->rear = NULL;
}
}
// 返回队头元素、返回队尾元素
QDataType QueueFront(pQueue pque)
{
assert(pque && pque->front);
return pque->front->data;
}
QDataType QueueBack(pQueue pque)
{
assert(pque && pque->rear);
return pque->rear->data;
}
// 判空、返回有效元素个数
bool QueueEmpty(pQueue pque)
{
assert(pque);
return pque->front == NULL;
}
int QueueSize(pQueue pque)
{
assert(pque);
return pque->size;
}
