隊列的概述
正如上次文章所述。隊列的實作方式有很多種，其中一種就是使用最簡單的數組來實作。還有使用連結清單的方式來實 現隊列。這裡簡單回顧下：
隊列是一種特殊的線性表，特殊之處在于它隻允許在表的前端（front）進行删除操作，而在表的後端（rear）進行 插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行删除操作的端稱為隊 頭。隊列中沒有元素時，稱為空隊列。 隊列的資料元素又稱為隊列元素。在隊列中插入一個隊列元素稱為入隊，從 隊列中删除一個隊列元素稱為出隊。因 為隊列隻允許在一端插入，在另一端删除，是以隻有最早進入隊列的元素才 能最先從隊列中删除，故隊列又稱為先 進先出（FIFO—first in first out）線性表。
02數組和連結清單的存儲資料的特點
☑ 數組
在記憶體中，數組是一塊連續的區域，申請的記憶體必須是連續的，而且數組申請的時候需要指定長度（也就是說需要 提前申請）。例如：申請了長度為10 ，但是如果裡面隻存儲了5個元素。那麼其他的記憶體就浪費了。
另外，資料的插入 和 删除 效率低下，因為數組是連續的，如果在插入的時候，就要求後續資料，在記憶體中往後移 動。例如（就像看電影座位有5個座位，中間有人坐了，如果來一個人坐中間，原本的人就要移動座位才行）擴充不容易，因為是提前申請記憶體空間，如果不夠就沒辦法繼續存儲。如果申請太多，沒用就是資源浪費了。
讀取效率高，因為數組的位址是連續的，并且知道位址之後，很快就可以根據位址查詢資料了。
☑ 連結清單
連結清單中申請的記憶體位址是随機的，可以不重複，也就意味着 可以充分利用資源，不會有像數組那樣的連續記憶體。增加和删除資料 效率高，因為連結清單（包括單清單和雙連結清單），有頭結點和尾結點，從頭部或者從尾部添加結點（數 據）的時候隻需要記住原頭不結點的位址或者是尾部結點的位址即可。很快便能申請記憶體位址。
擴充容易，因為不需要連續申請記憶體，資料可以存儲在任意的記憶體位址中。
查詢資料的時候效率低下，因為連結清單中的資料都是通過頭來找到的，（要找連結清單中的一個資料，必須就是從頭開始找起）。
03連結清單的隊列實作
實作思路：
·建立一個雙連結清單類
·建立一個以連結清單實作的隊列類，比如實作Queue的隊列接口
·在隊列類中使用連結清單作為資料存儲
·簡單實作入隊和出隊的模拟
☑ 建立雙連結清單類
package com.itheima.link;
import java.util.Comparator;
import java.util.Iterator;
public class MyDoubleLink2<E> implements Iterable<E> {
private class Node {
Node prev; // 上一個節點
E data;// 資料
Node next;// 下一個節點
}
private Node head;// 頭節點
private Node rear;// 尾節點
public void remove(Object data) {
// 1. 查找資料是否存在,查找資料所在的節點
Node node = findData(data);
// 2.判斷node是否存在
if (node != null) {
remove(node);
}
}
public boolean isEmpty(){
return head == null;
}
public E removeRear(){
E data = null;
if (rear != null) {
data = rear.data;
//移除
rear = rear.prev;
if (rear == null) {
//沒有節點
head = null;
} else {
rear.next = null;
}
}
return data;
}
public E removeHead(){
E data = null;
if (head != null){
data = head.data;
//下一個資料成為頭節點
head = head.next;
//後面沒有
if (head != null)
head.prev = null;
else {
//沒有資料
rear = null;
}
}
return data;
}
public boolean contains(Object data) {
return findData(data) != null;
}
private void remove(Node node) {
if (node == head && node == rear) {
// 1.隻有一個資料
head = null;
rear = null;
} else if (node == head) {
// 2.删除頭節點,後面肯定有節點
head = head.next;
head.prev = null;
} else if (node == rear) {
// 3.删除尾節點,前面肯定有節點
rear = rear.prev;
rear.next = null;
} else {
// 4.删除中間節點,前後肯定有節點
node.prev.next = node.next;
node.next.prev = node.prev;
}
}
private Node findData(Object data) {
Node node = head;
while (node != null) {
if (node.data.equals(data)
&& node.data.hashCode() == data.hashCode()) {
// 找到資料
break;
} else {
// 繼續下一個
node = node.next;
}
}
return node;
}
public void addHead(E data) {
// 1. 建立新的節點
Node node = new Node();
// 2. 把資料放入節點中
node.data = data;
// 3. 把節點連結到連結清單中
// 從連結清單的尾部添加資料
if (head == null) {
// 說明連結清單是空的 ,node就成頭節點
rear = node;
head = node;
} else {
// 有頭節點
head.prev = node;
node.next = head;
head = node;
}
}
public void add(E data) {
// 1. 建立新的節點
Node node = new Node();
// 2. 把資料放入節點中
node.data = data;
// 3. 把節點連結到連結清單中
// 從連結清單的尾部添加資料
if (rear == null) {
// 說明連結清單是空的 ,node就成頭節點
rear = node;
head = node;
} else {
// 有頭節點
rear.next = node;
node.prev = rear;
rear = node;
}
}
@Override
public String toString() {
StringBuilder mess = new StringBuilder("[");
// 周遊連結清單中所有的資料
Node node = head;// 從頭節點開始周遊資料
while (node != null) {
// 有資料
// 拼接資料
// 判斷是否是尾節點
if (node != rear) {
mess.append(node.data + ", ");
} else {
mess.append(node.data);
}
// 條件的改變
node = node.next;
}
mess.append("]");
return mess.toString();
}
@Override
public Iterator iterator() {
class MyIte implements Iterator {
private Node node = head;// 從頭節點周遊
@Override
public boolean hasNext() {
return node != null;
}
@Override
public Object next() {
// 擷取資料
Object data = node.data;
// 設定下一個資料
node = node.next;
return data;
}
@Override
public void remove() {
// 删除next方法傳回的資料
MyDoubleLink2.this.remove(node.prev);
}
}
return new MyIte();
}
}
從尾部結點的資料方法如下：
public void add(E data) {
// 1. 建立新的節點
Node node = new Node();
// 2. 把資料放入節點中
node.data = data;
// 3. 把節點連結到連結清單中
// 從連結清單的尾部添加資料
if (rear == null) {
// 說明連結清單是空的 ,node就成頭節點
rear = node;
head = node;
} else {
// 有頭節點
rear.next = node;
node.prev = rear;
rear = node;
}
}
☑ 建立以連結清單存儲資料的隊列類
package com.itheima.queue;
import com.itheima.link.MyDoubleLink;
import java.util.Collection;
import java.util.Iterator;
import java.util.Queue;
public class MyLinkQueue<E> implements Queue<E> {
private MyDoubleLink<E> datas = new MyDoubleLink2<>();
@Override
public boolean add(E e) {
datas.add(e);
return true;
}
@Override
public E poll() {
return datas.removeHead();
}
@Override
public String toString() {
return datas.toString();
}
@Override
public int size() {
return 0;
}
@Override
public boolean isEmpty() {
return datas.isEmpty();
}
@Override
public boolean contains(Object o) {
return false;
}
@Override
public Iterator<E> iterator() {
return null;
}
@Override
public Object[] toArray() {
return new Object[0];
}
@Override
public <T> T[] toArray(T[] a) {
return null;
}
@Override
public boolean remove(Object o) {
return false;
}
@Override
public boolean containsAll(Collection<?> c) {
return false;
}
@Override
public boolean addAll(Collection<? extends E> c) {
return false;
}
@Override
public boolean removeAll(Collection<?> c) {
return false;
}
@Override
public boolean retainAll(Collection<?> c) {
return false;
}
@Override
public void clear() {
}
@Override
public boolean offer(E e) {
return false;
}
@Override
public E remove() {
return null;
}
@Override
public E element() {
return null;
}
@Override
public E peek() {
return null;
}
}
方法解析：
為了以後的擴充性 可以實作Queue的接口，此處為示範 隻實作了其中的幾個方法：
·add(E e) 添加資料（入隊）
·poll() 移除資料（出隊）
·isEmpty() 判斷隊列是否為空
·toString() 重寫方法 便于列印
☑ 建立雙連結清單的資料儲存對象
在隊列類中建立
private MyDoubleLink<E> datas = new MyDoubleLink2<>();
☑ 入隊方法
入隊方法如下，參考剛才的方法。入隊的元素從尾部結點添加即可。
@Override
public boolean add(E e) {
datas.add(e);
return true;
}
如下圖所示：
解釋：
·将原尾結點的NEXT指向新的結點
·将新結點的prev指向原尾結點
·将新結點作為尾結點（也就是将尾結點的引用指向那個新的結點）
了解圖如下：
☑ 出隊方法
@Override
public E poll() {
return datas.removeHead();
}
隊列的方式是：先進先出，該方法表示從頭開始删除節點。也就是出隊。頭先添加，最先出去的也是頭結點。
如下圖：
·先判斷是否有頭 如果有，那麼将頭結點引用指向下一個結點。
·再将頭結點的prev指派為空即可。
04總結
以上示範了隊列的連結清單實作方式。
對于想快速通路，不經常進行插入和删除的操作 可以使用數組。對于經常進行添加和删除，對查詢沒有特别要求的可以使用連結清單。