C语言如何实现队列(c语言,开发技术)

一. 什么是队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（head）进行删除操作，而在表的后端（tail）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

这个队列就可以理解成我们平时的排队，先进入的先出去，与我们之前实现的先进后出的栈相反。

二. 使用什么来实现栈

再把上次的图拿出来，我们看看是用线性表来实现队列，还是链表比较好

不同点顺序表链表存储空间上物理上一定连续逻辑上连续，但物理上不一定连续随机访问可以直接访问任何元素必须从头节点开始往后寻找任意位置插入或删除元素要搬移其他的元素，效率低。只需要修改节点的指针指向，效率高插入动态顺序表，当空间不够时需要扩容无容量概念，需要就申请，不用就释放应用场景元素高效存储，并且需要频繁访问需要在任意位置插入或者删除频繁

综合上表来看，我觉得链表较为方便，原因如下：

1.队列有多少元素不确定，链表可以做到需要就申请，不用就释放，较为方便

2.队列是先进先出，顺序固定，不需要随机访问。

三. 队列的实现

3.1头文件

1.包含的标准库

#include<stdio.h>#include<stdlib.h>#include<stdbool.h>#include<assert.h>

2.定义结构体

typedefintQDateType;//队列存储数据类型typedefstructQueueNode//队列元素节点{ QDateTypeval; structQueueNode*next;}QueueNode;typedef structQueue//队列{ QueueNode*head; QueueNode*tail;}Queue;

3.函数声明

voidQueueInti(Queue*pq);//队列初始化voidQueueDestory(Queue*pq);//队列的销毁voidQueuePush(Queue*pq,QDateTypex);//入队voidQueuePop(Queue*pq);//出队QDateTypeQueueFront(Queue*pq);//取出队首元素intQueueSize(Queue*pq);//求队列的长度boolQueueEmpty(Queue*pq);//判断队是否为空

3.2 函数的实现

1.队列的初始化

将头尾置为空指针即可。

voidQueueInti(Queue*pq){assert(pq);//防止pq为空指针pq->head=pq->tail=NULL;}

2.队列的销毁

遍历队列元素，然后将每一个元素释放。

voidQueueDestory(Queue*pq){assert(pq);//防止pq为空指针QueueNode*cur=pq->head;while(cur){QueueNode*next=cur->next;free(cur);cur=next;}pq->tail=pq->head=NULL;}

3.入队

对于入队，我们首先需要去开辟一个新的节点来存储数据，然后将这个节点加入到tail后即可。此时我们就要分别考虑。

1.如果为空队列，那么我们不仅要改变tail，还要改变head的值

2.如果不为空队列，只用改变tail即可。

voidQueuePush(Queue*pq,QDateTypex){ assert(pq);//防止pq为空指针 QueueNode*newNode=(QueueNode*)malloc(sizeof(QueueNode)); if(NULL==newNode) { printf("mallocerror\n"); exit(-1); } newNode->val=x; newNode->next=NULL;//开辟一个新节点存储数据 if(pq->tail==NULL)//判断是否为空队列 { assert(pq->head==NULL); pq->head=pq->tail=newNode; } else { pq->tail->next=newNode; pq->tail=newNode; }}

4.出队

对于出队，我们同样需要考虑两种情况

• 队列为空，改变head的同时改变tail

• 队列不为空，改变head即可。

voidQueuePop(Queue*pq){assert(pq);//防止pq为空指针assert(pq->head&&pq->tail);//防止队列为空队列if(pq->head->next==NULL){free(pq->head);pq->head=pq->tail=NULL;}else{QueueNode*next=pq->head->next;free(pq->head);pq->head=next;}}

5. 取出队首元素

没啥说的，直接访问头节点取出即可

QDateTypeQueueFront(Queue*pq){assert(pq);//防止pq为空指针assert(pq->head&&pq->tail);//防止队列为空队列returnpq->head->val;}

6.判断是否为空队列

我们只需要判断头指针是否为NULL，如果是则为空

boolQueueEmpty(Queue*pq){assert(pq);returnpq->head==NULL;}

7. 求队伍长度

创建一个变量，遍历队伍求长度。

intQueueSize(Queue*pq){assert(pq);QueueNode*cur=pq->head;intcount=0;while(cur){cur=cur->next;count++;}returncount;}

四.完整代码

#include<stdio.h>#include<stdlib.h>#include<stdbool.h>#include<assert.h>typedefintQDateType;typedefstructQueueNode{ QDateTypeval; structQueueNode*next;}QueueNode;typedef structQueue{ QueueNode*head; QueueNode*tail;}Queue;voidQueueInti(Queue*pq){ assert(pq); pq->head=pq->tail=NULL;}voidQueueDestory(Queue*pq){ assert(pq); QueueNode*cur=pq->head; while(cur) { QueueNode*next=cur->next; free(cur); cur=next; } pq->tail=pq->head=NULL;}voidQueuePush(Queue*pq,QDateTypex){ assert(pq); QueueNode*newNode=(QueueNode*)malloc(sizeof(QueueNode)); if(NULL==newNode) { printf("mallocerror\n"); exit(-1); } newNode->val=x; newNode->next=NULL; if(pq->tail==NULL) { assert(pq->head==NULL); pq->head=pq->tail=newNode; } else { pq->tail->next=newNode; pq->tail=newNode; }}voidQueuePop(Queue*pq){ assert(pq); assert(pq->head&&pq->tail); if(pq->head->next==NULL) { free(pq->head); pq->head=pq->tail=NULL; } else { QueueNode*next=pq->head->next; free(pq->head); pq->head=next; }}boolQueueEmpty(Queue*pq){ assert(pq); returnpq->head==NULL;}QDateTypeQueueFront(Queue*pq){ assert(pq); assert(pq->head); returnpq->head->val;}intQueueSize(Queue*pq){ assert(pq); QueueNode*cur=pq->head; intcount=0; while(cur) { cur=cur->next; count++; } returncount;}

 </div> <div class="zixun-tj-product adv-bottom"></div> </div> </div> <div class="prve-next-news">