一、寫在前面
數據結構中的隊列應該是比較熟悉的了,就是先進先出,因為有序故得名隊列,就如同排隊嘛,在對尾插入新的節點,在對首刪除節點.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);}}運行結果：
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持武林網。