1.队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先 进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一 端称为队头
注意：队列和栈的不同点
栈：只能从栈顶插入和删除，满足先进后出的原则
队列：是从队尾插入，对头删除，满足先进先出的原则
2.队列的实现
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构， 出队列在数组头上出数据，效率会比较低。
数组存储：
总结：利用数组的结构去存储队列，插入时只需要尾插时间复杂度为O(1)，删除时需要把对头后面的元素依次往前移这样时间复杂度就为O(n).
链表存储：
总结：利用单链表的结构进行队的存储，插入只需要尾插时间复杂度为O(1)，删除只需要头删时间复杂度为O(n)。可以从上图中看出队列完美避开了单链表需要找前一个结点的问题。
下面我们就来利用单链表实现队列吧！！！
①首先我们先定义两个结构体类型
typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }QNode; typedef struct Queue { QNode* head; QNode* tail; }Queue;
第一个结构体类型QueueNode是结点，第二个Queue是队头和队尾
② 初始化
//初始化 void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; }
初始化的时候，我们把队头和队尾分别指向NULL
③插入
//队尾入 void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { printf("malloc fail\n"); 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; } }
④删除
//队头出 void QueuePop(Queue* pq) { assert(pq); assert(pq->head); //一个 多个 if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { QNode* next = pq->head->next; free(pq->head); pq->head = next; } }
⑤取队头
//取队头 QDataType QueueFront(Queue* pq) { assert(pq); assert(pq->head); return pq->head->data; }
我们首先得断言一下队列里面是否有数据，如果没有就不能返回，如果有才能返回
⑥取队尾
//取队尾 QDataType QueueBact(Queue* pq) { assert(pq); assert(pq->tail); return pq->tail->data; }
⑦队中有多少个结点
//队中数据个数 int QueueSize(Queue* pq) { assert(pq); int size = 0; QNode* cur = pq->head; while (cur) { ++size; cur = cur->next; } return size; }
⑧判空
//判空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; }
利用bool型进行判空，bool型就是真和假嘛
⑨销毁
//销毁 void QueueDestory(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { QNode* next = cur; free(cur); cur = next; } pq->head = pq->tail = NULL; }
销毁的好处是：防止内存泄漏的问题.
