隊列和雙端隊列
我們前面學習了棧數(shù)據(jù)結(jié)構(gòu), 隊列數(shù)據(jù)結(jié)構(gòu)和棧很相似, 區(qū)別是隊列屬于先進先出的數(shù)據(jù)結(jié)構(gòu), 雙端隊列是一種將棧的原則和隊列的原則混合在一起的數(shù)據(jù)結(jié)構(gòu)
隊列數(shù)據(jù)結(jié)構(gòu)
隊列是遵循先進先出（FIFO巴帮，也稱為先來先服務(wù)）原則的一組有序的項, 隊列在尾部添加新元素，并從頂部移除元素罢绽。最新添加的元素必須排在隊列的末尾, 類似于 '排隊'
- 如何創(chuàng)建一個隊列? 以及聲明一些隊列可用的方法
-
enqueue(element):向隊列尾部添加一個(或多個)新的項 -
dequeue():移除隊列的第一項, 并返回被移除的元素 -
peek():返回隊列的第一個元素-最先被添加, 也將是最先被移除的元素. 隊列不做變動. 該方法在其他語言也可以叫front方法 -
isEmpty():如果隊列中不包含任何元素, 返回 true, 否則返回 false -
size():返回隊列包含的元素個數(shù)
-
class Queue {
constructor() {
this.count = 0;
this.lowestCount = 0;
this.items = {}; // 使用對象來存儲我們的元素
}
// enqueue 方法和 Stack 類中 push 方法的實現(xiàn)方式相同
enqueue(element) {
this.items[this.count] = element;
this.count++;
}
/**
* items: {0: 1, 1: 8}
* 鍵為0 獲取隊列頭部的值, 刪除它, 再返回它的值, 刪除后, 變?yōu)?items: {1: 8}
* 再次執(zhí)行 dequeue 方法, lowestCount 0 -> 1
*/
dequeue() {
if (this.isEmpty()) return undefined;
const result = this.items[this.lowestCount]; // 如果隊列不為空, 暫存隊列頭部的值
delete this.items[this.lowestCount]; // 刪除隊列刪除元素
this.lowestCount++;
return result;
}
// 查看隊列頭部元素
peek() {
if (this.isEmpty()) return undefined;
return this.items[this.lowestCount];
}
/**
* 假設(shè) count 2, lowestCount 為 0, 表示隊列有兩個元素
* 移除一個元素, lowestCount -> 1 count 還是 2, 隊列只有一個元素了
*
*/
// 計算隊列有多少元素, 計算 count 和 lowestCount 之間的差值
isEmpty() {
return this.count - this.lowestCount === 0;
}
size() {
return this.count - this.lowestCount;
}
clear() {
this.count = 0;
this.lowestCount = 0;
this.items = {};
}
toString() {
if (this.isEmpty()) return "";
let objString = `${this.items[this.lowestCount]}`; // 第一個元素的值
for (let i = this.lowestCount + 1; i < this.count; i++) {
objString = `${objString},${this.items[i]}`;
}
return objString;
}
}
module.exports = Queue;
雙端隊列數(shù)據(jù)結(jié)構(gòu)
雙端隊列(deque, 或稱 double-ended queue) 是一種允許我們同事從前端和后端添加和移除元素的特殊隊列
雙端隊列在現(xiàn)實生活中的例子有電影院、餐廳中排隊的隊伍等苔悦。舉個例子或链，一個剛買了票的人如果只是還需要再問一些簡單的信息，就可以直接回到隊伍的頭部。另外吊宋，在隊伍末尾的人如果趕時間，他可以直接離開隊伍
- 和之前一樣, 聲明一個
Deque類及其構(gòu)造函數(shù), 包括相同的內(nèi)部屬性和以下方法：isEmpty颜武、clear璃搜、size 和 toString。 由于雙端隊列允許在兩端添加和移除元素鳞上，還會有下面幾個方法?-
addFront(element):該方法在雙端隊列前端添加新的元素 -
addBack(element):該方法在雙端隊列后端添加新的元素（實現(xiàn)方法和 Queue 類中的 enqueue 方法相同） -
removeFront():該方法會從雙端隊列前端移除第一個元素（實現(xiàn)方法和 Queue 類中的 dequeue 方法相同） -
removeBack():該方法會從雙端隊列后端移除第一個元素（實現(xiàn)方法和 Stack 類中的 pop 方法一樣） -
peekFront():該方法返回雙端隊列前端的第一個元素（實現(xiàn)方法和 Queue 類中的 peek 方法一樣） -
peekBack():該方法返回雙端隊列后端的第一個元素（實現(xiàn)方法和 Stack 類中的 peek 方法一樣）
-
class Deque {
constructor() {
this.count = 0;
this.lowestCount = 0;
this.items = {};
}
addFront(element) {
// 第一種情況: 如果雙端隊列是空的, 執(zhí)行 addBack 方法
if (this.isEmpty()) {
this.addBack(element);
/**
* 第二種情況:
* 一個元素已經(jīng)被從雙端隊列的前端移除, 也就是說 lowestCount 屬性會大于等于 1,
* 這種情況下这吻，我們只需要將 lowestCount 屬性減 1 并將新元素的值放在這個鍵的位置上即可
* 實例: items = {1: 8, 2: 9} count = 0; lowestCount = 1
* 想將元素7添加到雙端隊列的前端: -> lowestCount = 0; items[0] = 7
*/
} else if (this.lowestCount > 0) {
this.lowestCount--;
this.items[this.lowestCount] = element;
/**
* 第三種情況: 最后一種場景是 lowestCount 為 0 的情況
* 可以設(shè)置一個負值的鍵，同時更新用于計算雙端隊列長度的邏輯篙议，使其也能包含負鍵值
*
* 我們把本場景看作使用數(shù)組唾糯。要在第一位添加一個新元素，我們需要將所有元素后移一位（行{1}）來空出第一個位置。由于我們不想丟失任何已
* 有的值移怯，需要從最后一位開始迭代所有的值香璃，并為元素賦上索引值減 1 位置的值。在所有的元素都完成移動后芋酌，第一位將是空閑狀態(tài)增显，這樣就可以用需要添加的新元素來覆蓋它了{4}
*/
} else {
// {1} {0: 1, 1: 3}
for (let i = this.count; i > 0; i--) {
this.items[i] = this.items[i - 1];
}
this.count++;
this.lowestCount = 0;
this.items[0] = element; // {4}
}
}
addBack(element) {
this.items[this.count] = element;
this.count++;
}
removeFront() {
if (this.isEmpty()) return undefined;
const result = this.items[this.lowestCount]; // 如果隊列不為空, 暫存隊列頭部的值
delete this.items[this.lowestCount]; // 刪除隊列刪除元素
this.lowestCount++;
return result;
}
removeBack() {
if (this.isEmpty()) return undefined;
this.count--;
const result = this.items[this.count];
delete this.items[this.count];
return result;
}
peekFront() {
if (this.isEmpty()) return undefined;
return this.items[this.lowestCount];
}
peekBack() {
if (this.isEmpty()) return undefined;
return this.items[this.count];
}
isEmpty() {
return this.count - this.lowestCount === 0;
}
size() {
return this.count - this.lowestCount;
}
clear() {
this.count = 0;
this.lowestCount = 0;
this.items = {};
}
toString() {
if (this.isEmpty()) return "";
let objString = `${this.items[this.lowestCount]}`; // 第一個元素的值
for (let i = this.lowestCount + 1; i < this.count; i++) {
objString = `${objString},${this.items[i]}`;
}
return objString;
}
}
module.exports = Deque;
使用雙端隊列解決問題
使用隊列來模擬擊鼓傳花游戲，并使用雙端隊列來檢查一個短語是否為回文
- 循環(huán)隊列 --- 擊鼓傳花問題
const Queue = require("./queue");
function hotPotato(elementList, num) {
const queue = new Queue();
const elimitatedList = [];
// 會得到一份名單, 把里面的名字加入隊列
for (let i = 0; i < elementList.length; i++) {
queue.enqueue(elementList[i]);
}
// 給定一個數(shù)字, 然后迭代隊列. 從隊列開頭移除一項, 再將其添加到隊列末尾
while (queue.size() > 1) {
for (let i = 0; i < num; i++) {
queue.enqueue(queue.dequeue());
}
// 模擬擊鼓傳花（如果你把花傳給了旁邊的人脐帝，你被淘汰的威脅就立刻解除了）同云。一旦達到給定的傳遞次數(shù)，拿著花的那個人就被淘汰了（從隊列中移除
elimitatedList.push(queue.dequeue());
}
// 最后只剩下一個人的時候堵腹，這個人就是勝者
return {
eliminated: elimitatedList,
winner: queue.dequeue(),
};
}
const names = ["John", "Jack", "Camila", "Ingrid", "Carl"];
const result = hotPotato(names, 7);
result.eliminated.forEach((name) => {
console.log(`${name}在擊鼓傳花游戲中被淘汰炸站。`);
});
console.log(`勝利者： ${result.winner}`);
擊鼓傳花
- 回文檢查器
回文是正反都能讀通的單詞、詞組疚顷、數(shù)或一系列字符的序列旱易，例如 madam 或 racecar
下面的算法使用了一個雙端隊列來解決問題
const Deque = require("./Deque");
const palindromeChecker = (aString) => {
// 檢查傳入的字符串參數(shù)是否合法
if (
aString === undefined ||
aString === null ||
(aString !== null && aString.length === 0)
) {
return false;
}
const deque = new Deque();
const lowerString = aString.toLocaleLowerCase().split(" ").join(""); // 對字符串進行處理
let isEqual = true;
let firstChar, lastChar;
for (let i = 0; i < lowerString.length; i++) {
// 對字符串中的所有字符執(zhí)行 enqueue 操作
deque.addBack(lowerString.charAt(i));
}
// 如果所有元素都在雙端隊列中（如果只有一個字符的話，那它肯定是回文）并且首尾字符相同的話
while (deque.size() > 1 && isEqual) {
firstChar = deque.removeFront(); // 從前端移除一個元素
lastChar = deque.removeBack(); // 再從后端移除一個元素
// 要使字符串為回文腿堤，移除的兩個字符必須相同阀坏。如果字符不同的話，這個字符串就不是一個回文
if (firstChar !== lastChar) {
isEqual = false;
}
}
return isEqual;
};
