雙端佇列 Deque
本文同步發布於 2023 iThome 鐵人賽：那些前端不用會，但是可以會的資料結構與演算法 系列文中。
雙端佇列（Double-ended Queue, Deque）是一種允許在前端和後端進行插入和刪除操作的特殊佇列。
以現實生活中來舉例的話，就像是排隊買票，先到的人先買票，後到的人後買票，但如果今天有一個 VIP 會員要買票，他可以直接從對頭插隊進來被服務，不用從最後面開始慢慢排。
還有一個是我們之前在介紹 stack 時有說到 stack 的逆序輸出特性也被應用在儲存撤銷操作，例如我們在文字編輯器中很常使用 ctrl + z 來回到上一個步驟或操作，每次執行動作時我們就把目前的狀態 push 進 stack 然後撤銷時就 pop 出來，但是存在一個問題，如果我們不斷地 push 進去不去做撤銷，那麼存到超過記憶體上限時就會出現 overflow 的問題，因此更好的做法就是使用 deque，我們一樣在輸入文字時將其存入 deque 中，當我們需要撤銷（ctrl + z 還原）時，只需要從佇列的後端刪除最後一個元素即可（就像是 stack），而當儲存的撤銷操作超過一定的數量時，我們可以從佇列的前端刪除最早的元素，這樣就可以限制撤銷操作的數量。也就是說 deque 同時具有 stack 和 queue 的特性。
Deque 的常用方法
和之前一樣我們會先定義一個 Deque 類別來實作，既然它是一個特殊的 queue 那麼我們可以直接沿用部分程式碼：
class Deque {
#items = {};
#headCount = 0;
#count = 0;
isEmpty() {
return this.size() === 0;
}
size() {
return this.#count - this.#headCount;
}
clear() {
this.#items = {};
this.#headCount = 0;
this.#count = 0;
}
toString() {
let str = '';
for (let i = this.#headCount; i < this.#count; i++) {
str += this.#items[i] + (i < this.#count - 1 ? ',' : '');
}
return str;
}
}我們會有下面幾個方法：
addFront(data)：在佇列的前端新增一個元素。addBack(data)：在佇列的後端新增一個元素（和原本的enqueue方法一樣）。removeFront()：刪除佇列的前端元素（和原本的dequeue方法一樣）。removeBack()：刪除佇列的後端元素（跟 stack 的pop方法一樣）。peekFront()：回傳佇列的前端元素（和原本的peek方法一樣）。peekBack()：回傳佇列的後端元素（跟 stack 的peek方法一樣）。
所以我們的 Deque 目前會長這樣：
class Deque {
#items = {};
#headCount = 0;
#count = 0;
addBack(data) {
this.#items[this.#count] = data;
this.#count++;
}
removeFront() {
if (this.isEmpty()) return;
const head = this.#items[this.#headCount];
delete this.#items[this.#headCount];
this.#headCount++;
return head;
}
removeBack() {
if (this.isEmpty()) return;
this.#count--;
const tail = this.#items[this.#count];
delete this.#items[this.#count];
return tail;
}
peekFront() {
return this.#items[this.#headCount];
}
peekBack() {
if (this.isEmpty()) return;
return this.#items[this.#count - 1];
}
isEmpty() {/* 略 */}
size() {/* 略 */}
clear() {/* 略 */}
toString() {/* 略 */}
}addFront 方法
現在讓我們來看 addFront 要怎麼來實作：
addFront(data) {
// #1 if empty
if (this.isEmpty()) {
this.addBack(data);
} else {
// #2 headCount > 0
if (this.#headCount > 0) {
this.#headCount--;
this.#items[this.#headCount] = data;
} else {
// #3 headCount === 0
for (let i = this.#count; i > 0; i--) {
this.#items[i] = this.#items[i - 1];
}
this.#items[0] = data;
this.#count++;
}
}
}有三個情境需要考慮：
第一個是如果目前佇列是空的，那麼我們就可以直接呼叫 addBack 方法。因為 addBack 本身已經處理了 count 的增加，所以我們不需要再處理。
第二個情境是如果 headCount 大於 0，這表示已經有元素被從前端刪除過，所以 headCount 會大於 0，這時候我們只需要將 headCount 減 1，並且在 headCount 的位置新增元素即可。假設目前的佇列內部是：
items = {
1: 15,
2: 32
};
count = 3;
headCount = 1;如果我們要插一個 30 到前端，那麼就會進到這個情境，我們會將 headCount 減 1 變成 0，並且在 key 為 0 的位置填上 30。
第三個情境是如果 headCount 等於 0，我們可以使用負數的 key 來新增元素，然後去更新用來計算佇列長度的邏輯，讓它能夠計算包含負數 key 時的長度。這樣也能夠保持在新增元素時的時間複雜度為 O(1)。但是為了方便理解，我們這邊使用較為簡單的方式來實作，就是把它想像成是陣列，要在第一個位置新增元素時，我們需要將所有元素往後移動一個位置，將第一個位置給空出來。所以我們需要從最後一個元素開始迭代，將 i - 1 賦值給 i，最後再將 0 的位置填上新的元素。
Deque 的應用
Palindrome Checker
回文（Palindrome）是一種正向和反向讀取都相同的單詞、句子或數字的序列，例如：racecar、level。
題目需求是給你一個字串要你判斷它是否為回文，另外如果字元中間有空白的話，例如：never odd or even，我們可以先將空白移除後再判斷是否為回文。
有很多種方法可以判斷一個字串是否為回文，例如最簡單的方式就是將字串反轉後和原本的字串比較，如果相同就表示是回文；也可以使用 stack 來判斷，不過如果要用資料結構來解的話，直接使用剛才封裝好的 Deque 會是最簡單的方法：
function palindromeChecker(str) {
// 移除字串中的空白
const lowerStr = str.toLocaleLowerCase().split(' ').join('');
const deque = new Deque();
for (let i = 0; i < lowerStr.length; i++) {
deque.addBack(lowerStr[i]);
}
while (deque.size() > 1) {
if (deque.removeFront() !== deque.removeBack()) {
return false;
}
}
return true;
}
console.log('level', palindromeChecker('level'));
console.log('Step on no pets', palindromeChecker('Step on no pets'));首先將字串進行處理，將所有字元轉成小寫並且移除空白，接著將字串中的每個字元都加入到 deque 中，最後使用迴圈來判斷 deque 中的第一個元素和最後一個元素是否相同，如果不相同就表示不是回文，如果相同就繼續迴圈，直到 deque 中只剩下一個元素或是沒有元素，這時候就表示是回文。
小結
我們在實作 addFront 方法的第三個情境時模擬了陣列的 shift 方法的行為，所以新增元素到前端的時間複雜度會變成 O(n)，這也給了我們一個提示，陣列固然非常方便，但是在刪除或新增時都會有額外的成本，那麼有沒有一種資料結構可以在刪除或新增時都能夠保持 O(1) 的時間複雜度呢？答案是有的，那就是鏈結串列（Linked List），我會在明天的文章去介紹它。