文章目录
一、概念与结构
二、队列的实现
QueueNode.h
Queue.c
初始化
判断队列为空
队尾，入队列
队头，出队列
取队头数据
取队尾数据
取队列有效元素个数
销毁队列
test.c
一、概念与结构
- 概念：只允许在⼀端进⾏插⼊数据操作，在另⼀端进⾏删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
- ⼊队列：进⾏插⼊操作的⼀端称为队尾
- 出队列：进⾏删除操作的⼀端称为队头
在队列的底层结构的选择上有：
- 数组：若使用数组为底层结构，进行⼊队列操作的时间复杂度为 O(1) ,进行出队列操作的时间复杂度为 O(n);
- 单链表:若使用单链表为底层结构，进行⼊队列操作的时间复杂度为 O(n) ,进行出队列操作的时间复杂度为 O(1);
这么看好像两者的差别不大，但是我们在单链表结构中可以稍作改造，直接定义两个结点（头结点，尾结点）指向原链表的队头和队尾，那么在队尾入数据时就不用遍历链表，直接让尾结点->next 等于新结点，时间复杂度就变成 O(1)了。
二、队列的实现
QueueNode.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.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;
//初始化
void QueueInit(Queue* pq);
// ⼊队列，队尾
void QueuePush(Queue* pq, QDataType x);
// 出队列，队头
void QueuePop(Queue* pq);
//队列判空
bool QueueEmpty(Queue* pq);
//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);
//队列有效元素个数
int QueueSize(Queue* pq);
//销毁队列
void QueueDestroy(Queue* pq);Queue.c
初始化
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = pq->ptail = NULL;
pq->size = 0;
}判断队列为空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL && pq->ptail == NULL;
}
队尾，入队列
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
//申请新结点
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
//如果原队列为空
if (pq->phead == NULL)
{
pq->phead = pq->ptail = newnode;
}
//如果原队列不为空,进行尾插
else
{
pq->ptail->next = newnode;
pq->ptail = pq->ptail->next;
}
pq->size++; //有效数据个数加一
}队头，出队列
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
//如果队列为空，不可出队列
if (pq->phead == NULL)
{
free(pq->phead);
pq->phead = pq->ptail = NULL; //记得把尾结点也置为空，不然会成为野指针
}
else
{
QueueNode* n = pq->phead->next; //创建结点 n 为原头结点指向的下一个结点
free(pq->phead); //释放原队列头结点，也就是出队列
pq->phead = n; //结点 n 为新的队头
}
}取队头数据
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->phead->data;
}取队尾数据
QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->ptail->data;
}取队列有效元素个数
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
销毁队列
void QueueDestroy(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
QueueNode* pcur = pq->phead; //创建指针 pcur指向队列头结点遍历队列
while (pcur) //当 pcur 不为空循环
{
QueueNode* n = pcur->next; //创建指针 n 为 pcur 指向的下一个结点
free(pcur); //释放掉以遍历的队列结点
pcur = n; //此时 pcur 等于下一个结点
}
//直到队列为空
pq->phead = pq->ptail = NULL;
pq->size = 0;
}test.c
接下来可以再测试函数中测试代码中对队列的实现
#include"Queue.h"
void Queuetest()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
QueuePop(&q);
int a = QueueFront(&q);
int b = QueueBack(&q);
printf("队头数据：%d\n", a);
printf("队尾数据：%d\n", b);
int c =QueueSize(&q);
printf("有效数据个数：%d", c);
QueueDestroy(&q);
}
int main()
{
Queuetest();
return 0;
}- 初始化 ：
- 入队：
- 出队：
- 最后结果：
