數(shù)據(jù)結(jié)構(gòu)和算法動(dòng)態(tài)可視化網(wǎng)站

一玛瘸、隊(duì)列 Queue

隊(duì)列是一種特殊的線性表，只能在頭尾兩端進(jìn)行操作砰琢；

隊(duì)尾（rear）：只能從隊(duì)尾添加元素魁索，一般叫做 enQueue，入隊(duì)
隊(duì)頭（front）：只能從隊(duì)頭移除元素炬灭，一般叫做 deQueue，出隊(duì)
先進(jìn)先出的原則靡菇，First In First Out重归，F(xiàn)IFO

image.png

隊(duì)列的內(nèi)部實(shí)現(xiàn)可以使用動(dòng)態(tài)數(shù)組或雙向鏈表實(shí)現(xiàn)，優(yōu)先使用雙向鏈表厦凤，因?yàn)殛?duì)列主要是往頭尾操作元素鼻吮。

二、隊(duì)列的接口設(shè)計(jì)

public class Queue<E> {
    // 使用雙向鏈表實(shí)現(xiàn)隊(duì)列
    private List<E> list = new LinkedList<>();
    // 元素的數(shù)量
    public int size();
    // 是否為空
    public boolean isEmpty();
    // 入隊(duì)
    public void enQueue(E element);
    // 出隊(duì)
    public E deQueue();
    // 獲取隊(duì)列的頭元素
    public E front();
}

三较鼓、隊(duì)列的實(shí)現(xiàn)

public class Queue <E>{
    private List<E> list = new LinkedList<>();
    public void enQueue(E element){
        list.add(element);
    }
    public E deQueue(){
        return list.remove(0);
    }
    public int size(){
        return list.size();
    }
    public void clear(){
        list.clear();
    }
    public E top(){
        return list.get(0);
    }
    public boolean isEmpty(){
        return list.isEmpty();
    }
}

四椎木、雙端隊(duì)列 （Deque）

雙端隊(duì)列是能在頭尾兩端添加、刪除的隊(duì)列博烂；
英文 deque是 double ended queue 的簡(jiǎn)稱

雙端隊(duì)列接口設(shè)計(jì)

int size(); // 元素的數(shù)量
boolean isEmpty(); // 是否為空
void clear(); // 清空
void enQueueRear(E element); // 從隊(duì)尾入隊(duì)
E deQueueFront(); // 從隊(duì)頭出隊(duì)
void enQueueFront(E element); // 從隊(duì)頭入隊(duì)
E deQueueRear(); // 從隊(duì)尾出隊(duì)
E front(); // 獲取隊(duì)列的頭元素
E rear(); // 獲取隊(duì)列的尾元素

雙端隊(duì)列實(shí)現(xiàn)

public class Deque<E> {
    private List<E> list = new LinkedList<>();
    
    // 元素的數(shù)量
    public int size() {
        return list.size();
    }
    // 是否為空
    public boolean isEmpty() {
        return list.isEmpty();
    }
    // 從隊(duì)頭出隊(duì)
    public E deQueueFront() {
        return list.remove(0);
    }
    // 從隊(duì)頭入隊(duì)
    public void enQueueFront(E element) {
        list.add(0, element);
    }
    // 從隊(duì)尾入隊(duì)
    public void enQueueRear(E element) {
        list.add(element);
    }
    // 從隊(duì)尾出隊(duì)
    public E deQueueRear() {
        return list.remove(list.size() - 1);
    }
    // 獲取隊(duì)列的頭元素
    public E front() {
        return list.get(0);
    }
    // 獲取隊(duì)列的尾元素
    public E rear() {
        return list.get(list.size() - 1);
    }
}

五香椎、循環(huán)隊(duì)列

隊(duì)列內(nèi)部實(shí)現(xiàn)也可以用動(dòng)態(tài)數(shù)組實(shí)現(xiàn)，并且將各項(xiàng)接口優(yōu)化到O(1)的時(shí)間復(fù)雜度禽篱， 這個(gè)用數(shù)組實(shí)現(xiàn)并優(yōu)化之后的隊(duì)列就叫做: 循環(huán)隊(duì)列畜伐。

