快捷導(dǎo)航

java鏈表應(yīng)用--基于鏈表實(shí)現(xiàn)隊(duì)列詳解（尾指針操作）

更新時(shí)間：2020年03月17日 12:13:09 作者：WFaceBoss

這篇文章主要介紹了java鏈表應(yīng)用--基于鏈表實(shí)現(xiàn)隊(duì)列,結(jié)合實(shí)例形式分析了java基于鏈表實(shí)現(xiàn)隊(duì)列尾指針相關(guān)操作使用技巧,需要的朋友可以參考下

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

在開(kāi)始棧的實(shí)現(xiàn)之前，我們?cè)賮?lái)看看關(guān)于鏈表的只在頭部進(jìn)行的增加、刪除、查找操作，時(shí)間復(fù)雜度均為O(1)。

一、鏈表改進(jìn)分析

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

1.參考在鏈表頭部刪除、增加元素的時(shí)間復(fù)雜度為O(1)的思路，我們?cè)阪湵淼奈膊吭O(shè)立一個(gè)Node型的變量tail來(lái)記錄鏈表的尾部在哪，此時(shí)再head端和tail端添加元素都是及其簡(jiǎn)單的，在head端刪除元素也是及其簡(jiǎn)單的，但對(duì)于在tail端刪除元素時(shí)，是無(wú)法在時(shí)間復(fù)雜度為O(1)的情況進(jìn)行的，也就是從tail端刪除元素時(shí)不容易的。

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

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

二、鏈表改進(jìn)代碼

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

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

1.Queue接口代碼

package Queue;

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

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

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

  //出隊(duì)列
  public E dequeue();

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

2.LinkedListQueue類

package Queue;

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

  //將Node節(jié)點(diǎn)設(shè)計(jì)成私有的類中類
  private class Node<E> {
    public E e;
    public Node next;

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

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

    //無(wú)參構(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;
  }

  //獲取隊(duì)列中節(jié)點(diǎn)個(gè)數(shù)
  @Override
  public int getSize() {
    return size;
  }

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

  //鏈表尾部進(jìn)隊(duì)操作
  @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++;
  }

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

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

    size--;
    return retNode.e;
  }

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


  //為了便于測(cè)試，重寫(xiě)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.為了便于測(cè)試，在LinkedListQueue類中添加一個(gè)main函數(shù)

 //測(cè)試用例
  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個(gè)元素出隊(duì)列一個(gè)
        queue.dequeue();
        System.out.println(queue);
      }

    }

  }

4.結(jié)果為