队列的定义
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
就相当于我们现实的排队一样
队列的实现方法：
1.数组队列
2. 链表队列
双向链表
两边没有太多规定
单向链表
下面我就用单链表来演示下
队列的设计
队列的结构
typedef int QDataType; typedef struct QueueNode { QDataType val; struct QueueNode* next; }QNode; typedef struct Queue { QNode* head; QNode* tail;//尾节点和队尾 int size; } Queue;
这里有两个结构体，一个是链表节点的结构体，一个是队列的结构，这样设计可以在计算队列长度时的时间复杂度变成O(1),还要方便传参时不用频繁调用二级指针
初始化
void QueueInit(Queue* pq) { assert(pq); pq->size = 0; pq->head = NULL; pq->tail = NULL; }
插入（入队）
//插入 void QueuePush(Queue* pq, QDataType elemest) { //创建节点 QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc"); return; } newnode->next = NULL; newnode->val = elemest; if (pq->tail == NULL) { pq->head = newnode; pq->tail = newnode; } else { pq->tail->next = newnode; pq->tail = newnode; } pq->size++; }
我们这里是没有使用哨兵位，所以要判断head为空的情况下
删除（出队）
//删除 void QueuePop(Queue* pq) { assert(pq); assert(pq->head); if (pq->head == pq->tail) { free(pq->head); pq->tail = NULL; pq->head = NULL; } else { QNode* node = pq->head; pq->head = pq->head->next; free(node); } pq->size--; }
使用这种思路我们要注意head不能为空，还有就是只有一个节点的时候
一旦freel(head),tail就成了野指针了
队头
//队头 QDataType QueueFront(Queue* pq) { assert(pq); assert(pq->head); return pq->head->val; }
队尾
//队尾 QDataType QueueBack(Queue* pq) { assert(pq); assert(pq->head); return pq->tail->val; }
判断队列是否为空
//是否为空 bool QueueEmtry(Queue* pq) { assert(pq); return pq->size == 0; }
队列的长度
//长度 int QueueSize(Queue* pq) { assert(pq); return pq->size; }
释放
//释放 void QueueDestroy(Queue* pq) { assert(pq); QNode* node = pq->head; while (node) { QNode* node1 = node; node = node->next; free(node1); } pq->tail = NULL; pq->size = 0; }
总结
队列的大概简单的设计,如果想要设计数组队列可以去尝试一下
