Java基础复习笔记06数据结构队列

1、Java基础复习笔记06数据结构-队列刘岩Email:suhuanzheng77848771.队列队列又是一种比较特殊的线性表，和栈一样在线性表的基础上进行了一些限制操作。就是队列了。顾名思义，队列就是咱们排队买火车票一样，排在最前面的先买到，排到后队列的操作一般包括：进队列、出队列，访问队列头元素、删除队列头元素、判断队列是否为空、获得队列大小这些核心操作。Sun为Java的队列规定了一个规范、反映出来的的就是java.util.Queue,实现了此接口的所有方法，相当于"你按照Sun的Java规范为自己写了一个符合规范的队列实现类”。3 .队列的使用场景队列的使用场景其实个人感觉

2、比栈要广泛一些，比如开发网络服务中间件，处理并发消息的时候就需要将这些消息组成队列的方式一个一个处理，再比如对象池的应用，底层完全可以做成一个对象队列，将一个用完的对象放回池中后，就是放到等待队列中，先归还的对象，下次再使用的时候就比后放入的对象优先调用，因为先归还的对象肯定是休息了很久了，该对象应当回收的资源也都回收了。4 .队列的顺序实现和栈结构一样队列也有两种实现方式，先来看顺序的实现方式，顺序实现方式就是利用数组，记录当前队列头标记nowTopIndex以及下一个、新的队列结尾元素的标记newTaillndex。程序如下：packagedateStructer.queue;/*顺序队列

3、authorliuyanparam<E>*/publicclassMyArrayQueue<E>implementsQueue<E>/默认大小privatefinalstaticintDefSize=32;/临时数组privateObjectobjects;/当前队列头元素索引privateintnowTopIndex;/下一个队列新元素的索引privateintnewTailIndex;publicMyArrayQueue()objects=newObjectDefSize;/* 添加元素* /Overridepublicbooleanadd(Ee)int

4、elementSize=newTailIndex-nowTopIndexif(elementSize=0&&newTailIndex=0)objects0=e;nowTopIndex=0;newTailIndex=1;returntrue;objectsnewTailIndex+=e;returntrue;/* 获取队头元素* /OverridepublicEelement()return(E)objectsnowTopIndex;/* 返回头元素，不删除头元素* /OverridepublicEpeek()return(E)objectsnowTopIndex;/* 返回头元

5、素，删除头元素* /OverridepublicE poll() if ( objects nowTopIndex = null ) return null ;E date = (E) objects nowTopIndex ; objects nowTopIndex + = null ;return date;Overridepublic E remove() if ( nowTopIndex = 0) return null ;E date = (E) objects nowTopIndex ; objects nowTopIndex - = null ; return date;Over

6、ride public void clear() Arrays. f川 (objects nowTopIndex = 0; newTailIndex = 0;null );Overridepublic boolean contains(Object object) for ( int i = 0; i <objects . lengthif (object = objects i) return true ;i+) returnfalse;OverridepublicbooleanisEmpty()intelementSize=newTaillndex-nowTopIndex;retur

7、nelementSize=0;Overridepublicintsize()returnnewTailIndex-nowTopIndex;OverridepublicStringtoString()StringBufferstr=newStringBuffer("");intelementSize=newTailIndex-nowTopIndex;for(inti=nowTopIndex;i<newTailIndex;i+)str.append(""+objectsi.toString()+",");if(elementSize

8、>0)returnstr.substring(0,str.lastIndexOf(",")+""returnstr.append("").toString();测试代码如下publicstaticvoidmain(String口args)MyArrayQueue<String>myQueue=newMyArrayQueue<String>();myQueue.add("1");myQueue.add("2");myQueue.add("3");S

9、ystem.out.println(myQueue.toString();Stringe=myQueue.poll();System.out.println(e);System.out.println(myQueue.toString();myQueue.add("4");e=myQueue.peek();System.out.println("是否为空队列"+myQueue.isEmpty();System.out.println("队列大小"+myQueue.size();System.out.println(e);System.

10、out.println(myQueue.toString();System.out.println("是否包含相关元素"+myQueue.contains("1");System.out.println("是否包含相关元素"+myQueue.contains("2");myQueue.clear();System.out.println("是否为空队列"+myQueue.isEmpty();运行后效果如下1,2,312,3是否为空队列false队列大小322,3,4是否包含相关元素false是否

11、包含相关元素true是否为空队列true5.队列的链表实现相对于顺序实现方式，链式实现相对比较简单，只需要利用Node结构，记录下队列的/*头Node和尾巴Node,在记录下元素个数就可以了。算法如下packagedateStructer.queue;实现自己的队列authorliuyanparam<E>*/publicclassMyQueue<E>implementsQueue<E>/*双向链表结构*/publicclassLinkNode/真正的数据域privateEdate;/记录上一个节点privateLinkNodeprevLinkNode;/记录

