1. 队列概念和特点
只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的特点
2. 队列结构
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低，链表中删除头数据直接free，改变头指针指向即可，但是数组就要依次向前移动数据覆盖
typedef int QueueDataType; typedef struct QueueNode { int data; struct QueueNode* next; }QueueNode; typedef struct QueueLinkList { QueueNode* head; //队头 QueueNode* tail; //队尾 int size; //元素总数 }QLL;
为什么这里需要队头和队尾指针呢？
原因：队列有队尾和队头两端，我们会查看队尾数据和队头数据，所以这里就有两个指针用来指向队头和队尾的结点
这里的嵌套结构怎么理解呢？
3. 初始化
需不需要初始化？
需要，因为size不初始化就是0，head和tail也是野指针
void QLLInit(QLL* queue) { assert(queue); queue->head = NULL; queue->tail = NULL; queue->size = 0; }
4. 数据进队
void QLLPush(QLL* queue, QueueDataType x) { assert(queue); QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); if (newnode == NULL) { perror("QLLPush:malloc is failed!\n"); exit(-1); } newnode->data = x; newnode->next = NULL; //特殊情况，头指针为NULL时，改变头指针指向 if (queue->head == NULL) { queue->head = queue->tail = newnode; } //通常情况，尾插 else { queue->tail->next = newnode; queue->tail = newnode; } queue->size++; }
为什么传结构体指针？
改变QLL结构体中的内容，所以要传结构体指针对结构体更改
5. 数据出队
void QLLPop(QLL* queue) { assert(queue != NULL); assert(QLLEmpty(queue) != true); //只有一个结点时 if (queue->head->next == NULL) { free(queue->head); queue->head = queue->tail = NULL; } else { //通常情况 QueueNode* del = queue->head; queue->head = queue->head->next; free(del); //无需置空 } queue->size--; }
为什么只有一个结点时，要对头尾指针都置空？
都需要置空，以免出现野指针，不置空该两个指针依旧指向这块空间
为什么del指针不需要置空？
del是局部变量，出了函数栈帧自动销毁
6. 拿到队头数据
QueueDataType QLLFront(QLL* queue) { assert(queue != NULL); assert(QLLEmpty(queue) != true); return queue->head->data; }
注意：队列为NULL断言，为NULL拿到不数据
7. 拿到队尾数据
QueueDataType QLLBack(QLL* queue) { assert(queue != NULL); assert(QLLEmpty(queue) != true); return queue->tail->data; }
注意：队列为NULL断言，为NULL拿到不数据
8. 判断队列是否为NULL
bool QLLEmpty(QLL* queue) { assert(queue); //return queue->size == 0; //也可以这种 return queue->head == NULL && queue->tail == NULL; }
9. 队列总数据个数
int QLLSize(QLL* queue) { assert(queue); return queue->size; }
10. 销毁队列
void QLLDestroy(QLL* queue) { assert(queue); assert(QLLEmpty(queue) != true); QueueNode* cur = queue->head; while (cur != NULL) { QueueNode* del = cur; cur = cur->next; free(del); //无需置空，原因同上 } queue->head = queue->tail = NULL; queue->size = 0; }
为什么head和tail都需置空？
原因：head和tail不置空此指针依旧指向那块空间
