【数据结构】——队列

---

前言

本文章讲述的是数据结构的特殊线性表——队列

---

一.什么是队列，队列的特点

队列是数据结构中的一种特殊的线性表，它与栈不同，

队列的基本图例如上图：
显然，队列的特点就是:
先进先出
First In First Out
那么我们使用什么样的方式来实现队列呢？

基于队列的特点，使用链表而不是数组来实现队列是比较合适的
使用数组来实现队列的缺点：

出队时需要挪动数据，效率不高。

使用链表来实现队列的优点：入队出队效率高，不需要挪动数据。
使用链表来进行入队出队时，就需要链接起来和释放节点，所以我们最好定义头指针和尾指针指向队头和队尾。

把头指针和尾指针放在一个结构体中，更方便操作，如下图：

二、队列相关操作

队列的相关操作声明

void QueueInit(Queue* pq);//初始化队列void QueueDestroy(Queue* pq);//销毁队列void QueuePush(Queue* pq,QDataType x);//插入数据void QueuePop(Queue* pq);//删除数据int QueueSize(Queue* pq);//记录队列有多少人bool QueueEmpty(Queue* pq);//判断队列是否为NULLQDataType QueueFront(Queue* pq);//取出队头数据QDataType QueueBack(Queue* pq);//取出队尾数据

队列的创建

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int QDataType;
//队列更适合用链表写,因为如果用顺序表来写，出列的时候需要挪动数据typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QNode;
//队伍的每个人的结构体typedef struct Queue
{struct QueueNode* head;struct QueueNode* tail;
}Queue;
指向队头和队尾的两个指针放在一个结构体里面

1.队列的初始化

void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;
}

初始化指向队头和队尾的两个指针为NULL

2.对队列进行销毁

void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;
}

3.判断队列是否为空队列

bool QueueEmpty(Queue* pq)
{assert(pq);return pq->head == NULL;
}

4.入队操作

解读：队列的实现方式是链表，不需要检查容量不足，每入队一个人就申请一个节点即可

void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));assert(newnode != NULL);newnode->data = x;newnode->next = NULL;if (pq->head == NULL){pq->head = pq->tail = newnode;}//第一次入队的时候，就作为队头，头指针指向它pq->tail->next = newnode;pq->tail = newnode;}

5.出队操作

//记住队列是先进先出，所以队头先出
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//队头为空，说明删完了QNode* newhead = pq->head->next;//先记录队头的下一个人//删到最后的时候，tail没有置空，是野指针，所以这里要判断if (newhead == NULL){pq->tail = NULL;}free(pq->head);pq->head = newhead;
}

6.取出队头数据

注意出队的时候，并没有拿出该人数的节点的值

QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}

7. 取出队尾数据

QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}

8.计算队伍的人数

int QueueSize(Queue* pq)
{assert(pq);int size = 0;QNode* cur = pq->head;while (cur){++size;cur = cur->next;}return size;
}

总结

文章讲述简单队列的实现，复杂队列后续会讲。