前言：
本节博客是对基础数据结构队列的一种实现思路的分享，有需要借鉴即可。
1.队列的概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先
进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一
端称为队头
与此恰好相反的数据结构是栈的概念：详情见博客LINK
2.队列的结构
在写代码之前，我们首先要搞清楚几个问题：
1.队列依托的底层数据结构是什么？为什么？
如果用数组来做队列的话，有个问题，就是需要不停的一个一个的挪动数据。
我们接下来看一下用链表做队列的情况:
所以选择单链表。因为单链表可行且效率较高。
总结一下:用数组实现队列，无论怎么进行布局，都避免不了挪动数据的问题；用链表实现，尾插可以作为队尾（插入数据）头删可以用来出数据。
2.队列的一个整体接口是如何的？
3.为什么在队列的效率考虑我采用了一个结构体来存储指针？（这里指针意思是记录phead的内容与ptail的内容的指针）
原因：如果不用结构体来存储指针的话，那我们每个接口传入都需要传入这两个指针比较麻烦。
3.各种接口的实现
1.初始化与销毁
void QueueInit(Queue* pq) { assert(pq); pq->phead = pq->ptail = NULL; pq->size = 0; } void QueueDestroy(Queue* pq) { assert(pq); QNode* pcur = pq->phead; while (pcur) { QNode* next = pcur->next;//记录 free(pcur);//销毁 pcur = next;//更新 } pq->phead = pq->ptail = NULL; pq->size = 0; } int QueueSize(Queue* pq) { assert(pq); return pq->size; }
2.进队列与出队列
这个模块属于队列的重点，因而特地强调一下。
在进队列的情况下，有两种情况，一是没有结点的时候，需要移动phead与ptail两个指针。二是有一个或者多个结点的时候，只需要移动ptail进行尾插即可。
在出队列的情况下，有三种情况，一是没有结点的时候，不能出队列；二是有一个队列的时候，需要对ptai和phead两个指针做改动；三是有多个结点的时候，只需要修改phead进行头删即可。
void QueuePush(Queue* pq, QDataType x)//=尾插 { assert(pq); //申请一块堆空间 QNode* newnode = (QNode*)malloc(sizeof(QNode)); if(newnode == NULL) { perror("malloc fail"); exit(1); } //新节点的初始化 newnode->val = x; newnode->next = NULL; //如果是没有结点时候需要插入 if (pq->phead == NULL) { pq->phead = pq->ptail = newnode; }//至少有一个节点时需要插入（尾插） else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; } void QueuePop(Queue* pq) { assert(pq); //这里其实有三种不同的情况： //1.没有结点，这种是不可以删除的 //2.一个结点，那么就需要phead与ptail都需要调整(容易被坑) //3.多个结点，只需要调整phead即可 assert(pq->phead != NULL); if (pq->phead == pq->ptail) { free(pq->phead); pq->phead = pq->ptail = NULL; } else { QNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->size--; }
3.取头结点与取尾结点
QDataType QueueFront(Queue* pq) { assert(pq); //没有数据，不能取出 assert(pq->phead != NULL); //有数据 return pq->phead->val; } QDataType QueueBack(Queue* pq) { assert(pq); //没有数据，不能取出 assert(pq->phead != NULL); //有数据 return pq->ptail->val; } bool QueueEmpty(Queue* pq) { assert(pq); return pq->phead == NULL; }
4.全部代码一览
#include"Queue.h" void QueueInit(Queue* pq) { assert(pq); pq->phead = pq->ptail = NULL; pq->size = 0; } void QueueDestroy(Queue* pq) { assert(pq); QNode* pcur = pq->phead; while (pcur) { QNode* next = pcur->next;//记录 free(pcur);//销毁 pcur = next;//更新 } pq->phead = pq->ptail = NULL; pq->size = 0; } int QueueSize(Queue* pq) { assert(pq); return pq->size; } void QueuePush(Queue* pq, QDataType x)//=尾插 { assert(pq); //申请一块堆空间 QNode* newnode = (QNode*)malloc(sizeof(QNode)); if(newnode == NULL) { perror("malloc fail"); exit(1); } //新节点的初始化 newnode->val = x; newnode->next = NULL; //如果是没有结点时候需要插入 if (pq->phead == NULL) { pq->phead = pq->ptail = newnode; }//至少有一个节点时需要插入（尾插） else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; } void QueuePop(Queue* pq) { assert(pq); //这里其实有三种不同的情况： //1.没有结点，这种是不可以删除的 //2.一个结点，那么就需要phead与ptail都需要调整(容易被坑) //3.多个结点，只需要调整phead即可 assert(pq->phead != NULL); if (pq->phead == pq->ptail) { free(pq->phead); pq->phead = pq->ptail = NULL; } else { QNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->size--; } QDataType QueueFront(Queue* pq) { assert(pq); //没有数据，不能取出 assert(pq->phead != NULL); //有数据 return pq->phead->val; } QDataType QueueBack(Queue* pq) { assert(pq); //没有数据，不能取出 assert(pq->phead != NULL); //有数据 return pq->ptail->val; } bool QueueEmpty(Queue* pq) { assert(pq); return pq->phead == NULL; }
#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<stdbool.h> #include<stdlib.h> #include<assert.h> //队列结构-底层：单链表实现 typedef int QDataType; typedef struct QueueNode { QDataType val; struct QueueNode* next; }QNode; //两个指针的结构体 typedef struct Queue { QNode* phead; QNode* ptail; int size; }Queue; //实现的各种接口： //初始化与销毁 void QueueInit(Queue* pq); void QueueDestroy(Queue* pq); int QueueSize(Queue* pq); //插入与删除 void QueuePush(Queue* pq, QDataType x); void QueuePop(Queue* pq); //取头结点与取尾结点 QDataType QueueFront(Queue* pq); QDataType QueueBack(Queue* pq); bool QueueEmpty(Queue* pq);
#include"Queue.h" test1() { Queue q; QueueInit(&q); QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); QDataType x = QueueFront(&q); printf("%d ", x); QueuePop(&q); x = QueueFront(&q); printf("%d ", x); QueuePop(&q); QueuePush(&q, 4); QueuePush(&q, 5); QueuePush(&q, 6); //取出 while (QueueSize(&q) != 0) { x = QueueFront(&q); printf("%d ", x); QueuePop(&q); } } int main() { test1(); return 0; }
完。
