一、寫在前面
數據結構中的隊列應該是比較熟悉的了,就是先進先出,因為有序故得名隊列,就如同排隊嘛,在對尾插入新的節點,在對首刪除節點.jdk集合框架也是提供也一個Queue的接口.這個接口代表一個隊列.順序隊列:ArrayBlockingQueue,LinkedBlockingQueue.(上面兩種是足色隊列)還有一種是ConcurentLinkedQueue。
底層的實現由數組合鏈表兩種的,數組的實現會有個弊端的,會造成假滿的現象,開始的時候,隊列為空的時候,對首引用變量個對尾的引用變量都為null,隨著刪除隊列的元素,就會發生front+1,rear等于底層數組的容量了.在順序的存儲結構中,front總是保存這著隊列中即將出隊列的元素的索引,rear總是保存著即將進入隊列的元素的索引.隊列中的元素的個數就是rear-front的.在順序的隊列中,底層是數組,所以保存 的數據元素是不會改變的,改變的只有rear和front這兩個引用變量.
這里采用鏈式存儲可以有效的利用空間的,就是引用變量要占用額外的空間的.
隊列的常用的操作:
1:初始化
2:返回隊列的長度
3:添加元素
4:刪除元素
5:訪問對首的元素
6:訪問隊列的對尾的元素
7:判斷隊列是否為空
8:清空隊列
二、自定義的實現
源碼展示的比較清楚,就不用再多做介紹
public class LinkedQueue<T>{
//自定義鏈隊列--采用非靜態內部類來表示鏈隊列的數據節點
private class Node{
//表示鏈隊列的數據節點
private T data;
//指向下一個節點的引用
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;
//創建一個空的鏈對列
public LinkedQueue(){
front=null;
rear=null;
}
//以確定的元素來創建一個鏈對列,只有一個節點的
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;
}
}
//返回當前的鏈對隊列是否為空
public boolean empty(){
return size==0;
}
//清空一個鏈隊列
public void clear(){
front=null;
rear=null;
size=0;
}
//插入鏈隊列一個節點--對尾
public void add(T element){
//如果鏈對列為空,就新建一個節點
if(front==null){
rear=new Node(element,null);
front=rear;
}else{
//動態創建新節點
Node newRear=new Node(element,null);
rear.next=newRear;
rear=newRear;
}
size++;
}
//刪除鏈隊列一個節點,返回刪除后的節點
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("返回隊列的頭結點的數值:"+lQueue.elementFront());
System.out.println("返回隊列的尾節點的數值:"+lQueue.elementRear());
System.out.println(lQueue.length());
System.out.println(lQueue);
}
}
運行結果：
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