12、下一个节点privateLinkNodenextLinkNode;publicLinkNode()publicLinkNode(Edate,LinkNodeprevLinkNode,LinkNodenextLinkNode)this.date=date;this.prevLinkNode=prevLinkNode;this.nextLinkNode=nextLinkNode;/结点个数private int nodeSize ;/头结点privateLinkNodeheadNode/尾巴节点privateLinkNodetailNodepublic MyQueue()null ;null ;h

13、eadNode = tailNode =/* 添加元素*/Overridepublic booleanif ( nodeSize headNode else add(Eelement)=0)=newLinkNode(element,null,tailNode);if(tailNode=null)tailNode=newLinkNode(element,headNode,null);headNode.nextLinkNode=tailNode;nodeSize+;returntruenull );LinkNodelinkNode=tailNode;tailNode=newLinkNode(ele

14、ment,linkNode,linkNode.nextLinkNode=tailNode;nodeSize+;returntrue/*访问队列头元素*/OverridepublicEelement。returnheadNode.date/*返回头元素，不删除头元素*/OverridepublicEpeek()returnheadNode.date/*返回头元素，删除头元素*/OverridepublicEpoll()LinkNodeheadNodeTemp=headNode;Edate=headNodeTemp.date;if(headNode.nextLinkNode=null)headNo

15、de.date=null;headNode=null;nodeSize-;returndate;elseheadNode=headNode.nextLinkNodeif(headNode=tailNode)tailNode=null;nodeSize-;returnheadNodeTemp.date;/* 清除所有元素* /Overridepublicvoidclear()LinkNodelinkNodeNowTemp=headNodefor(inti=0;i<nodeSize;i+)if(linkNodeNowTemp!=tailNode&&linkNodeNowTem

16、p!=headNode)linkNodeNowTemp=linkNodeNowTempnextLinkNode;linkNodeNowTemp.prevLinkNode.nextLinkNode=nulllinkNodeNowTemp.prevLinkNode.prevLinkNode=nulllinkNodeNowTemp.prevLinkNode.date=null;linkNodeNowTemp.prevLinkNode=null;elseif(linkNodeNowTemp=tailNode)linkNodeNowTemp.prevLinkNode=null;elseif(linkNo

17、deNowTemp=headNode)linkNodeNowTemp.nextLinkNode=null;headNode=nulltailNode=nullnodeSize=0;/* 判断是否存在* /Overridepublicbooleancontains(Objectobject)headNode ;LinkNodelinkNodeNowTemp=/*/for (ifint i = 0; i <nodeSize ; i+) (object = linkNodeNowTemp. return true ;linkNodeNowTemp = linkNodeNowTemp. retu

18、rn false ;队列是否为空Overridepublic boolean isEmpty() / TODO Auto-generated method stub return nodeSize = 0;Overridepublic int size() /TODO Auto-generated method stubreturn nodeSize ;/*根据索引号查找节点param index return*/public LinkNode findLinkNodeByIndex(LinkNode linkNodeNowTemp =for (int i = 0; i <nodeSizedate ) nextLinkNode ;int index) headNode ;i+) if(i=index)returnlinkNodeNowTemp;linkNodeNowTemp=linkNodeNowTemp.nextLinkNodereturnnull;OverridepublicStringtoString()StringBuffer str = LinkNode linkNode = for ( in