当前位置：首页 > news >正文

队列的实现与应用详解

news 2026/3/26 22:59:16

队列（Queue）是一种遵循先进先出（FIFO, First In First Out）原则的线性数据结构，就像日常生活中排队买票的场景：先到的人先买票，后到的人排在队尾，只能等待前面的人处理完才能轮到自己。本文将从队列的结构设计、核心接口实现、功能测试等方面，详细讲解基于链表的队列实现。

一、队列的设计思路

队列的实现方式有两种：数组实现和链表实现。本文选择链表实现，原因是链表在队尾插入、队头删除操作时效率更高（无需移动元素），且不存在数组的容量限制问题。

1. 数据结构定义

队列的链表实现需要两个核心结构：

队列结点（QNode）：存储单个数据元素，并指向后继结点；
队列管理结构（Queue）：记录队列的队头（phead）和队尾（ptail）指针，方便快速访问队头 / 队尾，避免遍历链表。

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

// 队列存储的数据类型（可按需修改，如改为char、float等）
typedef int QDataType;

// 队列结点结构
typedef struct QueueNode
{
QDataType val;// 结点存储的数据
struct QueueNode* next;// 指向下一个结点的指针
} QNode;

// 队列管理结构（记录队头、队尾）

List item

typedef struct Queue
{
QNode* phead;// 队头指针
QNode* ptail;// 队尾指针
} Queue;

二、队列核心接口实现

队列的核心操作包括：初始化、入队、出队、取队头 / 队尾、判空、获取长度、销毁，所有接口的实现均基于链表操作。

1. 队列初始化（QueueInit）

初始化队列的核心是将队头和队尾指针置空，表示空队列。

#include"Queue.h"

// 初始化队列
void QueueInit(Queue* pq) {
assert(pq);// 确保传入的队列指针非空
pq->phead = pq->ptail = NULL;
}

2. 入队列（QueuePush）

入队操作是在队尾插入新结点，需处理两种情况：

队列为空：新结点既是队头也是队尾；
队列非空：将新结点链接到队尾，更新队尾指针。

// 入队列（队尾插入）
void QueuePush(Queue* pq, QDataType x) {
assert(pq);
// 1. 创建新结点
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL) { // 内存分配失败处理
perror(“malloc fail”);
exit(1);
}
newnode->val = x;
newnode->next = NULL;
// 2. 插入到队尾
if (pq->phead == NULL) {
// 空队列
pq->phead = pq->ptail = newnode;
} else {
// 非空队列
pq->ptail->next = newnode;
pq->ptail = newnode;
}
}
3. 队列判空（QueueEmpty）
判空是基础操作，后续出队、取队头 / 队尾都需要先判断队列是否为空，避免访问空指针。

// 队列判空：空返回true，非空返回false
bool QueueEmpty(Queue* pq) {
assert(pq);
return pq->phead == NULL;
}

4. 出队列（QueuePop）
出队操作是删除队头结点，需处理两种情况：

队列只有一个结点：删除后队头、队尾均置空；
队列有多个结点：更新队头指针为下一个结点，释放原队头结点。

// 出队列（队头删除）
void QueuePop(Queue* pq) {
assert(pq);
assert(!QueueEmpty(pq));// 队列非空校验

QNode* del = pq->phead;// 记录要删除的队头结点
if (pq->phead == pq->ptail) {** // 队列只有一个结点**
pq->phead = pq->ptail = NULL;
} else {// 队列有多个结点
pq->phead = pq->phead->next;
}
free(del); // 释放结点内存
del = NULL;
}

5. 取队头 / 队尾数据（QueueFront/QueueBack）

队头数据：直接返回队头结点的val；
队尾数据：直接返回队尾结点的val；
注意：操作前必须校验队列非空。
// 取队头数据
QDataType QueueFront(Queue* pq) {
assert(pq);
assert(!QueueEmpty(pq));
return pq->phead->val;
}

// 取队尾数据
QDataType QueueBack(Queue* pq) {
assert(pq);
assert(!QueueEmpty(pq));
return pq->ptail->val;
}

6. 队列销毁（QueueDestroy）
销毁队列需要遍历所有结点，逐个释放内存，最后将队头、队尾指针置空，避免内存泄漏。

// 销毁队列
void QueueDestroy(Queue* pq) {
assert(pq);
QNode* cur = pq->phead;
while (cur) {// 遍历释放所有结点
QNode* del = cur;
cur = cur->next;
free(del);
}
// 重置队头、队尾
pq->phead = pq->ptail = NULL;
}

7. 获取队列长度（QueueSize）
遍历链表，统计结点个数，即为队列的有效元素个数。

// 获取队列有效元素个数
int QueueSize(Queue* pq) {
assert(pq);
QNode* cur = pq->phead;
int size = 0;
while (cur) {
size++;
cur = cur->next;
}
return size;
}

三、常见错误修正

在初始实现代码中，存在一个典型错误：QueueBack函数错误返回了pq->phead->val（队头数据），而非pq->ptail->val（队尾数据），上述代码已修正该问题。
此外，QueuePop函数中初始代码的断言参数错误（assert(!QueueEmpty(&pq))），正确应为assert(!QueueEmpty(pq))（传入队列指针而非指针的地址）。

四、队列功能测试

编写测试代码，验证队列的核心功能是否正常：

#include"Queue.h"

void test_queue() {
Queue pq;
// 1. 初始化队列
QueueInit(&pq);

// 2. 入队：1 -> 2 -> 3 -> 4
QueuePush(&pq, 1);
QueuePush(&pq, 2);
QueuePush(&pq, 3);
QueuePush(&pq, 4);
printf(“队列长度：%d\n”, QueueSize(&pq));// 输出：4
printf(“队头元素：%d\n”, QueueFront(&pq));// 输出：1
printf(“队尾元素：%d\n”, QueueBack(&pq));// 输出：4

// 3. 出队（删除队头1）
QueuePop(&pq);
printf(“出队后队头：%d\n”, QueueFront(&pq));// 输出：2
printf(“出队后长度：%d\n”, QueueSize(&pq));// 输出：3

// 4. 循环出队，验证先进先出
while (!QueueEmpty(&pq)) {
printf(“出队元素：%d\n”, QueueFront(&pq));
QueuePop(&pq);
}
// 输出：2 -> 3 -> 4

// 5. 销毁队列
QueueDestroy(&pq);
}

int main() {
test_queue();
return 0;
}