一、什么是队列，什么是FIFO
队列允许在一端进行插入操作，在另一端进行删除操作的线性表，队列是与栈相对的一个数据结构，栈的特点是先进后出，而队列的特点是先进先出，进行插入操作的一端叫队尾，进行删除的一端叫队头。
正如队列的名字一样，我们假设有一个队列（正在排队的一列队伍），一群人，人们依次进入队列进行排队。
插入模拟图
显然先排队的必然先出来，依次取出，和放入的顺序一样，这就是队列（FIFO）。
删除模拟图
从程序化的角度来讲，应该有两个标记，一个标记着队头，一个标记着队尾，队头用来删除数据，队尾则用来插入数据。
二、使用C模拟实现以及解析队列
队列有两种实现方式，一种是使用数组来实现，另一种是使用链表来实现，由于队列需要对头部进行插入操作，使用数组效率方面会大打折扣，所以选择使用链表来实现队列是较优的选择。
1.结构体的定义
使用链表实现队列首先我们需要定义一个链表，其次由于需要在链表的头和尾进行插入以及删除操作，所有要定义两个指针分别记录下头和尾，再加入一个size来记录链表的大小。
typedef int QDataType; typedef struct QListNode { struct QlistNode* next; QDataType data; }QNode; typedef struct Queue { QNode* front; QNode* tail; int size; }Queue;
2.队列的创建及销毁
由于函数内有对参数指针的引用，加上assert预防程序崩溃，易于调试，摧毁的时候需要每个结点每个结点的进行销毁，因为链表的空间都是从堆中申请出来的，不进行释放会造成内存泄漏，全部释放之后再将指针制空。
void QueueInit(Queue* q) { assert(q); q->front = NULL; q->tail = NULL; q->size = 0; } void QueueDestroy(Queue* q) { assert(q); QNode* cur = q->front; while (cur) { QNode* next = cur->next; free(cur); cur = next; } q->front = NULL; q->tail = NULL; q->size = 0; }
3.实现插入操作
每次插入需要申请一块新节点，如果链表为空第一次进行插入（及链表为空），需要将头和尾全部指向新节点，如果不是第一次插入（不为空），则将tail指向新节点。然后对size进行++。
bool QueueEmpty(Queue* q) { return q->front == NULL; } void QueuePush(Queue* q, QDataType data) { assert(q); QNode *temp = (QNode*)malloc(sizeof(QNode)); if (temp == NULL) { perror("malloc error"); return; } QNode* Newnode = temp; Newnode->data = data; Newnode->next = NULL; if (QueueEmpty(q)) { q->front = q->tail = Newnode; } else { q->tail->next = Newnode; q->tail = q->tail->next; } q->size++; }
4.队列删除操作
如果为空，不能进行删除，如果不为空释放掉头结点，将头结点指向原来头结点的下一个，这里需要注意如果头结点下一个为空，就不能只将头结点指向下一个（空），还需要将尾结点置空。
void QueuePop(Queue* q) { assert(q); assert(!QueueEmpty(q)); QNode* next = q->front->next; free(q->front); q->front = next; if (next == NULL) q->tail == NULL; q->size--; }
5.获取栈中有效元素个数以及头元素尾元素
返回对应变量即可。
int QueueSize(Queue* q) { assert(q); return q->size; } QDataType QueueFront(Queue* q) { assert(q); assert(!QueueEmpty(q)); return q->front->data; } QDataType QueueBack(Queue* q) { assert(q); assert(!QueueEmpty(q)); return q->tail->data; }
源代码分享
//Queue.h #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <assert.h> #include <stdbool.h> #include <malloc.h> typedef int QDataType; typedef struct QListNode { struct QlistNode* next; QDataType data; }QNode; typedef struct Queue { QNode* front; QNode* tail; int size; }Queue; void QueueInit(Queue* q); void QueuePush(Queue* q, QDataType data); void QueuePop(Queue* q); QDataType QueueFront(Queue* q); QDataType QueueBack(Queue* q); int QueueSize(Queue* q); bool QueueEmpty(Queue* q); void QueueDestroy(Queue* q); //Queue.c #include "Queue.h" void QueueInit(Queue* q) { assert(q); q->front = NULL; q->tail = NULL; q->size = 0; } void QueueDestroy(Queue* q) { assert(q); QNode* cur = q->front; while (cur) { QNode* next = cur->next; free(cur); cur = next; } q->front = NULL; q->tail = NULL; q->size = 0; } bool QueueEmpty(Queue* q) { return q->front == NULL; } void QueuePush(Queue* q, QDataType data) { assert(q); QNode *temp = (QNode*)malloc(sizeof(QNode)); if (temp == NULL) { perror("malloc error"); return; } QNode* Newnode = temp; Newnode->data = data; Newnode->next = NULL; if (QueueEmpty(q)) { q->front = q->tail = Newnode; } else { q->tail->next = Newnode; q->tail = q->tail->next; } q->size++; } void QueuePop(Queue* q) { assert(q); assert(!QueueEmpty(q)); QNode* next = q->front->next; free(q->front); q->front = next; if (next == NULL) q->tail == NULL; q->size--; } int QueueSize(Queue* q) { assert(q); return q->size; } QDataType QueueFront(Queue* q) { assert(q); assert(!QueueEmpty(q)); return q->front->data; } QDataType QueueBack(Queue* q) { assert(q); assert(!QueueEmpty(q)); return q->tail->data; } //test.c #include "Queue.h" void test() { Queue pq; QueueInit(&pq); QueuePush(&pq,1); QueuePush(&pq,2); QueuePush(&pq,3); QueuePush(&pq,4); QueuePush(&pq,5); QueuePush(&pq,6); QNode* cur = pq.front; while (cur) { QNode* next = cur->next; printf("%d ", cur->data); cur = next; } printf("\n"); QueuePop(&pq); QueuePop(&pq); QueuePop(&pq); cur = pq.front; while (cur) { QNode* next = cur->next; printf("%d ", cur->data); cur = next; } printf("\n"); QueueSize(&pq); printf("%d", QueueFront(&pq)); printf("%d", QueueBack(&pq)); QueueDestroy(&pq); } int main() { test(); }
✨本文收录于数据结构理解与实现
下几期会继续带来栈与堆的练习题。如果文章对你有帮助记得点赞收藏关注。
