快捷導(dǎo)航

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

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

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

一、寫在前面

數(shù)據(jù)結(jié)構(gòu)中的隊列應(yīng)該是比較熟悉的了,就是先進(jìn)先出,因為有序故得名隊列,就如同排隊嘛,在對尾插入新的節(jié)點,在對首刪除節(jié)點.jdk集合框架也是提供也一個Queue的接口.這個接口代表一個隊列.順序隊列:ArrayBlockingQueue,LinkedBlockingQueue.(上面兩種是足色隊列)還有一種是ConcurentLinkedQueue。
底層的實現(xiàn)由數(shù)組合鏈表兩種的,數(shù)組的實現(xiàn)會有個弊端的,會造成假滿的現(xiàn)象,開始的時候,隊列為空的時候,對首引用變量個對尾的引用變量都為null,隨著刪除隊列的元素,就會發(fā)生front+1,rear等于底層數(shù)組的容量了.在順序的存儲結(jié)構(gòu)中,front總是保存這著隊列中即將出隊列的元素的索引,rear總是保存著即將進(jìn)入隊列的元素的索引.隊列中的元素的個數(shù)就是rear-front的.在順序的隊列中,底層是數(shù)組,所以保存的數(shù)據(jù)元素是不會改變的,改變的只有rear和front這兩個引用變量.
這里采用鏈?zhǔn)酱鎯梢杂行У睦每臻g的,就是引用變量要占用額外的空間的.

隊列的常用的操作:

             1:初始化
             2:返回隊列的長度
             3:添加元素
             4:刪除元素
             5:訪問對首的元素
             6:訪問隊列的對尾的元素
             7:判斷隊列是否為空
             8:清空隊列

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

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

public class LinkedQueue<T>{
//自定義鏈隊列--采用非靜態(tài)內(nèi)部類來表示鏈隊列的數(shù)據(jù)節(jié)點
private class Node{
//表示鏈隊列的數(shù)據(jù)節(jié)點 
private T data;
//指向下一個節(jié)點的引用
private Node next;
 @SuppressWarnings("unused")
 public Node(){
 
}
public Node(T data,Node next){
 this.data=data;
 this.next=next;
 }
}
//定義鏈隊列的對首和對尾的引用
 private Node front;
 private Node rear;
 //定義鏈棧的大小
private int size;
 //創(chuàng)建一個空的鏈對列
public LinkedQueue(){
 front=null;
 rear=null;
}
//以確定的元素來創(chuàng)建一個鏈對列,只有一個節(jié)點的
public LinkedQueue(T element){
front=new Node(element,null);
//指向同一個元素
rear=front;
size++;
}
//返回鏈隊列的大小
public int length(){
return size;
}
//返回鏈隊列得對首的元素,不刪除對首的元素
public T elementFront(){
if(!empty()){
 return front.data;
}else{
 return null; 
 
}
}
//訪問隊列的最后一個元素
public T elementRear(){
if(!empty()){
 return rear.data;
 
}else{
 return null; 
} 
}
//返回當(dāng)前的鏈對隊列是否為空
public boolean empty(){
 return size==0;
 }
//清空一個鏈隊列
public void clear(){
 front=null;
 rear=null;
 size=0;
}
//插入鏈隊列一個節(jié)點--對尾
public void add(T element){
 //如果鏈對列為空,就新建一個節(jié)點
 if(front==null){
 rear=new Node(element,null);
 front=rear;
 }else{
 //動態(tài)創(chuàng)建新節(jié)點
 Node newRear=new Node(element,null);
 rear.next=newRear;
 rear=newRear; 
}
size++;
}
//刪除鏈隊列一個節(jié)點,返回刪除后的節(jié)點
public T remove(){
   Node oldFront=front;
   front=front.next;
   oldFront.next=null;
   size--;
   return oldFront.data;
}
//返回隊列
public String toString(){
 //如果鏈隊列為空鏈隊列是
 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("返回隊列的頭結(jié)點的數(shù)值:"+lQueue.elementFront());
System.out.println("返回隊列的尾節(jié)點的數(shù)值:"+lQueue.elementRear());
System.out.println(lQueue.length());
System.out.println(lQueue);
}
}

運行結(jié)果：