快捷導(dǎo)航

Java自定義實(shí)現(xiàn)鏈隊(duì)列詳解

更新時(shí)間：2017年12月06日 08:41:50 作者：HcJsJqJSSM

這篇文章主要為大家詳細(xì)介紹了Java自定義實(shí)現(xiàn)鏈隊(duì)列的相關(guān)資料，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

一、寫(xiě)在前面

數(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)象,開(kāi)始的時(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ì)列的長(zhǎng)度
             3:添加元素
             4:刪除元素
             5:訪問(wèn)對(duì)首的元素
             6:訪問(wèn)隊(duì)列的對(duì)尾的元素
             7:判斷隊(duì)列是否為空
             8:清空隊(duì)列

二、自定義的實(shí)現(xiàn)

源碼展示的比較清楚,就不用再多做介紹

public class LinkedQueue<T>{
//自定義鏈隊(duì)列--采用非靜態(tài)內(nèi)部類(lèi)來(lá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;
}
//以確定的元素來(lái)創(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; 
 
}
}
//訪問(wèn)隊(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<String> lQueue=new LinkedQueue<String>();
 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é)果：