棧（stack）是一種常見的數(shù)據(jù)結(jié)構(gòu)，它是遵循后進(jìn)先出的有序集合惕稻，(LIFO)蔗衡，生活中書桌上堆放的書本纤虽，餐桌上疊起來的盤子，都是典型的棧的形象绞惦。
使用JS來實(shí)現(xiàn)一個(gè)棧的數(shù)據(jù)結(jié)構(gòu)逼纸，可以基于數(shù)組開始。
class Stack {
constructor() {
this.items = [];
}
}
棧的方法有
- push(elements) 添加一個(gè)或者多個(gè)元素到棧頂
- pop() 移除棧頂?shù)脑?/li>
- peek() 返回棧頂?shù)脑丶貌酰?duì)棧不做修改
- isEmpty() 棧為空返回true杰刽，否則返回false;
- clear() 清空棧
- size() 返回棧的元素個(gè)數(shù)
使用javascript的數(shù)組可以實(shí)現(xiàn)上述方法
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
}
使用數(shù)組來創(chuàng)建棧十分方便，但是數(shù)組屬于元素的有序集合王滤，為了保證有序贺嫂，占用的內(nèi)存空間也更多。
我們可以使用對(duì)象來再次創(chuàng)建一個(gè)棧雁乡，實(shí)現(xiàn)上述的方法第喳。
class Stack {
constructor() {
this.count = 0;
this.items = {};
}
push(element) {
this.items[this.count] = element;
this.count++;
}
pop() {
if(this.isEmpty()) {
return undefined;
}
this.count--;
const result = this.items[this.count];
delete this.items[this.count];
return result;
}
size() {
return this.count;
}
isEmpty() {
return this.count === 0;
}
peek() {
if (this.isEmpty) {
return undefined;
}
return this.items[this.count - 1];
}
clear() {
this.count = 0;
this.items = {};
}
}
為了保護(hù)類內(nèi)部的數(shù)據(jù)，可以設(shè)置下劃線命名踱稍，this._items,this._count;
或者使用symbol曲饱，或者weakMap，感興趣的友友們珠月，可以參考學(xué)習(xí)javascript數(shù)據(jù)結(jié)構(gòu)和算法扩淀，這些文章的編寫也是對(duì)我平時(shí)閱讀這本書的一些總結(jié)，個(gè)人練習(xí)輸出啤挎，這本書是寫的很不錯(cuò)的驻谆，解釋的很簡潔明確。
用棧解決問題的一個(gè)實(shí)例是侵浸，進(jìn)制轉(zhuǎn)換旺韭。
比如十進(jìn)制轉(zhuǎn)換二進(jìn)制。
function decimalToBinary(decNumber) {
const stack = new Stack();
let number = decNumber;
let rem; // 余數(shù)
let binaryNumber = '';
while(number > 0) {
rem = Math.floor(number % 2);
stack.push(rem);
number= Math.floor(number / 2);
}
while(!stack.isEmpty()) {
binaryNumber += stack.pop().toString();
}
return binaryNumber;
}
擴(kuò)展到其他進(jìn)制轉(zhuǎn)換掏觉。
function baseConvert(decNumber, base) {
const stack = new Stack();
let number = decNumber;
let rem;
let baseString = '';
const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
if (!(base >= 2 && base <= 36)) {
return '';
}
while(number > 0) {
rem = Math.floor(number % base);
stack.push(rem);
number = Math.floor(number / base);
}
while(!stack.isEmpty()) {
baseString += digits[stack.pop()];
}
return baseString;
}
