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

【初阶数据结构】队列

news 来源：原创 2025/8/25 16:48:21

文章目录

一、概念与结构

二、队列的实现

队列的定义

1.初始化

2.入队列

3.判断队列是否为空

4.出队列

5.取队头数据

6.取队尾数据

7.队列有效个数

8.销毁队列

三.完整源码

总结

一、概念与结构

概念：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

队列底层结构选型：

从逻辑上，队列是线性的；从物理上，队列的实现是可以用数组或链表来实现。已知队列是队尾入数据，队头出数据，如果使用数组的结构，出队列在数组头上出数据,效率会比较低，时间复杂度为O(n);如果使用链表的结构实现更优一些，时间复杂度为O(1) 因此使用链表来使用队列更优。

二、队列的实现

队列的定义

因为队列是链表来实现的，在这里实现队列的定义会所有不同。定义“队列的结构”之前要把“队列的结点结构”给定义出来，把结点一个个单独定义出来；再对“队列的结构”进行定义，对队头(phead)、队尾(ptail)两个指针进行结构定义以及定义队列中有效个数(size)

//底层结构用链表
typedef int QDataType;
//定义队列结点的结构:对每个结点单独定义
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QueueNode;
//定义队列结构:要对队头，队尾两个指针进行结构定义
typedef struct Queue {QueueNode* phead;QueueNode* ptail;int size;
}Queue;

1.初始化

代码解析：

先把头结点phead、尾结点ptail 都置为NULL，再把有效个数size设为0.

//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;int size = 0;
}

2.入队列

代码解析：

因为队列底层是链表，所以在把数据入队列之前；我们先申请新结点，再判断新结点是否为空；为空就是申请失败，不为空就是申请成功；如果是队列为空，队头和队尾就是新结点；队列不为空，就在队尾插入新结点，并更新队尾(新结点变成队尾)，有效个数 size 增加。


//入队列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail\n");exit(1);}newnode->data = x;newnode->next = NULL;if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else {//pq->ptail newnodepq->ptail->next = newnode;pq->ptail = pq->ptail->next;}pq->size++;
}

3.判断队列是否为空

代码解析：

通过bool函数判断队列是否为空，如果为空就返回头结点为NULL。

//队列断定
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}

4.出队列

代码解析：

在实现出队列之前，存在两种情况，当队列只有一个结点和当队列有多个结点。先用断言来判断pq，bool函数来对队列进行判空；当队列只有一个结点时，直接头结点释放，并把头结点和尾结点置为NULL；当队列有多个结点时，先创建指针next对当前结点的下一个结点进行保存，避免出现野指针的情况(避免释放了队头指针而队尾指针变成野指针)，在对头结点进行释放，释放后让pq中的头指针重新指向保存的节点；最后对size--.

//出队列
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else {QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}

5.取队头数据

代码解析：

先断言判断pq和队列不为空，再直接返回头结点的数据

//取对头数据
QDataType QueueFornt(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;
}

6.取队尾数据

代码解析：

先断言判断pq和队列不为空，再直接返回尾结点的数据

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

7.队列有效个数

代码解析：

有两种方法来实现：

方法一：此方法在结构定义中未定义size，所以创建一个指针pcur 从头结点开始遍历，用while 循环，在pcur 不为NULL的情况，依次遍历队列，走到一个结点就对其记数，用size++，并让pcur往后走；最后返回有效元素个数size.但是方法一有不足之处，方法一的时间复杂度为O(n)，而队列底层结构是链表而时间复杂度O(1)，所以此方法了解即可。

//队列有效元素个数
int QueueSize(Queue* pq)
{//方法一：int size = 0;QueueNode* pcur = pq->phead;while (pcur){size++;pcur = pcur->next;}return size;
}

方法二：方法一在结构定义中没有定义size，而方法二在结构定义中定义了size。先断言pq和队列不为空，再直接返回有效个数size.

//队列有效元素个数
int QueueSize(Queue* pq)
{//方法二：assert(pq);assert(!QueueEmpty(pq));return pq->size;
}

8.销毁队列

代码解析：

创建两个指针，一个指针pcur 从头遍历，一个指针next 对下一个结点起保存作用，释放pcur 并让pcur走到next的位置，一直循环下去直到pcur为空；最后把头结点和尾结点置为NULL，size=0.

//销毁队列
void QueueDestory(Queue* pq)
{assert(pq);QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pq->phead->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;int size = 0;
}

三.完整源码

Queue.h

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>//底层结构用链表
typedef int QDataType;
//定义队列结点的结构:对每个结点单独定义
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QueueNode;
//定义队列结构:要对队头，队尾两个指针进行结构定义
typedef struct Queue {QueueNode* phead;QueueNode* ptail;int size;
}Queue;//初始化:把队尾和队头都置为NULL，即队列为空
void QueueInit(Queue* pq);//入队列
void QueuePush(Queue* pq, QDataType x);//队列断定
bool QueueEmpty(Queue* pq);//队列有效元素个数
int QueueSize(Queue* pq);//出队列
void QueuePop(Queue* pq);//取对头数据
QDataType QueueFornt(Queue* pq);//取队尾数据
QDataType QueueBack(Queue* pq);//销毁队列:创建两个指针，一个从头遍历，一个起对下一个结点的保存作用
void QueueDestory(Queue* pq);

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;int size = 0;
}//入队列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail\n");exit(1);}newnode->data = x;newnode->next = NULL;if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else {//pq->ptail newnodepq->ptail->next = newnode;pq->ptail = pq->ptail->next;}pq->size++;
}//队列断定
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}//队列有效元素个数
int QueueSize(Queue* pq)
{//方法一：//int size = 0;//QueueNode* pcur = pq->phead;//while (pcur)//{//	size++;//	pcur = pcur->next;//}//return size;//方法二：assert(pq);assert(!QueueEmpty(pq));return pq->size;
}//出队列
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else {QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}//取对头数据
QDataType QueueFornt(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;
}//取队尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;
}//销毁队列
void QueueDestory(Queue* pq)
{assert(pq);QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pq->phead->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;int size = 0;
}

Test.c

#define _CRT_SECURE_NO_WARNINGS 1#include"Queue.h"void test()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);//出队列//while (QueueSize(&q))//{//	printf("%d\n", QueueSize(&q));//	QueuePop(&q);//}printf("phead:%d\n", QueueFornt(&q));printf("ptail:%d\n", QueueBack(&q));QueueDestory(&q);
}int main()
{test();return 0;
}

总结

非常感谢大家阅读完这篇博客。希望这篇文章能够为您带来一些有价值的信息和启示。如果您发现有问题或者有建议，欢迎在评论区留言，我们一起交流学习。

文章目录

一、概念与结构

二、队列的实现

队列的定义

1.初始化

2.入队列

3.判断队列是否为空

4.出队列

5.取队头数据

6.取队尾数据

7.队列有效个数

8.销毁队列

三.完整源码

总结

相关文章：