《學習JavaScript數據結構與算法》（下文中簡稱《學》）讀書筆記邑时。
文章首發(fā)于我的博客
棧
棧是一種遵從后進先出（Last In First Out, LIFO）的有序集合。新添加的元素保存在棧的末尾良拼，稱作棧頂设易，另一端叫棧底舟扎。
通俗點講就好像咱進電梯姻锁，后進的人先出來（電梯大了順序亂了啥的別計較）肮雨。
創(chuàng)建棧
創(chuàng)建一個類來表示棧，選擇數組來保存棧里的元素：
function Stack() {
this.items = [];
}
實現一個棧梭稚，通常要實現以下幾種方法：
| 方法 | 功能 |
|---|---|
| push() | 添加一個（或幾個）新元素到棧頂 |
| pop() | 移除棧頂元素颖低，同時返回該元素 |
| peek() | 返回棧頂元素 |
| isEmpty() | 判空 |
| clear() | 清空 |
| size() | 棧里元素個數 |
實現后的代碼：
function Stack() {
this.items = [];
}
Stack.prototype = {
push: function (element) {
this.items.push(element)
},
pop: function () {
return this.items.pop();
},
peek: function () {
return this.items[this.items.length - 1];
},
isEmpty: function () {
return this.items.length === 0;
},
size: function () {
return this.items.length;
},
clear: function () {
this.items = [];
},
print: function () {
console.log(this.items.toString());
}
};
module.exports = Stack;
使用Stack類
我們可以對上面代碼做個測試：
var Stack = require('./Stack');
var stack = new Stack();
console.log(stack.isEmpty()); // true
stack.push(5);
stack.push(8);
console.log(stack.peek());
stack.push(11);
console.log(stack.size()); // 3
console.log(stack.isEmpty()); // false
stack.push(15);
stack.pop();
stack.pop();
console.log(stack.size()); // 2
stack.print(); // 5, 8
下圖描述了我們上面測試代碼的操作（圖片來源：《學》）：
push操作
pop操作
應用示例
十進制轉為其他進制
轉為二進制圖解，其他進制也類似：
十進制=>二進制
代碼實現（使用了ES6語法默認參數弧烤，也可以去掉= 2）：
var Stack = require('./Stack');
function baseConverter(decNumber, base = 2) { // ES6語法忱屑，默認參數
var remStack = new Stack(),
rem,
binaryString = '',
digits = '0123456789ABCDEF';
while (decNumber > 0) {
rem = Math.floor(decNumber % base);
remStack.push(rem);
decNumber = Math.floor(decNumber / base);
}
while (!remStack.isEmpty()) {
binaryString += digits[remStack.pop()];
}
return binaryString;
}
// test
console.log(baseConverter(233));
console.log(baseConverter(10, 8));
console.log(baseConverter(1000, 16));
判斷給定字符串是否是回文
let Stack = require('./Stack');
let isPalindrome = (str) => {
let stack = new Stack();
for (let i = 0; i < str.length; i++) {
stack.push(str[i]);
}
let rstr = '';
while(str.size() > 0) {
rstr += stack.pop();
}
return str === rstr ? true : false;
};
模擬遞歸
// 階乘
function factorial(n) {
n === 0 && return 1;
return n * factorial(n - 1);
}
let Stack = require('./Stack');
let fact = (n) => {
let stack = new Stack();
while (n > 1) {
stack.push(n--);
}
let product = 1;
while (stack.size() > 0) {
product *= stack.pop();
}
return product;
};
隊列
隊列是一種先進先出（First In First Out, FIFO）的有序的數據結構。在尾部添加新元素，并從頂部移除元素莺戒。
創(chuàng)建隊列
創(chuàng)建一個類來表示隊列粱栖，用數組存儲隊列中元素的數據結構：
function Queue() {
this.items = [];
}
實現一個隊列，通常要實現以下幾種方法：
| 方法 | 功能 |
|---|---|
| enqueue() | 向隊列尾部添加一個（或多個）新的項 |
| dequeue() | 移除隊列隊首元素并返回 |
| front() | 返回隊列中第一個元素 |
| isEmpty() | 判空 |
| size() |
實現后的代碼：
function Queue() {
this.items = [];
}
Queue.prototype = {
enqueue: function (element) {
this.items.push(element)
},
dequeue: function () {
return this.items.shift();
},
front: function () {
return this.items[0];
},
isEmpty: function () {
return this.items.length === 0;
},
size: function () {
return this.items.length;
},
clear: function () {
this.items = [];
},
print: function () {
console.log(this.items.toString());
}
};
module.exports = Queue;
使用Queue類
var Queue = require('./Queue');
var queue = new Queue();
console.log(queue.isEmpty());
queue.enqueue('John');
queue.enqueue('Bob');
queue.enqueue('Lily');
queue.print(); // "John", "Bob", "Lily"
console.log(queue.size()); // 3
queue.dequeue();
queue.print(); // "Bob", "Lily"
優(yōu)先隊列
優(yōu)先隊列的添加和移除是基于優(yōu)先級的脏毯。顯示中的例子是頭等艙，再有就是急診室等幔崖。
實現一個優(yōu)先隊列食店，有兩種選項：設置優(yōu)先級，然后在正確的位置添加元素赏寇；或者用入列操作元素吉嫩，然后按照優(yōu)先級移除它們。我們使用第一種方式進行演示：
function PriorityQueue() {
this.items = [];
}
/**
* 要添加到隊列的元素及其在隊列中的優(yōu)先級
* @param {[type]} element
* @param {[number]} priority 優(yōu)先級
*/
function QueueElement(element, priority) {
this.element = element;
this.priority = priority;
}
PriorityQueue.prototype = {
enqueue: function (element, priority) {
var queueElement = new QueueElement(element, priority);
if (this.isEmpty()) {
// 如果隊列為空嗅定，元素直接入列
this.items.push(queueElement);
} else {
var added = false;
for (var i = 0; i < this.items.length; i++) {
if (queueElement.priority < this.items[i].priority) { // 最小優(yōu)先隊列
// 還能保證優(yōu)先級相同時也遵循隊列先進先出的原則
this.items.splice(i, 0, queueElement);
added = true;
break;
}
}
// 要添加元素的priority值大于任何已有的元素自娩，把它添加到隊列的末尾
if (!added) items.push(queueElement);
}
}
// 其他方法和默認的Queue實現相同
};
測試：
var priorityQueue = new PriorityQueue();
priorityQueue.enqueue('John', 2);
priorityQueue.enqueue('Jack', 1);
priorityQueue.enqueue('Camila', 1);
priorityQueue.print();
下圖可以看到上面測試代碼的運行結果（圖片來源：《學》）：
queue
第一個被添加的元素是優(yōu)先級為2的John。因為此前隊列為空渠退，所以它是隊列中唯一的元素忙迁。接下來，添加了優(yōu)先級為1的Jack碎乃。由于Jack的優(yōu)先級高于John姊扔，它就成了隊列中的第一個元素。 然后梅誓， 添加了優(yōu)先級也為1的Camila恰梢。 Camila的優(yōu)先級和Jack相同，所以它會被插入到Jack之后（因為Jack先被插入隊列）梗掰； Camila的優(yōu)先級高于John嵌言，所以它會被插入到John之前。
循環(huán)隊列——擊鼓傳花
擊鼓傳花游戲：人們圍成一個圈及穗，把花盡快傳給旁邊的人摧茴。某一時刻傳花停止，此時花在誰手里誰就退出圓圈結束游戲拥坛。重復此過程蓬蝶，直到只剩一個勝者。
var Queue = require('./Queue');
function hotPotato(nameList, num) {
var queue = new Queue();
for (var i = 0; i < nameList.length; i++) {
// 游戲者全部入隊列
queue.enqueue(nameList[i]);
}
var eliminated = '';
while (queue.size() > 1) {
for (var i = 0; i < num; i++) {
// 從隊列開頭移除一項猜惋，再將其添加到隊列末尾丸氛，模擬擊鼓傳花（如果你把花傳給了旁邊的人，你被淘汰的威脅立刻就解除了）
queue.enqueue(queue.dequeue());
}
// 傳遞次數達到給定數字著摔，此時拿花的人被淘汰
eliminated = queue.dequeue();
console.log(eliminated + '在擊鼓傳花游戲中被淘汰');
}
return queue.dequeue();
}
測試代碼：
var names = ['John', 'Jack', 'Camila', 'Ingrid', 'Carl'];
var winner = hotPotato(names, 7);
console.log('the winner is : ' + winner);
輸出：
Camila在擊鼓傳花游戲中被淘汰
Jack在擊鼓傳花游戲中被淘汰
Carl在擊鼓傳花游戲中被淘汰
Ingrid在擊鼓傳花游戲中被淘汰
the winner is : John
下圖模擬了這個輸出過程（圖片來源：《學》）：
循環(huán)隊列
