一、队列的概念及结构
队列是指只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。队列具有先进先出 FIFO(First In First Out) 这一点跟栈的先进后出是相反的
- 入队列:进行插入操作的一端并且称为队尾
- 出队列：进行删除操作的一端并且称为队头
队列可用通过数组或链表结构实现，一般推荐使用链表实现更优一点。如果使用数组实现在出队列时，需要挪移大量数据，效率较低
这里采用链表结构实现队列
在设计队列结构中，需要设计两个指针去控制队列各节点的情况。head(队头指针)指向实际对头元素，taill(队尾指针)，指向实际队尾元素，增加一个变量size用于统计元素个数，由于存在多种信息，可以使用结构体统一管理
二、实现队列的相关接口(Stack.h)
2.1 队列初始化
void QueueInit(Queue *pq)//所以导致了需要初始化 { assert(pq); pq->phead = NULL; pq->ptail = NULL; pq->size = 0; }
这里需要注意的是:这里不需要对于节点进行初始化，在创建节点时会完成对应的初始化工作。
2.2 队尾入队列
void QueuePush(Queue* pq, QDataType x) { assert(pq); Qnode* newnode = (Qnode*)malloc(sizeof(Qnode)); if (newnode == NULL) { perror("malloc fail!!!"); return ; } //创建为需要初始化下 newnode->next = NULL; newnode->val = x; if (pq->phead == NULL) pq->phead = pq->ptail = newnode; else { (pq->ptail)->next = newnode; pq->ptail = newnode; } pq->size++; }
这里需要注意的是:首先就是空间开辟失败，然后需要搞清楚我们申请空间是给谁使用的，这里是为节点开辟空间。而不是为Queue结构体对象开辟空间，这里节点之间连接是通过节点指针进行连接
2.3 队头出队列
void QueuePop(Queue* pq) { assert(pq && pq->phead); Qnode *del = pq->phead; pq->phead = pq->phead->next; free(del); del == NULL; if (pq->phead == NULL) { pq->ptail = NULL; } pq->size--; }
这里需要注意的是:当队列为空时，意味着头指针为空，那么尾指针也需要置成空
2.4 获得队列头部元素
QDataType QueueFront(Queue* pq) { assert(pq); assert(pq->phead); return pq->phead->val; }
2.5 获得队列尾部元素
QDataType QueueBack(Queue* pq) { assert(pq); assert(pq->phead); return pq->ptail->val; }
2.6 获取队列中有效元素个数
int QueueSize(Queue* pq) { assert(pq); return pq->size; }
2.7 检测队列是否为空
bool QueueEmpty(Queue* pq) { assert(pq); return pq->phead == NULL; }
2.8 打印队列数据
void QueuePrint(Queue* pq) { assert(pq); while (!QueueEmpty(pq)) { printf("%d->", QueueFront(pq)); QueuePop(pq); } }
这里需要注意的是:这里不能用cur，因为cur是不会动的，phead在pop的时候一直移动
2.9 队列的销毁
void QueueDestroy(Queue* pq) { assert(pq); Qnode* cur = pq->phead; while (cur)//删除的作用 { Qnode* next = cur->next; free(cur); cur = next; } pq->ptail = NULL; pq->phead = NULL; pq->size = 0; }
这里需要注意的是:这里cur不要手动置空，会跳出循环，需等待cur自动指向空。
三、循环队列
实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型 时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。(会单独一篇来讲述)
