java实现队列数据结构代码详解
什么是队列结构
一种线性结构,具有特殊的运算法则【只能在一端(队头)删除,在另一端(队尾)插入】。
分类:
顺序队列结构
链式队列结构
基本操作:
入队列
出队列
给出一些应用队列的场景
1):当作业被送到打印机的时候,就可以按到达的顺序排起来,因此每一份作业是队列的节点。
2):售票口的人买票的顺序的按照先来先买的顺序售票。
3):当所有的终端被占用,由于资源有限,来访请求需要放在一个队列中等候。
队列是先进先出的!
我们设置一个叫做LinkQueue
在Linkqueue的里面设置队列头指针front和队列尾指针rear,长度size=0;我们先设置一个构造器LinkQueue(),用来初始化这两个指针节点,当然,刚开始初始化的时候这两个指针仅仅是一个节点而已,里面的data是空的,我们还让这两个指针相等。
//链的数据结构 privateclassNode{ publicTdata; publicNodenext; //无参构造函数 publicNode(){} publicNode(Tdata,Nodenext){ this.data=data; this.next=next; } } //队列头指针 privateNodefront; //队列尾指针 privateNoderear;
publicLinkQueue(){ Noden=newNode(null,null); n.next=null; front=rear=n; }
当我们向该队列添加元素的时候,就会生成一个新的节点,其data就是你要加的元素,(当添加一个节点时,该节点就是队尾指针指向的最后的节点,一直排在最后),所以队尾rear.next=newNode(“新创建的节点”).这是第一个节点,也是最后一个节点,所以front.next=newNode.然后我们再让rear=newNode(不断更新)。
publicvoidenqueue(Tdata){ //创建一个节点 Nodes=newNode(data,null); //将队尾指针指向新加入的节点,将s节点插入队尾 rear.next=s; rear=s; size++; }
当队列出队的时候,还记得我们有一个Node是front.next=newNode吗?这就是第一个节点。先暂且把它叫做p,所以p.next=第二个节点,这时我们再把front.next=p.next;这样头指针就指向了第二个元素(每一次调用的时候队列头指针指会发生变化)。
publicTdequeue(){ if(rear==front){ try{ thrownewException("堆栈为空"); }catch(Exceptione){ e.printStackTrace(); } returnnull; }else{ //暂存队头元素 Nodep=front.next; Tx=p.data; //将队头元素所在节点摘链 front.next=p.next; //判断出队列长度是否为1 if(p.next==null) rear=front; //删除节点 p=null; size--; returnx; } }
到此为止,队列的核心操作就完毕了,剩下的比如说size(长度),isEmpty(是否为空),就不在说了。(因为太简单了!)
具体源码如下:
publicclassLinkQueue{ //链的数据结构 privateclassNode{ publicTdata; publicNodenext; //无参构造函数 publicNode(){ } publicNode(Tdata,Nodenext){ this.data=data; this.next=next; } } //队列头指针 privateNodefront; //队列尾指针 privateNoderear; //队列长度 privateintsize=0; publicLinkQueue(){ Noden=newNode(null,null); n.next=null; front=rear=n; } /** *队列入队算法 *@paramdata *@authorWWX */ publicvoidenqueue(Tdata){ //创建一个节点 Nodes=newNode(data,null); //将队尾指针指向新加入的节点,将s节点插入队尾 rear.next=s; rear=s; size++; } /** *队列出队算法 *@return *@authorWWX */ publicTdequeue(){ if(rear==front){ try{ thrownewException("堆栈为空"); } catch(Exceptione){ e.printStackTrace(); } returnnull; }else{ //暂存队头元素 Nodep=front.next; Tx=p.data; //将队头元素所在节点摘链 front.next=p.next; //判断出队列长度是否为1 if(p.next==null) rear=front; //删除节点 p=null; size--; returnx; } } /** *队列长队 *@return *@authorWWX */ publicintsize(){ returnsize; } /** *判断队列是否为空 *@return *@authorWWX */ publicBooleanisEmpty(){ returnsize==0; } }
另:我曾经看过一本JavaScript数据结构书,里面讲的浅显易懂,很适合前端搞js开发的让人理解的更为深入,在此给予推荐。
《数据结构与算法JavaScript描述》
总结
以上就是本文关于java实现队列数据结构代码详解的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站:
Java编程用两个栈实现队列代码分享
java编程实现优先队列的二叉堆代码分享
java编程队列数据结构代码示例
如有不足之处,欢迎留言指出。
声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:czq8825#qq.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。