1. 棧資料結構
- 棧是類似于數組的資料結構，在添加和删除元素時更為可控。
- 遵從後進先出（LIFO）原則的有序組合。
- 新添加或待删除的元素儲存在棧頂。
- 棧可被用在程式設計語言的編譯器和記憶體中儲存變量、方法調用等，也被用于浏覽器曆史記錄（浏覽器傳回按鈕）。
JavaScript資料結構與算法 - 棧1. 棧資料結構2. 建立一個基于JavaScript對象的Stack類3. 保護資料結構内部元素4. 将十進制轉換為二進制5. 進制轉換算法
1.1 建立一個基于 數組
數組
建立一個類來表示棧：
class Stack {
constructor() {
this.items = []; // 可以選擇數組來儲存棧裡的元素
};
// 方法
}
為棧聲明一些方法：
- push(element(s))：添加一個（或幾個）新元素到棧頂
- pop()：移除棧頂的元素，同時傳回被移除的元素
- peek()：傳回棧頂的元素，不對棧做任何修改
- isEmpty()：如果棧裡沒有任何元素就傳回true，否則傳回false
- clear()：移除棧裡所有元素
- size()：傳回棧裡的元素個數
1.2 向棧添加元素
隻添加元素到棧頂，即棧的末尾。
可以同時向Stack類中添加多個元素。
push(element) {
this.items.push(element);
}
1.3 從棧移除元素
移除的是最後添加進去的元素。
pop() {
return this.items.pop();
}
1.4 檢視棧頂元素
// 因為類内部是用數組儲存的，是以通路數組的最後一個元素可以用 length - 1
peek() {
return this.items[this.items.length - 1];
}
1.5 檢查棧是否為空
isEmpty() {
// 簡單判斷内部數組的長度是否為0
return this.items.length === 0;
}
1.6 棧的大小
類似數組的length屬性，我們也能實作棧的length。
對于集合，棧最好用size代替length。因為棧的内部使用數組儲存元素，是以能簡單地傳回棧的長度。
size() {
retutn this.items.length;
}
1.7 清空棧元素
clear() {
this.items = [];
}
也可以用多次pop方法，把數組元素全部移除。
1.8 使用Stack類
<script>
class Stack {
constructor() {
this.items = [];
};
// 聲明方法
// 添加元素
push(element) {
return this.items.push(element);
};
// 移除元素
pop() {
return this.items.pop();
};
// 檢視棧頂元素
peek() {
return this.items[this.items.length - 1];
};
// 判斷棧是否為空
isEmpty() {
return this.items.length === 0;
};
// 棧的長度
size() {
return this.items.length;
};
// 清空棧元素
clear() {
this.items = [];
};
}
// 先初始化類
const stack = new Stack();
// 檢驗棧是否為空
console.log(stack.isEmpty()); // true
// 往棧中添加元素
stack.push(10);
stack.push(20);
console.log(stack); // [10, 20]
console.log(stack.isEmpty()); // false
// 檢視棧頂元素
console.log(stack.peek()); // 20
stack.push(30); // [10, 20, 30]
// 檢視棧的長度
console.log(stack.size()); // 3
// 移除棧頂元素
stack.pop();
console.log(stack.size()); // 2
</script>
- 使用數組時，大部分方法時間複雜度為O(n)
- 數組是元素的一個有序集合，為了保證元素排列有序，它會占用更多的記憶體空間
2. 建立一個基于JavaScript 對象
對象
先聲明一個Stack類：
class Stack {
constructor() {
this.count = 0; // 記錄棧的大小
this.items = {};
};
// 方法
}
2.1 向棧中插入元素
對象的版本不同于數組版本，隻允許一次插入一個元素。
push(element) {
this.items[this.count] = element;
this.count++;
}
在JavaScript中，對象是一系列鍵值對的集合。
是以向棧中添加元素時，将使用count變量作為items對象的鍵名，插入的元素是它的值。
使用：
const stack = new Stack();
stack.push(10);
stack.push(20);
2.2 驗證一個棧是否為空
可以直接判斷count是否為0。
isEmpty() {
return this.count === 0;
}
2.3 棧的大小
可以簡單傳回count屬性的值來實作size。
size() {
return this.count;
}
2.4 從棧中彈出元素
pop() {
// 先檢驗棧是否為空
if (this.isEmpty()) {
return undefined;
}
this.count--;
// 儲存棧頂的值，以便在删除後将它傳回
const result = this.items[this.count];
delete this.items[this.count];
return result;
}
使用：
2.5 檢視棧頂的值
peek() {
if(this.isEmpty()) {
return undefined;
}
return this.items[this.count - 1];
}
2.6 清空棧元素
clear() {
this.items = {};
this..count = 0;
}
也可以遵循後進先出原則使用pop方法删除
while(!this.isEmpty()) {
this.pop();
}
2.7 建立toString方法
數組版本中，可以直接使用數組已經提供的toString方法。
對象版本，需要建立一個toString方法來像數組一樣列印出棧的内容。
toString() {
// 如果棧為空，傳回一個空字元串
if (this.isEmpty()) {
return ''
}
// 用底部的第一個元素作為字元串的初始值
let objString = `${this.items[0]}`;
// 如果隻有1個元素，循環不執行
// 疊代整個棧的健，直到棧頂
for (let i = 1; i < this.count; i++) {
// 添加一個逗号以及下一個元素
objString = `${objString}, ${this.items[i]}`;
}
return objString;
}
3. 保護資料結構内部元素
希望Stack類的使用者隻能通路我們在類中暴露的方法。
3.1 下劃線命名約定
部分開發者喜歡在JavaScript中使用下劃線命名約定一個屬性為私有屬性。
class Stack {
constructor() {
this._count = 0;
this._items = {};
}
}
這種方式隻是一種約定，并不能保護資料，隻能依賴于開發者所具備的常識。
3.2 用限定作用域 Symbol
Symbol
ES2015新增了Symbol的基本類型，它是不可變的，可以用作對象的屬性。
// 聲明了Symbol類型的變量_items
const _items = Symbol('stackItems');
class Stack {
// 初始化_items的值
constructor() {
this[_items] = [];
}
// 棧的方法
}
要通路_items，隻需要把所有的this.items換成this.[_items]
這種方法創造了一個假的私有屬性，因為Object.getOwnPropertySymbol方法能夠取到類裡面聲明的所有Symbol屬性。
一個破壞Stack類的例子：
const stack = new Stack();
stack.push(10);
stack.push(20);
let objectSymbols = Object.getOwnPropertySymbols(stack);
console.log(objectSymbols.length); // 1
console.log(objectSymbols); // [Symbol()]
console.log(objectSymbols[0]); // Symbol()
stack[objectSymbols[0]].push(1); // 10,20,1
stack.print();
上面的代碼可以通路到_items，并且_items屬性是一個數組，可以進行任意的數組操作。但我們操作的是棧，不應該出現這種行為。
3.3 WeakMap
WeakMap
- WeakMap可以確定屬性是私有的
- 可以存儲鍵值對，其中鍵是對象，值是可以任意資料類型
// 聲明一個WeakMap類型的變量items
const items = new WeakMap();
class Stack {
constructor() {
// 以this為鍵，把代表棧的數組存入items
items.set(this, []);
}
push(element) {
// 以this為鍵從items中取值
const s = items.get(this);
const r = s.pop();
return r;
}
// 其他方法
}
但是采用這種方法，代碼可讀性不強，而且在擴充該類時無法繼承私有屬性。
4. 将十進制轉換為二進制
<script>
class Stack {
constructor() {
this.items = [];
};
// 聲明方法
// 添加元素
push(element) {
return this.items.push(element);
};
// 移除元素
pop() {
return this.items.pop();
};
// 檢視棧頂元素
peek() {
return this.items[this.items.length - 1];
};
// 判斷棧是否為空
isEmpty() {
return this.items.length === 0;
};
// 棧的長度
size() {
return this.items.length;
};
// 清空棧元素
clear() {
this.items = [];
};
};
function decimalToBinary(decNumber) {
const remStack = new Stack();
let number = decNumber;
let rem;
let binaryString = '';
while (number > 0) {
rem = Math.floor(number % 2);
remStack.push(rem);
number = Math.floor(number / 2);
}
while (!remStack.isEmpty()) {
// 把出棧的元素連接配接成字元串
binaryString += remStack.pop().toString();
}
return binaryString;
}
console.log(decimalToBinary(10)); // 1010
</script>
5. 進制轉換算法
<script>
class Stack {
constructor() {
this.items = [];
};
// 聲明方法
// 添加元素
push(element) {
return this.items.push(element);
};
// 移除元素
pop() {
return this.items.pop();
};
// 檢視棧頂元素
peek() {
return this.items[this.items.length - 1];
};
// 判斷棧是否為空
isEmpty() {
return this.items.length === 0;
};
// 棧的長度
size() {
return this.items.length;
};
// 清空棧元素
clear() {
this.items = [];
};
};
function baseConverter(decNumber, base) {
const remStack = new Stack();
// 從十一進制開始，字母表中的字母将代表相應基數
const digits = '0123456789ABCDEFGHIJKLMNOPQRETUVWXYZ';
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()];
}
return baseString;
}
console.log(baseConverter(167, 16)); // A7
</script>