前言
本文章讲述的是数据结构的特殊线性表——队列
一.什么是队列，队列的特点
队列是数据结构中的一种特殊的线性表，它与栈不同，
队列的基本图例如上图：
显然，队列的特点就是:
先进先出
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);//判断队列是否为NULL QDataType 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; }
总结
文章讲述简单队列的实现，复杂队列后续会讲。
