数据结构---队列详解

一、队列的概念与结构

概念：概念：只允许在⼀端进行插入数据操作，在另⼀端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
**入队列：**进行插入操作的一端称为队尾。
出队列：进行删除操作的一端称为队头。
在这里插入图片描述
实现队列的底层结构一般使用链表，但是数组和链表的结构都可以实现，选用链表的是因为如果使用数组的结构，出队列在数组头上的数据，效率会比较低。

二、队列的常见接口

1、创建队列数据结构

//定义队列节点的结构
typedef struct QueueNode {QDataType data;struct QueueNode* next;
}QueueNode;//定义队列的数据结构
typedef struct Queue {QueueNode* phead;   //队头QueueNode* ptail;   //队尾int size;
}Queue;

这里我们要用两个结构体，首先创建一个链表的结构体，因为我们底层是用链表来实现的，第二个是创建一个队列的结构体

2、队列的初始化

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

3、队列的销毁

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

这里创建一个指向头节点的指针pcur，然后遍历队列。

4、插入数据

//插入数据
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;//如果队列为空，队头队尾都是newnodeif (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else {pq->ptail->next = newnode;pq->ptail = pq->ptail->next;}++pq->size;
}

创建一个新的结点将数据插入，判断队列是不是空，是空就把新创建的结点作为队头。

5、判断队列是否为空

//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}

6、队列中的有效数据个数

//有效元素个数
int QueueSize(Queue* pq)
{return pq->size;
}

我们会发现上述代码很简单，其实是因为我们在创建队列这个结构体的时候加了一个int->size，当插入数据的时候我们就++，删除数据的时候就–。如果前面创建队列的数据结构的时候没有加这个，我们要求队列里面的有效数据个数的代码如下：

int QueueSize(Queue* pq)
{assert(pq);int count = 0;QueueNode* pcur = pq->phead;while (pcur){count++;pcur = pcur->next;}return count;
}

是不是很复杂呀！而且时间复杂度也很大哦！

7、删除队列数据

//删除队列数据
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;
}

这里要注意的是只有一个节点的情况，其他就没什么了。

8、取队头

//取队头
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;
}

9、取队尾

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

三、队列代码总览

Queue.h

#pragma once
#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 QueueDestroy(Queue* pq);
//判断对列是否为空
bool QueueEmpty(Queue* pq);
//队列有效元素个数
int QueueSize(Queue* pq);//向队列中插入数据
void QueuePush(Queue* pq, QDataType x);
//删除队列中的数据
void QueuePop(Queue* pq);
//取队头
QDataType QueueFront(Queue* pq);
//取队尾
QDataType QueueBack(Queue* pq);

Queue.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}//销毁
void QueueDestroy(Queue* pq)
{assert(pq);QueueNode* pcur = pq->phead;while (pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}//插入数据
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;//如果队列为空，队头队尾都是newnodeif (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else {pq->ptail->next = newnode;pq->ptail = pq->ptail->next;}++pq->size;
}//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}//有效元素个数
int QueueSize(Queue* pq)
{/*assert(pq);int count = 0;QueueNode* pcur = pq->phead;while (pcur){count++;pcur = pcur->next;}return count;*/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 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;
}

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);
}int main()
{test();return 0;
}