java鏈表應用--基于鏈表實現(xiàn)隊列詳解（尾指針操作）

發(fā)布時間：2020-08-29 14:54:19 來源：腳本之家閱讀：148 作者：WFaceBoss 欄目：編程語言

本文實例講述了java基于鏈表實現(xiàn)隊列。分享給大家供大家參考，具體如下：

在開始棧的實現(xiàn)之前，我們再來看看關(guān)于鏈表的只在頭部進行的增加、刪除、查找操作，時間復雜度均為O(1)。

一、鏈表改進分析

對于隊列這種數(shù)據(jù)結(jié)構(gòu)，需要在線性結(jié)構(gòu)的一端插入元素，另外一端刪除元素。因此此時基于鏈表來實現(xiàn)隊列，則有一端的時間復雜度為O(n)。因此我們不能使用之前已經(jīng)實現(xiàn)的鏈表結(jié)構(gòu)，我們需要改進我們的鏈表。思路如下：

1.參考在鏈表頭部刪除、增加元素的時間復雜度為O(1)的思路，我們在鏈表的尾部設立一個Node型的變量tail來記錄鏈表的尾部在哪，此時再head端和tail端添加元素都是及其簡單的，在head端刪除元素也是及其簡單的，但對于在tail端刪除元素時，是無法在時間復雜度為O(1)的情況進行的，也就是從tail端刪除元素時不容易的。

java鏈表應用--基于鏈表實現(xiàn)隊列詳解（尾指針操作）

2.只在頭部head刪除元素（隊首），在尾部tail端添加元素（隊尾）。

java鏈表應用--基于鏈表實現(xiàn)隊列詳解（尾指針操作）

3.由于在基于鏈表實現(xiàn)隊列時不涉及到操作鏈表中間元素，此時我們改進的鏈表中，不在使用虛擬頭節(jié)，因此也就可能造成在沒有虛擬頭節(jié)點的情況下，鏈表為空。

二、鏈表改進代碼

前言，在寫本小節(jié)之前，我們已經(jīng)實現(xiàn)了一個基于靜態(tài)數(shù)組的隊列，轉(zhuǎn)到查看。此處我們實現(xiàn)基于鏈表的隊列。

在實現(xiàn)基于靜態(tài)數(shù)組的隊列的時候，我們已經(jīng)新建了一個package，此時我們在該package下新建一個LinkedListQueue類，用來實現(xiàn)Queue接口，目錄結(jié)構(gòu)為：

java鏈表應用--基于鏈表實現(xiàn)隊列詳解（尾指針操作）

1.Queue接口代碼

package Queue;

public interface Queue<E> {
  //獲取隊列中元素個數(shù)
  int getSize();

  //隊列中元素是否為空
  boolean isEmpty();

  //入隊列
  void enqueue(E e);

  //出隊列
  public E dequeue();

  //獲取隊首元素
  public E getFront();
}

2.LinkedListQueue類

package Queue;

public class LinkedListQueue<E> implements Queue<E> {

  //將Node節(jié)點設計成私有的類中類
  private class Node<E> {
    public E e;
    public Node next;

    //兩個參數(shù)的構(gòu)造函數(shù)
    public Node(E e, Node next) {
      this.e = e;
      this.next = next;
    }

    //一個參數(shù)的構(gòu)造函數(shù)
    public Node(E e) {
      this.e = e;
      this.next = null;
    }

    //無參構(gòu)造函數(shù)
    public Node() {
      this(null, null);
    }

    @Override
    public String toString() {
      return e.toString();
    }
  }

  private Node<E> head, tail;

  private int size;


  //顯示初始化
  public LinkedListQueue() {
    head = null;
    tail = null;
    size = 0;
  }

  //獲取隊列中節(jié)點個數(shù)
  @Override
  public int getSize() {
    return size;
  }

  //隊列中是否為空
  @Override
  public boolean isEmpty() {
    return size == 0;
  }

  //鏈表尾部進隊操作
  @Override
  public void enqueue(E e) {
    if (tail == null) {
      tail = new Node(e);
      head = tail;
    } else {
      tail.next = new Node(e);
      tail = tail.next;
    }
    size++;
  }

  //鏈表頭部出隊操作
  @Override
  public E dequeue() {
    if (isEmpty()) {
      throw new IllegalArgumentException("鏈表為空");
    }

    Node<E> retNode = head;
    head = head.next;
    retNode.next = null;
    if (head == null) {//當鏈表只有一個元素時
      tail = null;
    }

    size--;
    return retNode.e;
  }

  //獲取隊首元素
  @Override
  public E getFront() {
    if (isEmpty()) {
      throw new IllegalArgumentException("鏈表為空");
    }
    return head.e;
  }


  //為了便于測試，重寫object類toString()方法
  @Override
  public String toString() {
    StringBuilder res = new StringBuilder();
    res.append("Queue: front ");
    Node<E> cur = head;
    while (cur != null) {
      res.append(cur + "->");
      cur = cur.next;
    }
    res.append("NULL tail");
    return res.toString();
  }


}

3.為了便于測試，在LinkedListQueue類中添加一個main函數(shù)

 //測試用例
  public static void main(String[] args) {
    LinkedListQueue<Integer> queue = new LinkedListQueue<Integer>();
    for (int i = 0; i < 10; i++) {
      queue.enqueue(i);
      System.out.println(queue);

      if (i % 3 == 2) {//每添加3個元素出隊列一個
        queue.dequeue();
        System.out.println(queue);
      }

    }

  }

4.結(jié)果為

java鏈表應用--基于鏈表實現(xiàn)隊列詳解（尾指針操作）

結(jié)果分析：每進隊3個元素出隊列一個。

關(guān)于本小節(jié)，若您覺得還行、還過得去，記得給個推薦哦~，謝謝?。?/p>

本節(jié)源碼 https://github.com/FelixBin/dataStructure/blob/master/src/Queue/LinkedListQueue.java

更多關(guān)于java算法相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Java操作DOM節(jié)點技巧總結(jié)》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》

希望本文所述對大家java程序設計有所幫助。

向AI問一下細節(jié)

java鏈表應用--基于鏈表實現(xiàn)隊列詳解（尾指針操作）

一、鏈表改進分析

二、鏈表改進代碼

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標簽

一、鏈表改進分析

二、鏈表改進代碼