大部分記錄均來自小灰漫畫算法

· 區(qū)分物理結(jié)構(gòu)和邏輯結(jié)構(gòu)

物理結(jié)構(gòu)和邏輯結(jié)構(gòu).png

· 什么是棧
棧是一種線性數(shù)據(jù)結(jié)構(gòu)；棧中的元素只能先入后出。實(shí)現(xiàn)：Stack和LinkedStack

棧.png

· 什么是隊(duì)列
隊(duì)列是一種線性數(shù)據(jù)結(jié)構(gòu)，隊(duì)列中的元素只能先入先出。隊(duì)列的出口端叫對頭，隊(duì)列的入口端叫隊(duì)尾。
為了避免隊(duì)列的空間維持恒定：
在數(shù)組不擴(kuò)容的前提下，利用已出隊(duì)元素留下的空間，讓隊(duì)尾指針重新指揮數(shù)組的首位。一直到隊(duì)尾下標(biāo)+1 % 數(shù)組長度 = 對頭下標(biāo)。需要注意的是，這種做法需要隊(duì)尾指針指向的位置永遠(yuǎn)空出1位，所以隊(duì)列最大容量比數(shù)組長度小1。
public class MyQueue {

//恒定數(shù)組
private int [] array;
//隊(duì)頭
private int front;
//隊(duì)尾
private int end;

public MyQueue(int capacity) {
    this.array = new int[capacity];
}

public int deQueue() throws Exception {
    if(end == front) {
        throw new Exception("隊(duì)列以空");
    }
    int deQueueElement = array[front];
    front = (front + 1) % array.length;
    return deQueueElement;
}

public void enQueue(int element) throws Exception{
    if((end + 1) % array.length == front) {
        throw new Exception("隊(duì)列已滿");
    }
    array[end] = element;
    end = (end + 1) % array.length;
}

}

· 各自的應(yīng)用
棧通常用于對“歷史”的回溯。
隊(duì)列通常用于對“歷史”的回放。重現(xiàn)之前的操作步驟。

雙端隊(duì)列同時實(shí)現(xiàn)了棧和隊(duì)列的優(yōu)點(diǎn)。