堆疊是一種遵從后進先出（LIFO）原則的有序集合， 新添加或待洗掉的元素都保存在堆疊的同一端，稱作堆疊頂，另一端就叫堆疊底，堆疊也被用在編程語言的編譯器和記憶體中保存變數、方法呼叫等，也被用于瀏覽器歷史記錄（瀏覽器的回傳按鈕）
創建一個基于 JavaScript 陣列的 Stack 類
創建一個類來表示堆疊，簡單地從創建一個 stack-array.js 檔案并宣告 Stack 類開始
宣告 Stack 類
class Stack {
constructor() {
this.items = []; // {1}
}
}
向堆疊添加元素
push(element(s)) 添加一個（或幾個）新元素到堆疊頂，
push(element) {
this.items.push(element);
}
從堆疊移除元素
pop() 移除堆疊頂的元素，同時回傳被移除的元素，
pop() {
return this.items.pop();
}
查看堆疊頂元素
peek() 回傳堆疊頂的元素，不對堆疊做任何修改（該方法不會移除堆疊頂的元素，僅僅返它，
peek() {
return this.items[this.items.length - 1];
}
檢查堆疊是否為空
isEmpty() 如果堆疊里沒有任何元素就回傳 true，否則回傳 false，
isEmpty() {
return this.items.length === 0;
}
清空堆疊元素
clear() 移除堆疊里的所有元素，
clear() {
this.items = [];
}
實作堆疊的 length
size() 回傳堆疊里的元素個數，該方法和陣列lengt屬性很類似，
size() {
return this.items.length;
}
完整的Stack類
class Stack {
constructor() {
this.items = []; // {1}
};
push(element) {
this.items.push(element);
};
pop() {
return this.items.pop();
};
peek() {
return this.items[this.items.length - 1];
};
isEmpty() {
return this.items.length === 0;
};
clear() {
this.items = [];
};
size() {
return this.items.length;
}
}
使用 Stack 類
首先需要初始化 Stack 類，然后驗證一下堆疊是否為空
const stack = new Stack();
console.log(stack.isEmpty()); // 輸出為 true
往堆疊里添加一些元素（可以添加任意型別的元素）
stack.push(5);
stack.push(11);
stack.push(8);
如果呼叫 peek 方法，將輸出 8，因為它是往堆疊里添加的最后一個元素，
console.log(stack.peek()); // 輸出 8
console.log(stack.size()); // 輸出 3
console.log(stack.isEmpty()); // 輸出 false
使用基于陣列的堆疊的問題
- 在使用陣列時，大部分方法的時間復雜度是 O(n)
- 陣列是元素的一個有序集合，為了保證元素排列有序，它會占用更多的記憶體空間，
創建一個基于 JavaScript 物件的 Stack 類
對于使用 JavaScript 語言實作堆疊資料結構的場景，也可以使用一個JavaScript 物件來存盤所有的堆疊元素
首先像下面這樣宣告一個 Stack 類（stack.js 檔案），
class Stack {
constructor() {
this.count = 0; //count 屬性記錄堆疊的大小
this.items = {};
}
// 方法
}
向堆疊中插入元素
在 JavaScript 中，物件是一系列鍵值對的集合，要向堆疊中添加元素，可以使用 count 變數作為 items 物件的鍵名，插入的元素則是它的值，在向堆疊插入元素后，遞增 count 變數，
push(element) {
this.items[this.count] = element;
this.count++;
}
驗證一個堆疊是否為空和它的大小
count 屬性也表示堆疊的大小，因此，可以簡單地回傳 count 屬性的值來實作 size 方法，
size() {
return this.count;
}
要驗證堆疊是否為空，可以像下面這樣判斷 count 的值是否為 0，
isEmpty() {
return this.count === 0;
}
從堆疊中彈出元素
由于我們沒有使用陣列來存盤元素，需要手動實作移除元素的邏輯，pop 方法同樣回傳了從堆疊中移除的元素，
pop() {
if (this.isEmpty()) { // {1}
return undefined;
}
this.count--; // {2}
const result = this.items[this.count]; // {3}
delete this.items[this.count]; // {4}
return result; // {5}
}
首先，需要檢驗堆疊是否為空（行{1}），如果為空，就回傳 undefined，如果堆疊不為空的話，將 count 屬性減 1（行{2}），并保存堆疊頂的值（行{3}），以便在洗掉它（行{4}）之后將它回傳（行{5}）
查看堆疊頂的值并將堆疊清空
要訪問堆疊頂元素，需要將 count 屬性減 1，
peek() {
if (this.isEmpty()) {
return undefined;
}
return this.items[this.count - 1];
}
要清空該堆疊，只需要將它的值復原為建構式中使用的值即可，
clear() {
this.items = {};
this.count = 0;
}
也可以遵循 LIFO 原則，使用下面的邏輯來移除堆疊中所有的元素，
while (!this.isEmpty()) {
this.pop();
}
創建 toString 方法
在陣列版本中，不需要關心 toString 方法的實作，因為資料結構可以直接使用陣列已經提供的 toString 方法，對于使用物件的版本，需要創建一個 toString 方法來像陣列一樣列印出堆疊的內容，
toString() {
if (this.isEmpty()) {
return '';
}
let objString = `${this.items[0]}`; // {1}
for (let i = 1; i < this.count; i++) { // {2}
objString = `${objString},${this.items[i]}`; // {3}
}
return objString;
}
如果堆疊是空的，只需回傳一個空字串即可，如果它不是空的，就需要用它底部的第一個元素作為字串的初始值（行{1}），然后迭代整個堆疊的鍵（行{2}），一直到堆疊頂，添加一個逗號（,）以及下一個元素（行{3}），如果堆疊只包含一個元素，行{2}和行{3}的代碼將不會執行，
實作了 toString 方法后，就完成了這個版本的 Stack 類，
class Stack {
constructor() {
this.count = 0; //count 屬性記錄堆疊的大小
this.items = {};
}
// 方法
push(element) {
this.items[this.count] = element;
this.count++;
};
pop() {
if (this.isEmpty()) { // {1}
return undefined;
}
this.count--; // {2}
const result = this.items[this.count]; // {3}
delete this.items[this.count]; // {4}
return result; // {5}
};
peek() {
if (this.isEmpty()) {
return undefined;
}
return this.items[this.count - 1];
};
clear() {
this.items = {};
this.count = 0;
};
toString() {
if (this.isEmpty()) {
return '';
}
let objString = `${this.items[0]}`; // {1}
for (let i = 1; i < this.count; i++) { // {2}
objString = `${objString},${this.items[i]}`; // {3}
}
return objString;
}
}
這也是一個用不同方式寫代碼的例子，兩者都提供了相同的功能，只是內部實作很不一樣，
保護資料結構內部元素
在創建別的開發者也可以使用的資料結構或物件時，我們希望保護內部的元素，只有我們暴露出的方法才能修改內部結構，對于 Stack 類來說，要確保元素只會被添加到堆疊頂，而不是堆疊底或其他任意位置（比如堆疊的中間），不幸的是，我們在 Stack 類中宣告的 items 和 count 屬性并沒有得到保護，因為 JavaScript 的類就是這樣作業的，
試著執行下面的代碼，
const stack = new Stack();
console.log(Object.getOwnPropertyNames(stack)); // {1}
console.log(Object.keys(stack)); // {2}
console.log(stack.items); // {3}
行{1}和行{2}的輸出結果是[“count”, “items”]，這表示 count 和 items 屬性是公開的，我們可以像行{3}那樣直接訪問它們，根據這種行為，我們可以對這兩個屬性賦新的值，
ES2015（ES6）語法創建了 Stack 類，ES2015 類是基于原型的，盡管基于原型的類能節省記憶體空間并在擴展方面優于基于函式的類，但這種方式不能宣告私有屬性（變數）或方法，另外，我們希望 Stack 類的用戶只能訪問我們在類中暴露的方法，
使用 JavaScript 來實作私有屬性的方法，
下劃線命名約定
一部分開發者喜歡在 JavaScript 中使用下劃線命名約定來標記一個屬性為私有屬性，
class Stack {
constructor() {
this._count = 0;
this._items = {};
}
下劃線命名約定就是在屬性名稱之前加上一個下劃線（_），不過這種方式只是一種約定，并不能保護資料，而且只能依賴于使用我們代碼的開發者所具備的常識，
用 ES2015 的限定作用域 Symbol 實作類
ES2015 新增了一種叫作 Symbol 的基本型別，它是不可變的，可以用作物件的屬性，看看怎么用它在 Stack 類中宣告 items 屬性（我們將使用陣列來存盤元素以簡化代碼），
const _items = Symbol('stackItems'); // {1}
class Stack {
constructor () {
this[_items] = []; // {2}
}
//堆疊的方法
}
在上面的代碼中宣告了 Symbol 型別的變數_items（行{1}），在類的 constructor 函式中初始化它的值（行{2}），要訪問_items，只需要把所有的 this.items 都換成 this[_items] ，
這種方法創建了一個假的私有屬性，因為 ES2015 新增的 Object.getOwnPropertySymbols方法能夠取到類里面宣告的所有 Symbols 屬性，下面是一個破壞 Stack 類的例子，
const stack = new Stack();
stack.push(5);
stack.push(8);
let objectSymbols = Object.getOwnPropertySymbols(stack);
console.log(objectSymbols.length); // 輸出 1
console.log(objectSymbols); // [Symbol()]
console.log(objectSymbols[0]); // Symbol()
stack[objectSymbols[0]].push(1);
stack.print(); // 輸出 5, 8, 1
從以上代碼可以看到，訪問 stack[objectSymbols[0]] 是可以得到_items 的，并且，_items 屬性是一個陣列，可以進行任意的陣列操作，比如從中間洗掉或添加元素（使用物件進行存盤也是一樣的），但我們操作的是堆疊，不應該出現這種行為，
用 ES2015 的 WeakMap 實作類
有一種資料型別可以確保屬性是私有的，這就是 WeakMap，WeakMap 可以存盤鍵值對，其中鍵是物件，值可以是任意資料型別，如果用 WeakMap 來存盤 items 屬性（陣列版本），Stack 類就是這樣的：
const items = new WeakMap(); // {1}
class Stack {
constructor() {
items.set(this, []); // {2}
}
push(element) {
const s = items.get(this); // {3}
s.push(element);
}
pop() {
const s = items.get(this);
const r = s.pop();
return r;
}
// 其他方法
}
上面的代碼片段解釋如下，
行{ 1 } ，宣告一個 WeakMap 型別的變數 items，
行{ 2 } ，在 constructor 中，以 this（Stack 類自己的參考）為鍵，把代表堆疊的陣列存入 items，
行{ 3 } ，從 WeakMap 中取出值，即以 this 為鍵（行{ 2 } 設定的）從 items 中取值，
現在我們知道了，items 在 Stack 類里是真正的私有屬性，采用這種方法，代碼的可讀性不強，而且在擴展該類時無法繼承私有屬性，魚和熊掌不可兼得
用堆疊解決問題
如何解決十進制轉二進制問題，以及任意進制轉換的演算法?
要把十進制轉化成二進制，我們可以將該十進制數除以 2（二進制是滿二進一）并對商取整，直到結果是 0 為止，
function decimalToBinary(decNumber) {
const remStack = new Stack();
let number = decNumber;
let rem;
let binaryString = '';
while (number > 0) { // {1}
rem = Math.floor(number % 2); // {2}
remStack.push(rem); // {3}
number = Math.floor(number / 2); // {4}
}
while (!remStack.isEmpty()) { // {5}
binaryString += remStack.pop().toString();
}
return binaryString;
}
在這段代碼里，當除法的結果不為 0 時（行{1}），會獲得一個余數，并放到堆疊里（行{2}、行{3}），然后讓結果繼續除以 2（行{4}），另外請注意：JavaScript 有數值型別，但是它不會區分整數和浮點數，因此，要使用 Math.floor函式僅回傳除法運算結果的整數部分，最后，用 pop 方法把堆疊中的元素都移除，把出堆疊的元素連接成字串（行{5}），
測驗:
console.log(decimalToBinary(233)); // 11101001
console.log(decimalToBinary(10)); // 1010
console.log(decimalToBinary(1000)); // 1111101000
進制轉換演算法
可以修改之前的演算法，使之能把十進制轉換成基數為 2～36 的任意進制，除了把十進制數除以 2 轉成二進制數，還可以傳入其他任意進制的基數為引數，就像下面的演算法這樣，
function baseConverter(decNumber, base) {
const remStack = new Stack();
const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'; // {6}
let number = decNumber;
let rem;
let baseString = '';
if (!(base >= 2 && base <= 36)) {
return '';
}
while (number > 0) {
rem = Math.floor(number % base);
remStack.push(rem);
number = Math.floor(number / base);
}
while (!remStack.isEmpty()) {
baseString += digits[remStack.pop()]; // {7}
}
return baseString;
}
只需要改變一個地方，在將十進制轉成二進制時，余數是 0 或 1；在將十進制轉成八進制時，余數是 0～7；但是將十進制轉成十六進制時，余數是 0～9 加上 A、B、C、D、E 和 F（對應 10、11、12、13、14 和 15），因此，需要對堆疊中的數字做個轉化才可以（行{6}和行{7}），因此，從十一進制開始，字母表中的每個字母將表示相應的基數，字母 A 代表基數 11，B 代表基數 12，以此類推，
測驗
console.log(baseConverter(100345, 2)); // 11000011111111001
console.log(baseConverter(100345, 8)); // 303771
console.log(baseConverter(100345, 16)); // 187F9
console.log(baseConverter(100345, 35)); // 2BW0
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/290294.html
標籤：其他
上一篇：仿小米輪播
下一篇：js常見面試題（一）