c语言链式队列与循环队列怎么实现-mile米乐体育

c语言链式队列与循环队列怎么实现

这篇文章主要介绍了c语言链式队列与循环队列怎么实现的相关知识，内容详细易懂，操作简单快捷，具有一定借鉴价值，相信大家阅读完这篇c语言链式队列与循环队列怎么实现文章都会有所收获，下面我们一起来看看吧。

队列的实现

队列是一种先进先出（first in first out）的线性表，简称fifo。与栈不同，栈是一种后进先出（先进后出）的线性表。在队列中，允许插入的一端称为队尾，允许删除的一端称为队头。假设队列是q=（a1,a2,…,an），那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，列在最后。这也比较符合我们通常生活中的习惯，排在第一个的优先出列，最后来的当然在队伍的最后。队列分为顺序队列和循环队列。顺序队列我们可以利用数组或者链表实现。这里，我们选择用链表实现顺序队列。

今天主要介绍链表实现的队列和循环队列

链式队列

队列主要有哪些基本操作

//初始化队列voidqueueinit(queue*q);//队尾入队列voidqueuepush(queue*q,qdatatypedata);//队头出队列voidqueuepop(queue*q);//获取队列头部元素qdatatypequeuefront(queue*q);//获取队列队尾元素qdatatypequeueback(queue*q);//获取队列中有效元素个数intqueuesize(queue*q);//检测队列是否为空，如果为空返回非零结果，如果非空返回0boolqueueempty(queue*q);//销毁队列voidqueuedestroy(queue*q);

链式队列的定义

typedefintqdatatype;//链式结构：表示队列typedefstructqlistnode{structqlistnode*_next;qdatatype_data;}qnode;//队列的结构typedefstructqueue{qnode*_front;qnode*_rear;}queue;

链式队列的实现

1、初始化队列

voidqueueinit(queue*q){assert(q);q->_front=null;q->_rear=null;}

2、销毁队列

voidqueuedestroy(queue*q){assert(q);qnode*cur=q->_front;while(cur!=null){qnode*next=cur->_next;free(cur);cur=next;}q->_front=q->_rear=null;}

3、队列判空

boolqueueempty(queue*q){assert(q);//if(q->_front==null)//{//return1;//}//else//{//return0;//}returnq->_front==null;}

4、入队操作

voidqueuepush(queue*q,qdatatypedata){assert(q);qnode*newnode=(qnode*)malloc(sizeof(qnode));if(newnode==null){exit(-1);}newnode->_data=data;newnode->_next=null;if(q->_front==null){q->_front=q->_rear=newnode;}else{q->_rear->_next=newnode;q->_rear=newnode;}}

5、出队操作

voidqueuepop(queue*q){assert(q);assert(!queueempty(q));qnode*next=q->_front->_next;free(q->_front);q->_front=next;if(q->_front==null){q->_rear=null;}}

6、取队头元素

qdatatypequeuefront(queue*q){assert(q);assert(!queueempty(q));returnq->_front->_data;}

7、取队尾操作

qdatatypequeueback(queue*q){assert(q);assert(!queueempty(q));returnq->_rear->_data;}

8、队中有效元素个数

intqueuesize(queue*q){assert(q);intsize=0;qnode*cur=q->_front;while(cur){size ;cur=cur->_next;}returnsize;}

循环队列

循环队列的定义

循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列结构中，当存储空间的最后一个位置已被使用而再要进入队运算时，只需要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。循环队列可以更简单防止伪溢出的发生，但队列大小是固定的。在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有maxsize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件是front=rear，而队列判满的条件是front=（rear 1)%maxsize。

循环队列的空间可以重复利用，解决了普通队列的空间浪费问题

循环队列的实现

typedefstruct{int*a;intfront;inttail;intk;}mycircularqueue;//提前声明判空判满boolmycircularqueueisempty(mycircularqueue*obj);boolmycircularqueueisfull(mycircularqueue*obj);//创建循环队列mycircularqueue*mycircularqueuecreate(intk){mycircularqueue*cq=(mycircularqueue*)malloc(sizeof(mycircularqueue));cq->a=(int*)malloc(sizeof(int)*(k 1));cq->front=cq->tail=0;cq->k=k;returncq;}//循环队列入队boolmycircularqueueenqueue(mycircularqueue*obj,intvalue){if(mycircularqueueisfull(obj)){returnfalse;}obj->a[obj->tail]=value;obj->tail ;obj->tail%=(obj->k 1);returntrue;}//循环队列出队boolmycircularqueuedequeue(mycircularqueue*obj){if(mycircularqueueisempty(obj)){returnfalse;}obj->front ;obj->front%=(obj->k 1);returntrue;}//循环队列取队头intmycircularqueuefront(mycircularqueue*obj){if(mycircularqueueisempty(obj)){return-1;}returnobj->a[obj->front];}//循环队列取队尾intmycircularqueuerear(mycircularqueue*obj){if(mycircularqueueisempty(obj)){return-1;}inti=(obj->tail obj->k)%(obj->k 1);returnobj->a[i];}//循环队列判空boolmycircularqueueisempty(mycircularqueue*obj){returnobj->front==obj->tail;}//循环队列判满boolmycircularqueueisfull(mycircularqueue*obj){return(obj->tail 1)%(obj->k 1)==obj->front;}//销毁循环队列voidmycircularqueuefree(mycircularqueue*obj){free(obj->a);free(obj);}

关于“c语言链式队列与循环队列怎么实现”这篇文章的内容就介绍到这里，感谢各位的阅读！相信大家对“c语言链式队列与循环队列怎么实现”知识都有一定的了解，大家如果还想学习更多知识，欢迎关注恰卡编程网行业资讯频道。