队列的概念及实现

目录：

一、队列的概念及结构

二、队列的实现

1.队列的结构

2.队列的初始化

3.队列的销毁

4.队列的插入

5.队列的删除

6.统计队列的数据个数

7.判断队列是否为空

8.返回队列表头数据

9.返回队列表尾数据

10.运行展示

三、代码

一、队列的概念及结构

二、队列的实现

1.队列的结构

既然底层是单链表，那我们就先创造一个结构体表示单链表

不会单链表的可以看这个链接:https://blog.csdn.net/xpcxpt/article/details/147569114?spm=1001.2014.3001.5501

那么单链表结构如下:

因为队列需要在表尾插入数据，每次找表尾，都需要遍历链表，非常麻烦，所以我们在创建一个尾指针指向表为，这里可以创建一个结构体，来同时包含表头指针phead和表尾指针ptail:

这里加了一个size变量，用来统计个数

2.队列的初始化

初始化很简单，那么就是表头指针phead和表尾指针ptail首先都是空，并且size在初始时候为0：

3.队列的销毁

销毁要相对麻烦一点，因为这是一个单链表，所以我们需要创建一个指针遍历链表，逐一销毁:

4.队列的插入

要插入节点，首先需要malloc一个新节点，随后进行判断，如果在初始情况，那么还没有节点，这个时候的phead和ptail就都指向新节点；如果链表中已经有了节点，那只需要尾插到后面，记得size要++:

5.队列的删除

删除同样要判断，如果只有一个节点，那么删完，phead和ptail就都要置为NULL，如果不为空，那么就要指定新的头结点,记得size要--：

6.统计队列的数据个数

统计个数就是统计size：

7.判断队列是否为空

size如果是0，那就是空:

8.返回队列表头数据

那就返回头指针指向的val:

9.返回队列表尾数据

那就返回尾指针指向的val:

10.运行展示

我们假设插入1,2,3,4：

运行如下:

三、代码

test.c:

#include"Queue.h"int main()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);while (!QueueEmpty(&q)){printf("%d ", QueueFront(&q));QueuePop(&q);}printf("\n");QueueDestroy(&q);return 0;
}

Queue.h:

#pragma once
#pragma once#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType val;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;void QueueInit(Queue* pq);//初始化
void QueueDestroy(Queue* pq);//销毁
void QueuePush(Queue* pq, QDataType x);//队列的插入
void QueuePop(Queue* pq);//队列的删除int QueueSize(Queue* pq);//统计队列的数据个数QDataType QueueFront(Queue* pq);//返回队列表头数据
QDataType QueueBack(Queue* pq);//返回队列表尾数据
bool QueueEmpty(Queue* pq);//判断队列是否为空

Queue.c:

#include "Queue.h"void QueueInit(Queue* pq)
{assert(pq);//判断是否为空pq->phead = NULL;//初始化指向NULLpq->ptail = NULL;//初始化指向NULLpq->size = 0;//初始的时候，值为0
}
void QueuePush(Queue* pq, QDataType x)
{QNode* newnode = (QNode*)malloc(sizeof(QNode));//创建一个新节点if (newnode == NULL)//判断是否创建成功{perror("malloc fail");return;}newnode->next = NULL;//新节点的next指针为NULLnewnode->val = x;//它的值为给的xif (pq->ptail == NULL)//判断是否为初始情况{pq->phead = pq->ptail = newnode;}else//不是初始情况，链表中已经有节点{pq->ptail->next = newnode;//直接尾插pq->ptail = newnode;//成为新的尾}pq->size++;//个数加一
}void QueuePop(Queue* pq)
{assert(pq);assert(pq->size != 0);if (pq->phead->next==NULL)//是否链表中只有一个节点{free(pq->phead);pq->phead = pq->ptail = NULL;//都为NULL}else//链表中不止一个节点{QNode* tmp = pq->phead->next;//临时变量存放新的头结点free(pq->phead);pq->phead = tmp;}pq->size--;//删除节点，size要减少1
}int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}
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->size = 0;//size也变成0
}