二.队列
1.队列的概念及结构
- 队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
- 入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
2.队列的实现
- 队列也可以使用数组和链表的结构实现，实际上使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
- 因此在下面的讲解中，我们通过链表来实现
队列的基本结构
typedef int QDataType; typedef struct QueueNode { struct QueueNode* next; QDataType data; }QNode; typedef struct Queue { QNode* head; QNode* tail; int size; }Que;
- 在队列的实现中与之前最大的不同是我们使用了两个结构体，其中第一个保存链表的存储的元素以及地址，而第二个保存的则是队列的头和尾的指针，这样有什么意义呢？
- 在队列中，我们常常需要获取队列保存元素的多少，同时我们又需要实现队列的先进先出，也就是尾插进，头插出，这样如果我们没有一个能够指向尾部的指针，每次都需要通过遍历一下我们这个链表队列来找尾，这无疑不利于程序运行，因此我们定义第二个结构体来找尾。
队列的初始化 QueueInit
//初始化队列 void QueueInit(Que* pq) { assert(pq); pq->head = pq->tail = NULL; pq->size = 0; }
- 初始化非常简单啊，无法是指针置空，让队列元素size置0就行，不多解释啦
往队列中插入元素 QueuePush
//把结点插入队列中(尾插) void QueuePush(Que* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode));//malloc申请空间 if (newnode == NULL)//判断申请是否成功 { perror("malloc failed\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; } pq->size++;//插入元素成功，有效元素个数加1 }
- 上面这个图很形象的画出了入队和出队的情况，就不像之前详细的每一过程都用逻辑图带大家逐一分析了，大家结合这张图以及代码中的注释我相信非常好理解这个部分。
删除队列中的元素 QueuePop
// 删除队列中某个结点 void QueuePop(Que* pq) { assert(pq); assert(!QueueEmpty(pq));//判空，如果为空就不需要再删除了 //如果只有一个结点 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;//头指向删除结点的下一个结点 } pq->size--;//队列中有效元素减1 }
判断队列是否为空 QueueEmpty
//判断队列是否为空 bool QueueEmpty(Que* pq) { assert(pq); return pq->tail == NULL; }
- 这里利用返回bool的函数来判断我们的尾是否为0，为0说明此时的队列中没有元素，队列为空返回true，如果尾指针不为0说明队列不为空就返回false
获取队列中的队头元素 QueueFront
//获取队列的队头元素 QDataType QueueFront(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); QNode* cur = pq->head; return cur->data; }
- 队头元素就是头指针指向的结点，返回头指针存储的元素即可
获取队尾的元素 QueueBack
//获取队列的队尾元素 QDataType QueueBack(Que* pq) { assert(pq); assert(!QueueEmpty(pq)); return pq->tail->data; }
- 这里就体现了我们使用两个结构体的优势，我们通过尾指针就可以直接指向队尾，返回队尾的元素即可
队列的销毁 QueueDestroy
//队列的销毁 void QueueDestroy(Que* pq) { assert(pq); QNode* cur = pq->head;//保存头指针 while (cur) { QNode* next = cur->next;//保存需要销毁结点的下一个结点，防止释放掉后找不到 free(cur); cur = next; } pq->head = pq->tail = NULL;//头尾指针全置空 pq->size = 0;//有效元素置0 }
- 我们通过遍历队列链表中每一个结点来销毁我们的队列，当head为空时，说明我们链表中的结点已经全部被销毁，队列的销毁完成
计算队列元素的数量
//计算队列的元素的数量 int QueueSize(Que* pq) { return pq->size; }
- 我们每次进行入队或者出队时，都会让有效元素size+1或者-1，因此此时需要获取队列元素的数量时，返回size即可。
总结
- 今天的内容到这里就结束了，栈与队列的最大区别在于栈是后进先出，而队列是先进先出，两者在实现中实际都并没有那么难，如果你想学好这部分内容的话，不妨自己照着上面的内容试试吧！
- 好了，如果你有任何疑问欢迎在评论区或者私信我提出，大家下次再见啦！
