C语言数据结构与算法之队列的实现详解

第C语言数据结构与算法之队列的实现详解目录队列的概念及结构队列的实现Queue.hQueue.cTest.c

队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(FirstInFirstOut)的原则

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

队列的结构在生活中非常地常见，比如排队时的抽号机就是一个典型的队列结构。那队列如何实现呢？我们一起来看一下。

队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些。因为如果使用数组的结构，出队列在数组头上出数据，需要挪动数据，时间复杂度为O(N)，效率会比较低。

Queue.h

#pragmaonce

#includestdio.h

#includestdlib.h

#includeassert.h

#includestdbool.h

typedefintQDataType;

typedefstructQueueNode

QDataTypedata;

structQueueNode*next;

}QNode;

typedefstructQueue

QNode*head;//头指针

QNode*tail;//尾指针

intsize;//节点的个数

}Queue;

voidQueueInit(Queue*pq);

voidQueueDestroy(Queue*pq);

voidQueuePush(Queue*pq,QDataTypex);

voidQueuePop(Queue*pq);

QDataTypeQueueFront(Queue*pq);

QDataTypeQueueBack(Queue*pq);

boolQueueEmpty(Queue*pq);

intQueueSize(Queue*pq);

队列要实现的函数接口有：初始化队列、销毁队列、数据入队、数据出队、返回队头的数据、返回队尾的数据、判断队列是否为空以及队列中数据的个数。这些接口实现起来也不是很难，我们一起来看一下。

Queue.c

#include"Queue.h"

voidQueueInit(Queue*pq)

assert(pq);

pq-head=pq-tail=NULL;

pq-size=0;

voidQueueDestroy(Queue*pq)

assert(pq);

QNode*cur=pq-head;

while(cur)

QNode*del=cur;

cur=cur-next;

free(del);

pq-head=pq-tail=NULL;

pq-size=0;

voidQueuePush(Queue*pq,QDataTypex)

assert(pq);

QNode*newnode=(QNode*)malloc(sizeof(QNode));

if(newnode==NULL)

perror("mallocfail");

exit(-1);

else

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++;

voidQueuePop(Queue*pq)

assert(pq);

assert(!QueueEmpty(pq));

//队列中只有一个节点

if(pq-head-next==NULL)

free(pq-head);

pq-head=pq-tail=NULL;

else

QNode*del=pq-head;

pq-head=pq-head-next;

free(del);

//del=NULL;

pq-size--;

QDataTypeQueueFront(Queue*pq)

assert(pq);

assert(!QueueEmpty(pq));

returnpq-head-data;

QDataTypeQueueBack(Queue*pq)

assert(pq);

assert(!QueueEmpty(pq));

returnpq-tail-data;

boolQueueEmpty(Queue*pq)

assert(pq);

returnpq-size==0;

//returnpq-head==NULLpq-tail==NULL;

intQueueSize(Queue*pq)

assert(pq);

returnpq-size;

初始化队列

头指针和尾指针都指向空，队列元素个数初始化为0

voidQueueInit(Queue*pq)

assert(pq);

pq-head=pq-tail=NULL;

pq-size=0;

销毁队列

利用while循环将申请的节点一一释放掉，然后头指针pq-head和尾指针pq-tail指向空，栈的数据个数置为0pq-size=0

voidQueueDestroy(Queue*pq)

assert(pq);

QNode*cur=pq-head;

while(cur)

QNode*del=cur;

cur=cur-next;

free(del);

pq-head=pq-tail=NULL;

pq-size=0;

数据入队

1.申请新的节点newnodenewnode-data=x,newnode-next=NULL

2.数据入队：当pq-tail==NULL时，队列中没有节点，那么头指针和尾指针都赋值为newnodepq-head=pq-tail=newnode；当pq-tail!=NULL时，队列中有节点，那么尾部链接上新节点newnode，然后newnode成为新的尾结点。

3.队列数据个数加一pq-size++

voidQueuePush(Queue*pq,QDataTypex)

assert(pq);

QNode*newnode=(QNode*)malloc(sizeof(QNode));

if(newnode==NULL)

perror("mallocfail");

exit(-1);

else

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.判断队列是否为空

2.数据出队：当pq-head-next==NULL时，队列中只有一个节点，释放该节点，头指针和尾指针都指向空；当pq-head-next!=NULL时，释放让头指针指向当前节点的下一个节点，释放原来的头节点

3.队列数据个数减一pq-size--

voidQueuePop(Queue*pq)

assert(pq);

assert(!QueueEmpty(pq));

//队列中只有一个节点

if(pq-head-next==NULL)

free(pq-head);

pq-head=pq-tail=NULL;

else

QNode*del=pq-head;

pq-head=pq-head-next;

free(del);

//del=NULL;

pq-size--;

返回队头数据

先判断队列是否为空，不为空时，返回队头数据。

QDataTypeQueueFront(Queue*pq)

assert(pq);

assert(!QueueEmpty(pq));

returnpq-head-data;

返回队尾数据

先判断队列是否为空，不为空时，返回队尾数据。

QDataTypeQueueFront(Queue*pq)

assert(pq);

assert(!QueueEmpty(pq));

returnpq-tail-data;

判断队列是否为空

判断队列是否为空有两种方式：1.判断pq-size等不等于0；2.判断头指针pq-head和尾指针pq-tail是否等于空指针NULL

boolQueueEmpty(Queue*pq)

assert(pq);

returnpq-size==0;

//returnpq-head==NULLpq-tail==NULL;

队列中数据的个数

直接返回队列数据的个数pq-size

intQueueSize(Queue*pq)

assert(pq);

returnpq-size;

Test.c

以下为测试函数接口的代码，大家可以参考一下。需要注意的是，打印队列中的数据是通过打印队头数据、Pop掉队头数据的方式来实现的。

#include"Queue.h"

voidQueueTest()

Queueq;

QueueInit(

QueuePush(q,1);

QueuePush(q,2);

QueuePush(q,3);

printf("%d",QueueFront(q));

QueuePop(

printf("%d",QueueFront(q));

QueuePop(

QueuePush(q,4);

QueuePu