資訊專欄INFORMATION COLUMN
摘要：我們已經(jīng)學(xué)習(xí)了棧，隊(duì)列和棧非常類似，但是隊(duì)列遵循的是先進(jìn)先出原則的一組有序的項(xiàng)，并從頂部移除元素，但是最新添加的元素必須排在隊(duì)列的末尾。恩，我們的前輩就提出了雙端隊(duì)列，允許用戶在隊(duì)首進(jìn)行添加和刪除元素的操作，隊(duì)尾也是一樣。
我們已經(jīng)學(xué)習(xí)了棧，隊(duì)列和棧非常類似，但是隊(duì)列遵循的是先進(jìn)先出（FIFO）原則的一組有序的項(xiàng)，并從頂部移除元素，但是最新添加的元素必須排在隊(duì)列的末尾。在生活中也有隊(duì)列的應(yīng)用，比如我們在售票處排隊(duì)等票，隊(duì)頭的人先拿到票，就走了，而新來的人，就必須排在隊(duì)偉文明排隊(duì)。
隊(duì)列 創(chuàng)建隊(duì)列class Queue {
constructor() {
this.count = 0;
this.lowestCount = 0;//追蹤隊(duì)列的第一個元素
this.items = {};
}
向隊(duì)列添加元素
enqueue(element) {
this.items[this.count] = element;
this.count++;
}
細(xì)節(jié)就是要注意到隊(duì)列只能在尾部添加元素
檢查隊(duì)列是否為空并獲取它的長度size() {
return this.count - this.lowestCount;
};
isEmpty() {
return this.size() === 0;
};
從隊(duì)列移除元素
dequeue() {
//判斷是否為空
if (this.isEmpty()) {
return undefined;
}
const result = this.items[this.lowestCount];
delete this.items[this.lowestCount];
this.lowestCount++;
return result;
}
查看隊(duì)列頭元素
peek() {
if (this.isEmpty()) {
return undefined;
}
return this.items[this.lowestCount];
}
清空隊(duì)列
clear() {
this.items = {};
this.count = 0;
this.lowestCount = 0;
}
創(chuàng)建toString方法
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;
}
好的，我們的隊(duì)列到此就創(chuàng)建完畢了。但是，有些小伙伴就有疑問了，還是排隊(duì)情景，假如我已經(jīng)離開售票廳了，但是我還想再問些簡單問題，直接到前臺詢問，這就是隊(duì)首添加元素了，還有隊(duì)尾的人突然有事離開了，這也是刪除元素操作呀，那這個用隊(duì)列怎么實(shí)現(xiàn)。恩 ，我們的前輩就提出了雙端隊(duì)列，允許用戶在隊(duì)首進(jìn)行添加和刪除元素的操作，隊(duì)尾也是一樣。
雙端隊(duì)列 創(chuàng)建雙端隊(duì)列class Deque {
constructor() {
this.count = 0;
this.lowestCount = 0;
this.items = {};
}
添加操作
隊(duì)首添加元素
addFront(element) {
if (this.isEmpty()) {//空隊(duì)列
this.addBack(element);
} else if (this.lowestCount > 0) {//之前被刪除，重新添加
this.lowestCount--;
this.items[this.lowestCount] = element;
} else {
for (let i = this.count; i > 0; i--) {
this.items[i] = this.items[i - 1];
}
this.count++;
this.items[0] = element;
}
}
隊(duì)尾添加元素
addBack(element) {
this.items[this.count] = element;
this.count++;
}
刪除操作
隊(duì)首刪除元素
removeFront() {
if (this.isEmpty()) {
return undefined;
}
const result = this.items[this.lowestCount];
delete this.items[this.lowestCount];
this.lowestCount++;
return result;
}
隊(duì)尾刪除元素
removeBack() {
if (this.isEmpty()) {
return undefined;
}
this.count--;
const result = this.items[this.count];
delete this.items[this.count];
return result;
}
查詢操作
返回隊(duì)首元素
peekFront() {
if (this.isEmpty()) {
return undefined;
}
return this.items[this.lowestCount];
}
返回隊(duì)尾元素
peekBack() {
if (this.isEmpty()) {
return undefined;
}
return this.items[this.count - 1];
}
隊(duì)列的實(shí)踐
模擬擊鼓傳花游戲
情景：孩子們圍城一圈，把花傳遞給身邊的人，某一時刻停止，花在誰手上，誰就推出。重復(fù)這個操作，剩下的最后一個人就是勝利者。
代碼實(shí)現(xiàn)：
function hotPotato(elementsList, num) {
const queue = new Queue();
const elimitatedList = [];
for (let i = 0; i < elementsList.length; i++) {
queue.enqueue(elementsList[i]);
}
while (queue.size() > 1) {
for (let i = 0; i < num; i++) {
queue.enqueue(queue.dequeue());
}
elimitatedList.push(queue.dequeue());
}
return {
eliminated: elimitatedList,
winner: queue.dequeue()
};
}
回文檢查器
檢查一個詞組揮著字符串是否為回文。
代碼實(shí)現(xiàn)：
function palindromeChecker(aString) {
if (
aString === undefined
|| aString === null
|| (aString !== null && aString.length === 0)
) {
return false;
}
const deque = new Deque();
const lowerString = aString.toLocaleLowerCase().split(" ").join("");
let firstChar;
let lastChar;
for (let i = 0; i < lowerString.length; i++) {
deque.addBack(lowerString.charAt(i));
}
while (deque.size() > 1) {
firstChar = deque.removeFront();
lastChar = deque.removeBack();
if (firstChar !== lastChar) {
return false;
}
}
return true;
};
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/109968.html
摘要：最小初始化容量。它作為堆棧隊(duì)列雙端隊(duì)列的操作和的操作是一致的，只是內(nèi)部的實(shí)現(xiàn)不同。根據(jù)元素內(nèi)容查找和刪除的效率比較低，為。但是接口有對應(yīng)的并發(fā)實(shí)現(xiàn)類類。 Queue接口的實(shí)現(xiàn)類 Queue接口作為隊(duì)列數(shù)據(jù)結(jié)構(gòu)，java在實(shí)現(xiàn)的時候，直接定義了Deque接口（雙端隊(duì)列）來繼承Queue接口，并且只實(shí)現(xiàn)Deque接口。這樣java中的雙端隊(duì)列就囊括了隊(duì)列、雙端隊(duì)列、堆棧（Deque接口又定...
摘要：定場詩馬瘦毛長蹄子肥，兒子偷爹不算賊，瞎大爺娶個瞎大奶奶，老兩口過了多半輩，誰也沒看見誰前言本章為重讀學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法第三版的系列文章，主要講述隊(duì)列數(shù)據(jù)結(jié)構(gòu)雙端隊(duì)列數(shù)據(jù)結(jié)構(gòu)以及隊(duì)列相關(guān)應(yīng)用。 定場詩 馬瘦毛長蹄子肥，兒子偷爹不算賊，瞎大爺娶個瞎大奶奶，老兩口過了多半輩，誰也沒看見誰！ 前言 本章為重讀《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法-第三版》的系列文章，主要講述隊(duì)列數(shù)據(jù)結(jié)構(gòu)、...
摘要：一同步容器常用的一些容器例如都不是線程安全的，最簡單的將這些容器變?yōu)榫€程安全的方式，是給這些容器所有的方法都加上關(guān)鍵字。為了降低哈希沖突的成本，在鏈表長度超過時，將鏈表轉(zhuǎn)換為紅黑樹。 一、同步容器 常用的一些容器例如 ArrayList、HashMap、都不是線程安全的，最簡單的將這些容器變?yōu)榫€程安全的方式，是給這些容器所有的方法都加上 synchronized 關(guān)鍵字。 Java 的...
摘要：小鹿題目設(shè)計(jì)實(shí)現(xiàn)雙端隊(duì)列。你的實(shí)現(xiàn)需要支持以下操作構(gòu)造函數(shù)雙端隊(duì)列的大小為。獲得雙端隊(duì)列的最后一個元素。檢查雙端隊(duì)列是否為空。數(shù)組頭部刪除第一個數(shù)據(jù)。以上數(shù)組提供的使得更方便的對數(shù)組進(jìn)行操作和模擬其他數(shù)據(jù)結(jié)構(gòu)的操作，棧隊(duì)列等。 Time：2019/4/15Title: Design Circular DequeDifficulty: MediumAuthor: 小鹿 題目：Desi...
摘要：第二步執(zhí)行任務(wù)并合并結(jié)果。使用兩個類來完成以上兩件事情我們要使用框架，必須首先創(chuàng)建一個任務(wù)。用于有返回結(jié)果的任務(wù)。如果任務(wù)順利執(zhí)行完成了，則設(shè)置任務(wù)狀態(tài)為，如果出現(xiàn)異常，則紀(jì)錄異常，并將任務(wù)狀態(tài)設(shè)置為。 1. 什么是Fork/Join框架 Fork/Join框架是Java7提供了的一個用于并行執(zhí)行任務(wù)的框架， 是一個把大任務(wù)分割成若干個小任務(wù)，最終匯總每個小任務(wù)結(jié)果后得到大任務(wù)結(jié)果的...
閱讀 3160·2021-10-08 10:04
閱讀 1102·2021-09-30 09:48
閱讀 3470·2021-09-22 10:53
閱讀 1690·2021-09-10 11:22
閱讀 1702·2021-09-06 15:00
閱讀 2158·2019-08-30 15:56
閱讀 721·2019-08-30 15:53
閱讀 2293·2019-08-30 13:04
