一、寫在前面
創(chuàng)新互聯(lián)建站長期為上1000家客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對(duì)不同對(duì)象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺(tái)，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為白堿灘企業(yè)提供專業(yè)的成都網(wǎng)站建設(shè)、網(wǎng)站制作，白堿灘網(wǎng)站改版等技術(shù)服務(wù)。擁有10余年豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開發(fā)。
數(shù)據(jù)結(jié)構(gòu)中的隊(duì)列應(yīng)該是比較熟悉的了,就是先進(jìn)先出,因?yàn)橛行蚬实妹?duì)列,就如同排隊(duì)嘛,在對(duì)尾插入新的節(jié)點(diǎn),在對(duì)首刪除節(jié)點(diǎn).jdk集合框架也是提供也一個(gè)Queue的接口.這個(gè)接口代表一個(gè)隊(duì)列.順序隊(duì)列:ArrayBlockingQueue,LinkedBlockingQueue.(上面兩種是足色隊(duì)列)還有一種是ConcurentLinkedQueue。
底層的實(shí)現(xiàn)由數(shù)組合鏈表兩種的,數(shù)組的實(shí)現(xiàn)會(huì)有個(gè)弊端的,會(huì)造成假滿的現(xiàn)象,開始的時(shí)候,隊(duì)列為空的時(shí)候,對(duì)首引用變量個(gè)對(duì)尾的引用變量都為null,隨著刪除隊(duì)列的元素,就會(huì)發(fā)生front+1,rear等于底層數(shù)組的容量了.在順序的存儲(chǔ)結(jié)構(gòu)中,front總是保存這著隊(duì)列中即將出隊(duì)列的元素的索引,rear總是保存著即將進(jìn)入隊(duì)列的元素的索引.隊(duì)列中的元素的個(gè)數(shù)就是rear-front的.在順序的隊(duì)列中,底層是數(shù)組,所以保存 的數(shù)據(jù)元素是不會(huì)改變的,改變的只有rear和front這兩個(gè)引用變量.
這里采用鏈?zhǔn)酱鎯?chǔ)可以有效的利用空間的,就是引用變量要占用額外的空間的.
隊(duì)列的常用的操作:
1:初始化
2:返回隊(duì)列的長度
3:添加元素
4:刪除元素
5:訪問對(duì)首的元素
6:訪問隊(duì)列的對(duì)尾的元素
7:判斷隊(duì)列是否為空
8:清空隊(duì)列
二、自定義的實(shí)現(xiàn)
源碼展示的比較清楚,就不用再多做介紹
public class LinkedQueue{ //自定義鏈隊(duì)列--采用非靜態(tài)內(nèi)部類來表示鏈隊(duì)列的數(shù)據(jù)節(jié)點(diǎn) private class Node{ //表示鏈隊(duì)列的數(shù)據(jù)節(jié)點(diǎn) private T data; //指向下一個(gè)節(jié)點(diǎn)的引用 private Node next; @SuppressWarnings("unused") public Node(){ } public Node(T data,Node next){ this.data=data; this.next=next; } } //定義鏈隊(duì)列的對(duì)首和對(duì)尾的引用 private Node front; private Node rear; //定義鏈棧的大小 private int size; //創(chuàng)建一個(gè)空的鏈對(duì)列 public LinkedQueue(){ front=null; rear=null; } //以確定的元素來創(chuàng)建一個(gè)鏈對(duì)列,只有一個(gè)節(jié)點(diǎn)的 public LinkedQueue(T element){ front=new Node(element,null); //指向同一個(gè)元素 rear=front; size++; } //返回鏈隊(duì)列的大小 public int length(){ return size; } //返回鏈隊(duì)列得對(duì)首的元素,不刪除對(duì)首的元素 public T elementFront(){ if(!empty()){ return front.data; }else{ return null; } } //訪問隊(duì)列的最后一個(gè)元素 public T elementRear(){ if(!empty()){ return rear.data; }else{ return null; } } //返回當(dāng)前的鏈對(duì)隊(duì)列是否為空 public boolean empty(){ return size==0; } //清空一個(gè)鏈隊(duì)列 public void clear(){ front=null; rear=null; size=0; } //插入鏈隊(duì)列一個(gè)節(jié)點(diǎn)--對(duì)尾 public void add(T element){ //如果鏈對(duì)列為空,就新建一個(gè)節(jié)點(diǎn) if(front==null){ rear=new Node(element,null); front=rear; }else{ //動(dòng)態(tài)創(chuàng)建新節(jié)點(diǎn) Node newRear=new Node(element,null); rear.next=newRear; rear=newRear; } size++; } //刪除鏈隊(duì)列一個(gè)節(jié)點(diǎn),返回刪除后的節(jié)點(diǎn) public T remove(){ Node oldFront=front; front=front.next; oldFront.next=null; size--; return oldFront.data; } //返回隊(duì)列 public String toString(){ //如果鏈隊(duì)列為空鏈隊(duì)列是 if(empty()){ return "[]"; }else{ StringBuilder sBuilder=new StringBuilder("["); for(Node current=front;current!=null;current=current.next){ sBuilder.append(current.data.toString()+","); } int len=sBuilder.length(); return sBuilder.delete(len-1, len).append("]").toString(); } } public static void main(String[] args) { LinkedQueue lQueue=new LinkedQueue (); lQueue.add("aaa"); lQueue.add("bbb"); lQueue.add("ccc"); lQueue.add("ddd"); System.out.println("返回隊(duì)列的頭結(jié)點(diǎn)的數(shù)值:"+lQueue.elementFront()); System.out.println("返回隊(duì)列的尾節(jié)點(diǎn)的數(shù)值:"+lQueue.elementRear()); System.out.println(lQueue.length()); System.out.println(lQueue); } }
運(yùn)行結(jié)果：
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持創(chuàng)新互聯(lián)。
重慶分公司
重慶分公司
