文章目錄
和上一篇的棧相反，隊列(queue)是一種先進先出(First In First Out, FIFO)的線性表。
它隻允許在表的一端進行插入，而在另一端删除元素。這和日常生活中的排隊是一緻的，最早進入隊列的元素最早離開。
在隊列中，允許插入的一端稱為隊尾(rear), 允許 删除的一端則稱為隊頭(front)。出隊列和入隊列示意圖如下：
隊列的基本運算和堆棧類似，包含判空、擷取長度、入隊、出隊、出隊、取隊頭（不删除隊頭）等。
我們這裡定義一個隊列的接口。
/**
* @Author 三分惡
* @Date 2020/8/27
* @Description 隊列
*/
public interface Queue {
public boolean isEmpty(); //判空
public int size(); //擷取隊列容量
public void enQueue(Object element); //入隊
public Object deQueue(); //出隊
public Object getHead(); //取隊首元素
} 隊列是一種受限的線性表，同樣有順序和鍊式兩種實作。
這裡順序隊列通過可擴容數組來實作。
在類裡标記了隊頭和對尾的下标。
入隊時，隊尾往後移動，隊頭保持不變，出隊是隊頭往後移動，隊尾保持不變。
為什麼不保持隊頭指向0？因為如果隊首指向0，那麼出隊的時候需要将數組前移，時間複雜度為O(n)。使用了隊頭和隊尾标記之後，出隊時隊頭往後移動一位，這樣避免了元素的移動。
/**
* @Author 三分惡
* @Date 2020/8/27
* @Description 順序隊列
*/
public class ArrayQueue implements Queue{
private static int defaultSize=15; //預設容量
private int size; //實際容量：實際存儲元素個數
private Object[] data; //存放元素的數組
private int front=0; //隊頭（下标）
private int rear=0; //隊尾（下标）
/**
* 無參構造方法：按預設容量構造元素數組
*/
public ArrayQueue(){
data=new Object[defaultSize];
}
/**
* 有參構造方法：指定元素數組容量
* @param capacity
*/
public ArrayQueue(int capacity){
data=new Object[capacity];
}
/**
* 判空
* @return
*/
public boolean isEmpty() {
return size==0;
}
/**
* 擷取隊列元素個數
* @return
*/
public int size() {
return size;
}
/**
* 入隊
* @param element
*/
public void enQueue(Object element) {
//如果隊滿
if (size==data.length&&front==0){
//真隊滿，擴容
if (front==0){
//擴容兩倍的新數組
Object [] newData=new Object[size<<1];
//拷貝數組
System.arraycopy(data,0,newData,0,size);
data=newData;
}else{
//假隊滿：前移元素
//所有資料前移front位
for (int i=front;i<size;i++){
data[i-front] = data[i];
}
//隊尾前移front位
rear-=front;
//隊頭指向0
front=0;
}
}
//隊尾插入元素
data[rear]=element;
rear++;
size++;
}
/**
* 出隊
* @return
*/
public Object deQueue() {
if (isEmpty()){
throw new RuntimeException("隊空");
}
//取隊頭元素
Object f=data[front];
//隊頭數組元素指向null，幫助gc
data[front]=null;
//隊首指向下一進制素
front++;
//元素個數減1
size--;
//傳回隊首元素
return f;
}
/**
* 取隊首元素（不删除隊首元素）
* @return
*/
public Object getHead() {
if (isEmpty()){
throw new RuntimeException("隊空");
}
return data[front];
}
} 時間複雜度分析：
- 入隊：平均O(1)，最壞情況（擴容）O(n)
- 出隊：O(1)
- 取隊首：O(1)
這裡使用單向連結清單來實作鍊式隊列。
入隊是将隊尾指向插入的新元素，出隊是将隊頭指向隊頭的下一個元素。
/**
* @Author 三分惡
* @Date 2020/8/27
* @Description
*/
public class LinkedQueue implements Queue{
/**
* 節點類
* @param <T>
*/
class Node<T>{
private Object data; //資料
private Node next; //下一節點
Node(Object it, Node nextVal){
this.data=it;
this.next=nextVal;
}
}
private Node front; //隊頭
private Node rear; //隊尾
private int size; //隊列元素個數
/**
* 判空
* @return
*/
public boolean isEmpty() {
return size==0;
}
public int size() {
return size;
}
/**
* 入棧
* @param element
*/
public void enQueue(Object element) {
Node node=new Node(element,null);
//如果隊列為空
if (rear==null){
rear=node;
front=node;
}else{
rear.next=node;
}
size++;
}
/**
* 出隊
* @return
*/
public Object deQueue() {
//隊列為空
if (front==null){
throw new RuntimeException("隊列為空");
}
//隊頭
Node node=front;
front=front.next;
size--;
return node.data;
}
/**
* 取隊頭元素
*/
public Object getHead() {
//隊列為空
if (front==null){
throw new RuntimeException("隊列為空");
}
return front.data;
}
} - 入隊：O(1)
除此之外，順序隊列有變種循環隊列，當rear到達數組的最大下标時，重新指回數組下标為0的位置;
鍊式隊列有雙端隊列，隊頭、隊尾都可以進行入隊、出隊操作的隊列，可以通過雙向連結清單實作；
java中有一個隊列接口java.util.Queue，定義了隊列的一些方法。
它有一個子接口，java.util.Deque，定義了雙端隊列的方法。
LinkedList實作了java.util.Deque接口，是以LinkedList能作為隊列也能作為雙端隊列使用。詳見
LinkedList源碼閱讀筆記。
源碼位址：
https://gitee.com/LaughterYoung/data-structure-learn.git