目录一.队列的创建二.队列的初始化三.入队四.判空五.出队六.求队列的长度七.取队头元素八.取队尾元素九.销毁一.队列的创建相比于顺序表使用链表结构更易于理解队列和书写代码。我们知道单链表头插头删的时间复杂度都是O1尾插和尾删的时间复杂度是ON有什么方法能够降低尾插和尾删的时间复杂度吗想到链表有一个指针phead指向第一个节点类比下同样可以设置一个指针patil指向尾节点这样对于尾部的操作的时间复杂度就将为O1。所以队列的结构就是一个头节点phead一个尾节点ptail。但是队列毕竟是由链表组成所以队列节点的结构也就是链表的结构。队列的特点是先进先出后进后出。队尾入数据队头出数据。所以我们将链表的头作为队头链表的尾作为队尾。代码如下typedef int QDataType; //队列结点的结构 typedef struct QueueNode { QDataType data; struct QueueNode* next; }QueueNode; //队列的结构 typedef struct Queue { QueueNode* phead; QueueNode* ptail; //int size; //队列中有效数据个数 }Queue;二.队列的初始化在链表部分对链表的初始化是将头指针置为NULLdata置为0而到了队列这里,多一个ptail变量与phead的处理相同置为NULL。不过要对传过来的形参断言没有地址的队列就是没有创建没创建就无法初始化。代码如下//初始化 void QueueInit(Queue* pq) { assert(pq); pq-phead pq-ptail NULL; }三.入队入队的思路与单链表尾插异曲同工插入前先开辟新节点判断队列是否为空即头尾指针是否相等为空则将新结点头插进队列不为空“尾插”进队列即可。同样要进行断言操作。代码如下//入队——队尾 void QueuePush(Queue* pq, QDataType x) { assert(pq); QueueNode* newnode (QueueNode*)malloc(sizeof(QueueNode)); if (newnode NULL) { perror(malloc fail); exit(1); } newnode-data x; newnode-next NULL; //队列为空 if (pq-phead NULL) { pq-phead pq-ptail newnode; } else { //队列非空 pq-ptail-next newnode; pq-ptail pq-ptail-next; } }四.判空判空对于出队和取队头队尾操作而言很重要如果队列为空就无法出队。如果phead为空返回true否则返回false。同样进行断言操作。代码如下//队列判空 bool QueueEmpty(Queue* pq) { assert(pq); return pq-phead NULL; }五.出队判断队列是否为空队列如果是,抛出异常终止程序如果不是使用一个指针记录下当前队头的下一个结点的位置释放当前队头结点,然后更新队头指针。与单链表的尾删操作相同同样需要判断队列中是否仅剩一个结点如果只剩一个结点,释放该结点,然后将head和tail置为空。代码如下//出队——队头 void QueuePop(Queue* pq) { assert(!QueueEmpty(pq)); //只有一个节点phead和ptail都套置为空 if (pq-phead pq-ptail) { free(pq-phead); pq-phead pq-ptail NULL; } else { QueueNode* next pq-phead-next; free(pq-phead); pq-phead next; } }六.求队列的长度求队列长度的思路是创建一个新指针来储存头节点的位置遍历队列直至pcur为空每次循环size最后返回size即可。代码如下//队列有效元素个数 int QueueSize(Queue* pq) { assert(pq); //遍历链表——适用于不会频繁调用队列有效数据个数的场景 QueueNode* pcur pq-phead; int size 0; while (pcur) { size; pcur pcur-next; } return size;七.取队头元素取队头元素思路:判断队列是否为空不为空返回队头指针指向的头节点的数据域即可。代码如下//取队头数据 QDataType QueueFront(Queue* pq) { assert(!QueueEmpty(pq)); return pq-phead-data; }八.取队尾元素取队尾元素思路:判断队列是否为空不为空返回队尾指针指向的尾节点的数据域即可。代码如下//取队尾数据 QDataType QueueBack(Queue* pq) { assert(!QueueEmpty(pq)); return pq-ptail-data; }九.销毁销毁思路:从头遍历队列的元素,逐一释放链队列中的结点。释放完将队头指针和队尾指针置为NULL。代码如下//销毁队列 void QueueDestroy(Queue* pq) { assert(pq); QueueNode* pcur pq-phead; while(pcur) { QueueNode* next pcur-next; free(pcur); pcur next; } pq-phead pq-ptail NULL; }希望对大家有帮助共勉