image.png

• 使用一個(gè)索引變量front控制第0個(gè)元素所在位置。
• 每一次出棧躺率，就將front位置的元素取出并刪除玛界，然后front向后+1万矾。
• 每一次入棧，都根據(jù)front和當(dāng)前元素?cái)?shù)量計(jì)算出入棧元素應(yīng)該存入的索引慎框，然后將元素存入到數(shù)組對(duì)應(yīng)索引的位置上勤众。

循環(huán)隊(duì)列的接口設(shè)計(jì)

public class CircleQueue<E> {
    // 記錄第0個(gè)元素的索引
    private int front;
    // 當(dāng)前隊(duì)列存儲(chǔ)的元素個(gè)數(shù)
    private int size;
    // 用來(lái)存儲(chǔ)元素的數(shù)組
    private E[] elements;
    // 當(dāng)前隊(duì)列存儲(chǔ)的元素?cái)?shù)量
    public int size();
    // 當(dāng)前隊(duì)列是否為空
    public boolean isEmpty();
    // 入隊(duì)
    public void enQueue(E element);
    // 出隊(duì)
    public E deQueue();
    // 查看索引為0的元素
    public E front();
}

循環(huán)隊(duì)列的實(shí)現(xiàn)

1、構(gòu)造方法

public class ArrayList<E> {
    private E[] elements;
    // 設(shè)置elements數(shù)組默認(rèn)的初始化空間
    private static final int DEFAULT_CAPACITY = 10;
    
    public CircleQueue() {
        elements = (E[]) new Object[DEFAULT_CAPACITY];
    }
}

2鲤脏、入隊(duì)

• 入隊(duì)前需要考慮兩個(gè)問(wèn)題：隊(duì)列是否需要擴(kuò)容和計(jì)算入隊(duì)實(shí)際索引们颜。

擴(kuò)容相關(guān)內(nèi)容請(qǐng)閱讀《動(dòng)態(tài)數(shù)組》一章

• 擴(kuò)容后front 需要重置為0

image.png

private void ensureCapacity(int capacity) {
    int oldCapacity = elements.length;
    if (oldCapacity >= capacity) return;
        
    // 新容量為舊容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1); //位運(yùn)算
    E[] newElements = (E[]) new Object[newCapacity];
    for (int i = 0; i < size; i++) {
        newElements[i] = elements[index(i)];
    }
    elements = newElements;
        
    // 重置front
    front = 0;
}

3、索引計(jì)算

• 預(yù)期入隊(duì)索引 = 第0個(gè)元素索引 + 當(dāng)前隊(duì)列元素個(gè)數(shù)猎醇。
• 如果預(yù)期入隊(duì)索引大于等于數(shù)組長(zhǎng)度窥突，實(shí)際入隊(duì)索引 = 預(yù)期入隊(duì)索引 - 數(shù)組長(zhǎng)度。
• 如果預(yù)期入隊(duì)索引小于數(shù)組長(zhǎng)度硫嘶，實(shí)際入隊(duì)索引 = 預(yù)期入隊(duì)索引阻问。

// 索引計(jì)算
private int index(int index) {
    index += front;
    return index - (index >= elements.length ? elements.length : 0);
}

// 入隊(duì)的代碼
public void enQueue(E element) {
    // 數(shù)組擴(kuò)容判斷
    ensureCapacity(size + 1);
    // 索引計(jì)算，并賦值
    elements[index(size)] = element;
    // size加一
    size++;
}

4沦疾、出隊(duì)

出隊(duì)后需要更新front

public E deQueue() {
    // 獲取出隊(duì)元素
    E frontElement = elements[front];
    // 將索引位置致空
    elements[front] = null;
    // 更新font
    front = index(1);
    // size減一
    size--;
    // 返回出隊(duì)元素
    return frontElement;
}