作者：一个喜欢猫咪的的程序员
专栏：《数据结构》
喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》
目录
队列的结构和概念：
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头。
队列分为了两种结构
一种是数组，一种是链表。
数组在头删上面效率低，需要挪动数据。
链表头删容易。我们定义一个尾指针tail，我们就可以大大提高尾插的效率了。
链表分为单双，是否循环，是否带头。我们的选择：单链表
Queue.h文件
#pragma once #include<stdio.h> #include<assert.h> #include<stdbool.h> #include<stdlib.h> typedef int QDataType; typedef struct QueueNode { QDataType data; struct QueueNode* next; }QNode; typedef struct Queue { QNode* head; QNode* tail; int size; }Queue; void QInit(Queue* pq); void QDestroty(Queue* pq); void QPush(Queue* pq, QDataType x); void QPop(Queue* pq); QDataType QFront(Queue* pq); QDataType QBack(Queue* pq); bool QEmpty(Queue* pq); int QSize(Queue* pq);
Queue.c文件
#include"Queue.h" void QInit(Queue* pq) { assert(pq); pq->head = NULL; pq->tail = NULL; pq->size = 0; } void QDestroty(Queue* pq) { assert(pq); assert(!QEmpty(pq)); QNode* cur = pq->head; while (cur) { QNode* del = cur; cur = cur->next; free(del); } pq->head = pq->tail = NULL; } void QPush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); exit(-1); } newnode->data = x; newnode->next = NULL; if (pq->tail==NULL) { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } pq->size++; } void QPop(Queue* pq) { assert(pq); assert(!QEmpty(pq)); if (pq->head->next == NULL) { free(pq->head); pq->head = NULL; pq->tail = NULL; } else { QNode* del = pq->head; pq->head = pq->head->next; free(del); del = NULL; } pq->size--; } QDataType QFront(Queue* pq) { assert(pq); assert(!QEmpty(pq)); return pq->head->data; } QDataType QBack(Queue* pq) { assert(pq); assert(!QEmpty(pq)); return pq->tail->data; } bool QEmpty(Queue* pq) { assert(pq); if (pq->head == NULL && pq->tail == NULL) return true; else return false; } int QSize(Queue* pq) { assert(pq); return pq->size; }
这里跟链表的设计差不多，我提几个要注意的点：
- 这里需要assert是因为pq要调用head和tail，理论上一定不为空，pq是指向一个结构体，结构体不为空。
- 这里的循环条件是不等于NULL而不是不等于尾，尾是一个结构体。
- 当头删的时候，可能会照成一种隐藏的bug，当只剩下一个数据的时候，删掉后，head为NULL，tail为野指针，会造成尾插代码的bug。
Test.c文件：
#include"Queue.h" void test1() { Queue pq; QInit(&pq); QPush(&pq, 1); QPush(&pq, 2); QDataType x = QFront(&pq); QDataType y = QBack(&pq); printf("%d %d", x, y); QDestroty(&pq); } int main() { test1(); return 0; }
当我们要改变一个指针的地址的时候有三种方法：
利用二级指针改变一级指针
利用返回值
利用结构体，将指针放在结构体内，传结构体。
