作者：同夢(mèng)奇緣 https://segmentfault.com/a/1190000017905515
寫在前面原計(jì)劃是把《你不知道的Javascript》三部全部看完的，偶然間朋友推薦了數(shù)據(jù)結(jié)構(gòu)與算法的一套入門視頻，學(xué)之。發(fā)現(xiàn)數(shù)據(jù)結(jié)構(gòu)并沒有想象中那么遙不可及，反而發(fā)覺挺有意思的。手頭上恰好有《學(xué)習(xí)Javascript數(shù)據(jù)結(jié)構(gòu)與算法》的書籍，便轉(zhuǎn)而先把數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)。 一、認(rèn)識(shí)數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)？下面是維基百科的解釋： 數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)意味著接口或封裝：一個(gè)數(shù)據(jù)結(jié)構(gòu)可被視為兩個(gè)函數(shù)之間的接口，或者是由數(shù)據(jù)類型聯(lián)合組成的存儲(chǔ)內(nèi)容的訪問方法封裝
我們每天的編碼中都會(huì)用到數(shù)據(jù)結(jié)構(gòu)，因?yàn)?strong>數(shù)組是最簡(jiǎn)單的內(nèi)存數(shù)據(jù)結(jié)構(gòu)，下面是常見的數(shù)據(jù)結(jié)構(gòu)： 數(shù)組（Array） 棧（Stack） 隊(duì)列（Queue） 鏈表（Linked List） 樹（Tree） 圖（Graph） 堆（Heap） 散列表（Hash）
下面來學(xué)習(xí)學(xué)習(xí)棧和隊(duì)列。 二、棧2.1 棧數(shù)據(jù)結(jié)構(gòu)棧是一種遵循后進(jìn)先出（LIFO）原則的有序集合。新添加的或待刪除的元素都保存在棧的同一端，稱作棧頂，另一端就叫棧底。在棧里，新元素都接近棧頂，舊元素都接近棧底。
類比生活中的物件：一摞書??或者推放在一起的盤子。 2.2 棧的實(shí)現(xiàn)普通的棧常用的有以下幾個(gè)方法： push 添加一個(gè)（或幾個(gè)）新元素到棧頂
pop 溢出棧頂元素，同時(shí)返回被移除的元素
peek 返回棧頂元素，不對(duì)棧做修改
isEmpty 棧內(nèi)無元素返回 true，否則返回 false
size 返回棧內(nèi)元素個(gè)數(shù)
clear 清空棧
class Stack {
constructor() {
this._items = []; // 儲(chǔ)存數(shù)據(jù)
}
// 向棧內(nèi)壓入一個(gè)元素
push(item) {
this._items.push(item);
}
// 把棧頂元素彈出
pop() {
return this._items.pop();
}
// 返回棧頂元素
peek() {
return this._items[this._items.length - 1];
}
// 判斷棧是否為空
isEmpty() {
return !this._items.length;
}
// 棧元素個(gè)數(shù)
size() {
return this._items.length;
}
// 清空棧
clear() {
this._items = [];
}
}
現(xiàn)在再回頭想想數(shù)據(jù)結(jié)構(gòu)里面的棧是什么。 突然發(fā)現(xiàn)并沒有那么神奇，僅僅只是對(duì)原有數(shù)據(jù)進(jìn)行了一次封裝而已。而封裝的結(jié)果是：并不去關(guān)心其內(nèi)部的元素是什么，只是去操作棧頂元素，這樣的話，在編碼中會(huì)更可控一些。 2.3 棧的應(yīng)用（1）十進(jìn)制轉(zhuǎn)任意進(jìn)制 要求：給定一個(gè)函數(shù)，輸入目標(biāo)數(shù)值和進(jìn)制基數(shù)，輸出對(duì)應(yīng)的進(jìn)制數(shù)（最大為16進(jìn)制）。 baseConverter(10, 2) ==> 1010
baseConverter(30, 16) ==> 1E
分析：進(jìn)制轉(zhuǎn)換的本質(zhì)——將目標(biāo)值一次一次除以進(jìn)制基數(shù)，得到的取整值為新目標(biāo)值，記錄下余數(shù)，直到目標(biāo)值小于0，最后將余數(shù)逆序組合即可。利用棧，記錄余數(shù)入棧，組合時(shí)出棧。 // 進(jìn)制轉(zhuǎn)換
function baseConverter(delNumber, base) {
const stack = new Stack();
let rem = null;
let ret = [];
// 十六進(jìn)制中需要依次對(duì)應(yīng)A~F
const digits = '0123456789ABCDEF';
while (delNumber > 0) {
rem = Math.floor(delNumber % base);
stack.push(rem);
delNumber = Math.floor(delNumber / base);
}
while (!stack.isEmpty()) {
ret.push(digits[stack.pop()]);
}
return ret.join('');
}
console.log(baseConverter(100345, 2)); //輸出11000011111111001
console.log(baseConverter(100345, 8)); //輸出303771
console.log(baseConverter(100345, 16)); //輸出187F9
（2）逆波蘭表達(dá)式計(jì)算 要求： 逆波蘭表達(dá)式，也叫后綴表達(dá)式，它將復(fù)雜表達(dá)式轉(zhuǎn)換為可以依靠簡(jiǎn)單的操作得到計(jì)算結(jié)果的表達(dá)式，例如 (a+b)*(c+d)轉(zhuǎn)換為 a b+c d+* ['4', '13', '5', '/', '+'] ==> (4 + (13 / 5)) = 6
['10', '6', '9', '3', '+', '-11', '*', '/', '*', '17', '+', '5', '+']
==> ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
分析： 以符號(hào)為觸發(fā)節(jié)點(diǎn)，一旦遇到符號(hào)，就將符號(hào)前兩個(gè)元素按照該符號(hào)運(yùn)算，并將新的結(jié)果入棧，直到棧內(nèi)僅一個(gè)元素 function isOperator(str) {
return ['+', '-', '*', '/'].includes(str);
}
// 逆波蘭表達(dá)式計(jì)算
function clacExp(exp) {
const stack = new Stack();
for (let i = 0; i < exp.length; i++) {
const one = exp[i];
if (isOperator(one)) {
const operatNum1 = stack.pop();
const operatNum2 = stack.pop();
const expStr = `${operatNum2}${one}${operatNum1}`;
const res = eval(expStr);
stack.push(res);
} else {
stack.push(one);
}
}
return stack.peek();
}
console.log(clacExp(['4', '13', '5', '/', '+'])); // 6.6
（3）利用普通棧實(shí)現(xiàn)一個(gè)有 min方法的棧 思路： 使用兩個(gè)棧來存儲(chǔ)數(shù)據(jù)，其中一個(gè)命名為 dataStack，專門用來存儲(chǔ)數(shù)據(jù)，另一個(gè)命名為 minStack，專門用來存儲(chǔ)棧里最小的數(shù)據(jù)。始終保持兩個(gè)棧中的元素個(gè)數(shù)相同，壓棧時(shí)判別壓入的元素與 minStack棧頂元素比較大小，如果比棧頂元素小，則直接入棧，否則復(fù)制棧頂元素入棧；彈出棧頂時(shí)，兩者均彈出即可。這樣 minStack的棧頂元素始終為最小值。 class MinStack {
constructor() {
this._dataStack = new Stack();
this._minStack = new Stack();
}
push(item) {
this._dataStack.push(item);
// 為空或入棧元素小于棧頂元素，直接壓入該元素
if (this._minStack.isEmpty() || this._minStack.peek() > item) {
this._minStack.push(item);
} else {
this._minStack.push(this._minStack.peek());
}
}
pop() {
this._dataStack.pop();
return this._minStack.pop();
}
min() {
return this._minStack.peek();
}
}
const minstack = new MinStack();
minstack.push(3);
minstack.push(4);
minstack.push(8);
console.log(minstack.min()); // 3
minstack.push(2);
console.log(minstack.min()); // 2
三、隊(duì)列3.1 隊(duì)列數(shù)據(jù)結(jié)構(gòu)隊(duì)列是遵循先進(jìn)先出（FIFO，也稱為先來先服務(wù)）原則的一組有序的項(xiàng)。隊(duì)列在尾部添加新元素，并從頂部移除元素。最新添加的元素必須排在隊(duì)列的末尾。
類比：日常生活中的購物排隊(duì)。 3.2 隊(duì)列的實(shí)現(xiàn)普通的隊(duì)列常用的有以下幾個(gè)方法： enqueue 向隊(duì)列尾部添加一個(gè)(或多個(gè))新的項(xiàng)
dequeue 移除隊(duì)列的第一(即排在隊(duì)列最前面的)項(xiàng)，并返回被移除的元素
head 返回隊(duì)列第一個(gè)元素，隊(duì)列不做任何變動(dòng)
tail 返回隊(duì)列最后一個(gè)元素，隊(duì)列不做任何變動(dòng)
isEmpty 隊(duì)列內(nèi)無元素返回 true，否則返回 false
size 返回隊(duì)列內(nèi)元素個(gè)數(shù)
clear 清空隊(duì)列
class Queue {
constructor() {
this._items = [];
}
enqueue(item) {
this._items.push(item);
}
dequeue() {
return this._items.shift();
}
head() {
return this._items[0];
}
tail() {
return this._items[this._items.length - 1];
}
isEmpty() {
return !this._items.length;
}
size() {
return this._items.length;
}
clear() {
this._items = [];
}
}
與棧類比，棧僅能操作其頭部，隊(duì)列則首尾均能操作，但僅能在頭部出尾部進(jìn)。當(dāng)然，也印證了上面的話：棧和隊(duì)列并不關(guān)心其內(nèi)部元素細(xì)節(jié)，也無法直接操作非首尾元素。 3.3 隊(duì)列的應(yīng)用（1）約瑟夫環(huán)（普通模式） 要求： 有一個(gè)數(shù)組 a[100]存放0~99；要求每隔兩個(gè)數(shù)刪掉一個(gè)數(shù)，到末尾時(shí)循環(huán)至開頭繼續(xù)進(jìn)行，求最后一個(gè)被刪掉的數(shù)。 分析： 按數(shù)組創(chuàng)建隊(duì)列，依次判斷元素是否滿足為指定位置的數(shù)，如果不是則 enqueue到尾部，否則忽略，當(dāng)僅有一個(gè)元素時(shí)便輸出。 // 創(chuàng)建一個(gè)長(zhǎng)度為100的數(shù)組
const arr_100 = Array.from({ length: 100 }, (_, i) => i*i);
function delRing(list) {
const queue = new Queue();
list.forEach(e => { queue.enqueue(e); });
let index = 0;
while (queue.size() !== 1) {
const item = queue.dequeue();
index += 1;
if (index % 3 !== 0) {
queue.enqueue(item);
}
}
return queue.tail();
}
console.log(delRing(arr_100)); // 8100 此時(shí)index=297
（2）菲波那切數(shù)列（普通模式） 要求： 使用隊(duì)列計(jì)算斐波那契數(shù)列的第n項(xiàng)。 分析： 斐波那契數(shù)列的前兩項(xiàng)固定為1，后面的項(xiàng)為前兩項(xiàng)之和，依次向后，這便是斐波那契數(shù)列。 function fibonacci(n) {
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(1);
let index = 0;
while(index < n - 2) {
index += 1;
// 出隊(duì)列一個(gè)元素
const delItem = queue.dequeue();
// 獲取頭部值
const headItem = queue.head();
const nextItem = delItem + headItem;
queue.enqueue(nextItem);
}
return queue.tail();
}
console.log(fibonacci(9)); // 34
（3）用隊(duì)列實(shí)現(xiàn)一個(gè)棧 要求： 用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧。 分析： 使用隊(duì)列實(shí)現(xiàn)棧最主要的是在隊(duì)列中找到棧頂元素并對(duì)其操作。具體的思路如下： 兩個(gè)隊(duì)列，一個(gè)備份隊(duì)列 emptyQueue，一個(gè)是數(shù)據(jù)隊(duì)列 dataQueue； 在確認(rèn)棧頂時(shí)，依次 dequeue至備份隊(duì)列，置換備份隊(duì)列和數(shù)據(jù)隊(duì)列的引用即可。
class QueueStack {
constructor() {
this.queue_1 = new Queue();
this.queue_2 = new Queue();
this._dataQueue = null; // 放數(shù)據(jù)的隊(duì)列
this._emptyQueue = null; // 空隊(duì)列,備份使用
}
// 確認(rèn)哪個(gè)隊(duì)列放數(shù)據(jù),哪個(gè)隊(duì)列做備份空隊(duì)列
_initQueue() {
if (this.queue_1.isEmpty() && this.queue_2.isEmpty()) {
this._dataQueue = this.queue_1;
this._emptyQueue = this.queue_2;
} else if (this.queue_1.isEmpty()) {
this._dataQueue = this.queue_2;
this._emptyQueue = this.queue_1;
} else {
this._dataQueue = this.queue_1;
this._emptyQueue = this.queue_2;
}
};
push(item) {
this.init_queue();
this._dataQueue.enqueue(item);
};
peek() {
this.init_queue();
return this._dataQueue.tail();
}
pop() {
this.init_queue();
while (this._dataQueue.size() > 1) {
this._emptyQueue.enqueue(this._dataQueue.dequeue());
}
return this._dataQueue.dequeue();
};
};
同樣的，一個(gè)隊(duì)列也能實(shí)現(xiàn)棧的基本功能： class QueueStack {
constructor() {
this.queue = new Queue();
}
push(item) {
this.queue.enqueue(item);
}
pop() {
// 向隊(duì)列末尾追加 隊(duì)列長(zhǎng)度-1 次，后彈出隊(duì)列頭部
for(let i = 1; i < this.queue.size(); i += 1) {
this.queue.enqueue(this.queue.dequeue());
}
return this.queue.dequeue();
}
peek() {
return this.queue.tail();
}
}
學(xué)習(xí)了棧和隊(duì)列這類簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，我們會(huì)發(fā)現(xiàn)。數(shù)據(jù)結(jié)構(gòu)并沒有之前想象中那么神秘，它們只是規(guī)定了這類數(shù)據(jù)結(jié)構(gòu)的操作方式：棧只能對(duì)棧頂進(jìn)行操作，隊(duì)列只能在尾部添加在頭部彈出；且它們不關(guān)心內(nèi)部的元素狀態(tài)。 個(gè)人認(rèn)為，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)是為了提高我們通過代碼建模的能力，這也是任何一門編程語言都通用的知識(shí)體系，優(yōu)秀編碼者必學(xué)之。
分享前端好文，缺個(gè) 在看 
|
