(注釋：整篇數(shù)據(jù)結(jié)構(gòu)與算法文集窝撵，部分總結(jié)于王爭的《數(shù)據(jù)結(jié)構(gòu)與算法之美》和李明杰的《戀上數(shù)據(jù)結(jié)構(gòu)與算法》，加上自己的理解丹喻，所以出了這個(gè)文集薄货，僅做個(gè)人筆記記錄所用。如你需要驻啤，請購買他們的正版資源菲驴，支持他們的原創(chuàng))
隊(duì)列是一種特殊的線性表，只能在頭尾兩端進(jìn)行操作
- 隊(duì)尾(rear):只能從隊(duì)尾添加元素骑冗，一般叫做 enQueue赊瞬，入隊(duì)
- 隊(duì)頭(front):只能從隊(duì)頭移除元素，一般叫做 deQueue贼涩，出隊(duì)
- 先進(jìn)先出的原則巧涧，F(xiàn)irst In First Out，F(xiàn)IFO
隊(duì)列接口的設(shè)計(jì)
- int size(); // 元素的數(shù)量
- boolean isEmpty(); // 是否為空
- void clear(); // 清空
- void enQueue(E element); // 入隊(duì)
- E deQueue(); // 出隊(duì)
- E front(); // 獲取隊(duì)列的頭元素
隊(duì)列的內(nèi)部實(shí)現(xiàn)是否可以直接利用以前學(xué)過的數(shù)據(jù)結(jié)構(gòu)?
動態(tài)數(shù)組遥倦、鏈表
優(yōu)先使用雙向鏈表谤绳，因?yàn)殛?duì)列主要是往頭尾操作元素
用棧來實(shí)現(xiàn)隊(duì)列
https://leetcode-cn.com/problems/implement-queue-using-stacks/
雙端隊(duì)列
雙端隊(duì)列是能在頭尾兩端添加、刪除的隊(duì)列
-英文 deque 是 double ended queue 的簡稱
雙端隊(duì)列接口的設(shè)計(jì) (可用鏈表來便捷的 實(shí)現(xiàn)雙端隊(duì)列)
-int size(); // 元素的數(shù)量
-boolean isE mpty(); // 是否為空
-void clear(); // 清空
-void enQueueRear(E element);// 從隊(duì)尾入隊(duì)
-E deQueueRear(); // 從隊(duì)尾出隊(duì)
-void enQueueFront(E element); // 從隊(duì)頭入隊(duì)
-E deQueueFront(); // 從隊(duì)頭出隊(duì)
-E front(); // 獲取隊(duì)列的頭元素
-E rear(); // 獲取隊(duì)列的尾元素
用數(shù)組來實(shí)現(xiàn)隊(duì)列
// 用數(shù)組實(shí)現(xiàn)的隊(duì)列
public class ArrayQueue {
// 數(shù)組：items袒哥，數(shù)組大兴跎浮：n
private String[] items;
private int n = 0;
// head表示隊(duì)頭下標(biāo)，tail表示隊(duì)尾下標(biāo)
private int head = 0;
private int tail = 0;
// 申請一個(gè)大小為capacity的數(shù)組
public ArrayQueue(int capacity) {
items = new String[capacity];
n = capacity;
}
// 入隊(duì)
public boolean enqueue(String item) {
// 如果tail == n 表示隊(duì)列已經(jīng)滿了
if (tail == n) return false;
items[tail] = item;
++tail;
return true;
}
// 出隊(duì)
public String dequeue() {
// 如果head == tail 表示隊(duì)列為空
if (head == tail) return null;
// 為了讓其他語言的同學(xué)看的更加明確堡称，把--操作放到單獨(dú)一行來寫了
String ret = items[head];
++head;
return ret;
}
}
當(dāng) a却紧、b、c、d 依次入隊(duì)之后，隊(duì)列中的 head 指針指向下標(biāo)為 0 的位置冠王，tail 指針指向下標(biāo)為 4 的位置豪娜。
當(dāng)我們調(diào)用兩次出隊(duì)操作之后，隊(duì)列中 head 指針指向下標(biāo)為 2 的位置，tail 指針仍然指向下標(biāo)為 4 的位置。
你肯定已經(jīng)發(fā)現(xiàn)了恐锣，隨著不停地進(jìn)行入隊(duì)、出隊(duì)操作，head 和 tail 都會持續(xù)往后移動。當(dāng) tail 移動到最右邊，即使數(shù)組中還有空閑空間，也無法繼續(xù)往隊(duì)列中添加數(shù)據(jù)了。這個(gè)問題該如何解決呢褒纲？
// 入隊(duì)操作读宙，將item放入隊(duì)尾
public boolean enqueue(String item) {
// tail == n表示隊(duì)列末尾沒有空間了
if (tail == n) {
// tail ==n && head==0膀估，表示整個(gè)隊(duì)列都占滿了
if (head == 0) return false;
// 數(shù)據(jù)搬移
for (int i = head; i < tail; ++i) {
items[i-head] = items[i];
}
// 搬移完之后重新更新head和tail
tail -= head;
head = 0;
}
items[tail] = item;
++tail;
return true;
}
從代碼中我們看到饼记，當(dāng)隊(duì)列的 tail 指針移動到數(shù)組的最右邊后，如果有新的數(shù)據(jù)入隊(duì)匪凡，我們可以將 head 到 tail 之間的數(shù)據(jù)衬衬，整體搬移到數(shù)組中 0 到 tail-head 的位置奸远。
這只是數(shù)組實(shí)現(xiàn)隊(duì)列的其中一種的解法讽挟。之后空間還不足的話就需要動態(tài)擴(kuò)容或者使用循環(huán)隊(duì)列等等技術(shù)了懒叛。
循環(huán)隊(duì)列 (可以理解為循環(huán)利用的隊(duì)列)
以下內(nèi)容為王爭的授課內(nèi)容，采用數(shù)組耽梅，輔以雙指針的方式薛窥，先來看看雙指針方式實(shí)現(xiàn)循環(huán)隊(duì)列。
我們剛才用數(shù)組來實(shí)現(xiàn)隊(duì)列的時(shí)候眼姐，在 tail==n 時(shí)诅迷，會有數(shù)據(jù)搬移操作，這樣入隊(duì)操作性能就會受到影響众旗。那有沒有辦法能夠避免數(shù)據(jù)搬移呢罢杉？
我們來看看循環(huán)隊(duì)列的解決思路。循環(huán)隊(duì)列贡歧，顧名思義滩租，它長得像一個(gè)環(huán)。原本數(shù)組是有頭有尾的利朵，是一條直線÷上耄現(xiàn)在我們把首尾相連，扳成了一個(gè)環(huán)绍弟。我畫了一張圖技即，你可以直觀地感受一下。
我們可以發(fā)現(xiàn)樟遣，圖中這個(gè)隊(duì)列的大小為 8而叼，當(dāng)前 head=4，tail=7豹悬。當(dāng)有一個(gè)新的元素 a 入隊(duì)時(shí)葵陵，我們放入下標(biāo)為 7 的位置。但這個(gè)時(shí)候屿衅，我們并不把 tail 更新為 8埃难，而是將其在環(huán)中后移一位，到下標(biāo)為 0 的位置涤久。當(dāng)再有一個(gè)元素 b 入隊(duì)時(shí)涡尘，我們將 b 放入下標(biāo)為 0 的位置，然后 tail 加 1 更新為 1响迂。所以考抄，在 a，b 依次入隊(duì)之后蔗彤，循環(huán)隊(duì)列中的元素就變成了下面的樣子：
通過這樣的方法川梅，我們成功避免了數(shù)據(jù)搬移操作疯兼。看起來不難理解贫途，但是循環(huán)隊(duì)列的代碼實(shí)現(xiàn)難度要比前面講的非循環(huán)隊(duì)列難多了吧彪。要想寫出沒有 bug 的循環(huán)隊(duì)列的實(shí)現(xiàn)代碼，我個(gè)人覺得丢早，最關(guān)鍵的是姨裸，確定好隊(duì)空和隊(duì)滿的判定條件。
在用數(shù)組實(shí)現(xiàn)的非循環(huán)隊(duì)列中怨酝，隊(duì)滿的判斷條件是 tail == n傀缩，隊(duì)空的判斷條件是 head == tail。那針對循環(huán)隊(duì)列农猬，如何判斷隊(duì)空和隊(duì)滿呢赡艰？
隊(duì)列為空的判斷條件仍然是 head == tail。但隊(duì)列滿的判斷條件就稍微有點(diǎn)復(fù)雜了斤葱。我畫了一張隊(duì)列滿的圖慷垮，你可以看一下，試著總結(jié)一下規(guī)律苦掘。
就像我圖中畫的隊(duì)滿的情況换帜，tail=3，head=4鹤啡，n=8惯驼，所以總結(jié)一下規(guī)律就是：(3+1)%8=4。多畫幾張隊(duì)滿的圖递瑰，你就會發(fā)現(xiàn)祟牲，當(dāng)隊(duì)滿時(shí)，(tail+1)%n=head抖部。
你有沒有發(fā)現(xiàn)说贝，當(dāng)隊(duì)列滿時(shí)，圖中的 tail 指向的位置實(shí)際上是沒有存儲數(shù)據(jù)的慎颗。所以乡恕，循環(huán)隊(duì)列會浪費(fèi)一個(gè)數(shù)組的存儲空間。(為什么要浪費(fèi)一個(gè)數(shù)組的存儲空間俯萎，我的理解是這樣的傲宜，其實(shí)主要問題就是為了能夠很好的判斷隊(duì)滿的條件是什么？如果不浪費(fèi)一個(gè)數(shù)組空間夫啊，可能需要引入其他變量函卒，去記錄隊(duì)列的實(shí)際容量，也是需要額外的內(nèi)存空間撇眯，那如果浪費(fèi)了一個(gè)數(shù)組空間报嵌，可以在不需要引入額外的變量的情況下虱咧，給出隊(duì)滿的判斷條件。)
public class CircularQueue {
// 數(shù)組：items锚国，數(shù)組大型笱病：n
private String[] items;
private int n = 0;
// head表示隊(duì)頭下標(biāo)，tail表示隊(duì)尾下標(biāo)
private int head = 0;
private int tail = 0;
// 申請一個(gè)大小為capacity的數(shù)組
public CircularQueue(int capacity) {
items = new String[capacity];
n = capacity;
}
// 入隊(duì)
public boolean enqueue(String item) {
// 隊(duì)列滿了
if ((tail + 1) % n == head) return false;
items[tail] = item;
tail = (tail + 1) % n;
return true;
}
// 出隊(duì)
public String dequeue() {
// 如果head == tail 表示隊(duì)列為空
if (head == tail) return null;
String ret = items[head];
head = (head + 1) % n;
return ret;
}
}
下面是MJ使用數(shù)組輔以單指針的方式跷叉，來實(shí)現(xiàn)循環(huán)隊(duì)列逸雹。 (單指針是省略了尾指針，使用 (front+size)%length的方式求出最后一個(gè)要添加的位置云挟，其實(shí)也就等同于上面的尾指針了。其實(shí)頭指針也容易越界转质，所以也要取模操作front = (front + 1)%length )园欣。下面代碼實(shí)現(xiàn)循環(huán)隊(duì)列的同時(shí)做了動態(tài)擴(kuò)容。
package com.mj.circle;
@SuppressWarnings("unchecked")
public class CircleQueue<E> {
private int front;
private int size;
private E[] elements;
private static final int DEFAULT_CAPACITY = 10;
public CircleQueue() {
elements = (E[]) new Object[DEFAULT_CAPACITY];
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void clear() {
for (int i = 0; i < size; i++) {
elements[index(i)] = null;
}
front = 0;
size = 0;
}
public void enQueue(E element) {
//入隊(duì)前先判斷容量夠不夠存休蟹，size是當(dāng)前容量沸枯，size + 1就是需要看看有沒有額外一個(gè)容量，有的話才能add
ensureCapacity(size + 1);
// element[(front+size)%elements.length] = element;
elements[index(size)] = element;
size++;
}
public E deQueue() {
E frontElement = elements[front];
elements[front] = null;
//front = (front + 1)%length ;
front = index(1);
size--;
return frontElement;
}
public E front() {
return elements[front];
}
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("capcacity=").append(elements.length)
.append(" size=").append(size)
.append(" front=").append(front)
.append(", [");
for (int i = 0; i < elements.length; i++) {
if (i != 0) {
string.append(", ");
}
string.append(elements[i]);
}
string.append("]");
return string.toString();
}
//因?yàn)閹滋幍胤蕉加玫搅?*+front)%elements.length赂弓，所以把這個(gè)提出來绑榴，需要的地方直接把*傳進(jìn)來。
private int index(int index) {
return (front + index)%elements.length;
//index += front;
//return index - (index >= elements.length ? elements.length : 0);
}
/**
* 保證要有capacity的容量
* @param capacity
*/
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (oldCapacity >= capacity) return;
// 新容量為舊容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
//擴(kuò)容時(shí)數(shù)據(jù)搬遷不是單純的的0元素放0元素盈魁，而是front元素放在新的數(shù)組0的位置翔怎，依次放入。
//newElements[i] = elements[(i+front)%elements.length];
newElements[i] = elements[index(i)];
}
elements = newElements;
// 重置front
front = 0;
}
}
循環(huán)雙端隊(duì)列(此處使用了數(shù)組來實(shí)現(xiàn)循環(huán)雙端隊(duì)列杨耙。因?yàn)槿绻面湵硖^于 簡單)
循環(huán)雙端隊(duì)列相比上面的循環(huán)隊(duì)列赤套，特別需要注意的是在頭部入隊(duì)的問題。其實(shí)頭部坐標(biāo)也很好解決珊膜。如果0的位置有值的話容握，依舊往頭部入隊(duì)，其實(shí)是要入到整個(gè)數(shù)組的最后一個(gè)元素處车柠，如果front-1的話就變成-1了剔氏，此時(shí)如果-1+length的話就是需要入隊(duì)的頭部位置了
package com.mj.circle;
@SuppressWarnings("unchecked")
public class CircleDeque<E> {
private int front;
private int size;
private E[] elements;
private static final int DEFAULT_CAPACITY = 10;
public CircleDeque() {
elements = (E[]) new Object[DEFAULT_CAPACITY];
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public void clear() {
for (int i = 0; i < size; i++) {
elements[index(i)] = null;
}
front = 0;
size = 0;
}
/**
* 從尾部入隊(duì)
* @param element
*/
public void enQueueRear(E element) {
ensureCapacity(size + 1);
elements[index(size)] = element;
size++;
}
/**
* 從頭部出隊(duì)
* @param element
*/
public E deQueueFront() {
E frontElement = elements[front];
elements[front] = null;
front = index(1);
size--;
return frontElement;
}
/**
* 從頭部入隊(duì)
* @param element
*/
public void enQueueFront(E element) {
ensureCapacity(size + 1);
front = index(-1);
elements[front] = element;
size++;
}
/**
* 從尾部出隊(duì)
* @param element
*/
public E deQueueRear() {
int rearIndex = index(size - 1);
E rear = elements[rearIndex];
elements[rearIndex] = null;
size--;
return rear;
}
public E front() {
return elements[front];
}
public E rear() {
return elements[index(size - 1)];
}
@Override
public String toString() {
StringBuilder string = new StringBuilder();
string.append("capcacity=").append(elements.length)
.append(" size=").append(size)
.append(" front=").append(front)
.append(", [");
for (int i = 0; i < elements.length; i++) {
if (i != 0) {
string.append(", ");
}
string.append(elements[i]);
}
string.append("]");
return string.toString();
}
private int index(int index) {
//先讓front和index相加，看看是不是負(fù)數(shù)竹祷。如果是負(fù)數(shù)就說明是從頭部入隊(duì)谈跛，此時(shí)加上整個(gè)數(shù)組長度就可得到入隊(duì)坐標(biāo)。如果是正數(shù)溶褪，就按著之前的取模币旧。
index += front;
if (index < 0) {
return index + elements.length;
}
return index % elements.length;
//上面的那句取模運(yùn)算可以優(yōu)化
/**
n = 11 (坐標(biāo))
m = 10 (數(shù)組長度)
在此處n限定于小于2m的情況下
if(n>=m){
return n-m;
}else {
return n;
}
所以可以總結(jié)為下面這句
return index - (index >= elements.length ? elements.length : 0);
*/
}
/**
* 保證要有capacity的容量
* @param capacity
*/
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (oldCapacity >= capacity) return;
// 新容量為舊容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[index(i)];
}
elements = newElements;
// 重置front
front = 0;
}
}
