上一篇文章我們理解了List這種數據結構，知道了它的特點和一些使用場景，這篇文章我們就來看一下棧這種數據結構，這里的棧可不是客棧哦，哈哈

棧其實和List非常像，使用javascript實現都是基于數組來實現

嘗試理解Stack

1.棧只能在棧頂進行入棧和出棧（ 我們可以嘗試把棧想象成一個瓶子，瓶子只有一個瓶口，所有的東西都只能從瓶口塞進去，叢瓶口拿出來）
2. 棧是一種后進先出的數據結構（LIFO，last-in-first-out）（最后塞進瓶子的東西一定最先從瓶子里面拿出來）
3. 棧也有自己的屬性和方法（瓶子里面可以塞很多東西，我們也可以取出瓶子里的東西，或清空整個瓶子）

代碼實現

function Stack () {// 當前棧的數據this.data = [];// 棧頂位置this.top = 0// 向棧中壓入一個元素this.push = function (elem) {this.data[this.top++] = elem}// 從棧中彈出(刪除)棧頂元素并返回this.pop = function() {return this.data[--this.top]}// 僅返回棧頂元素，不刪除this.peek = function() {return this.data[this.top-1]}// 返回棧中的元素個數this.length = function() {return this.top}// 清空棧this.clear = function() {this.top = 0}
}

測試一下

const s = new Stack();
s.push("David");
s.push("Raymond");
s.push("Bryan");
console.log('當前棧長度length:', s.length());
console.log('當前棧頂元素為：', s.peek());const popped = s.pop()
console.log('被彈出的棧頂元素為:', popped);
console.log('當前棧頂元素為：', s.peek());
s.push("Cynthia");
console.log('當前棧頂元素為：', s.peek());
s.clear()
console.log('執行了清空棧');
console.log('當前棧長度length:', s.length());
console.log('當前棧頂元素為：', s.peek());
s.push("Clayton");
console.log('當前棧頂元素為：', s.peek());

測試結果：

實際應用

1. 進制轉換

/*** 進制轉換* @param num * @param base */
function mulBase(num, base) {const s = new Stack()do {s.push(num%base)num = Math.floor(num/base)} while (num > 0)let converted = ''while(s.length() > 0) {converted += s.pop()}return converted
}
console.log('將10轉換為二進制：', mulBase(10, 2))
console.log('將32轉換為二進制：', mulBase(32, 2))
console.log('將125轉換為八進制：', mulBase(125, 8))

2. 判斷回文字符串

/*** 判斷一個字符串是否回文字符串* @param word 需要判斷的字符串*/
function isPalindrome(word) {const s = new Stack()for(let i = 0; i < word.length; i ++) {s.push(word[i])}let rword = ''while(s.length() > 0) {rword += s.pop()}if(word === rword) return truereturn false
}
const word = "hello";
if (isPalindrome(word)) {console.log(word + " 是回文字符串");
}
else {console.log(word + " 不是回文字符串");
}const word1 = "racecar"
if (isPalindrome(word1)) {console.log(word1 + " 是回文字符串");
}
else {console.log(word1 + " 不是回文字符串");
}

3. 模擬遞歸過程，階乘函數

/*** 使用棧模擬遞歸過程，返回n的階乘 n!* @param n * @returns */
function fact(n) {const s = new Stack()while (n > 1) {s.push(n--)}let product = 1while(s.length() > 0) {product *= s.pop()}return product
}
console.log('5的階乘為：', fact(5))

4. 表達式括號匹配問題

/*** 計算某個表達式中的括號是否匹配* @param str 表達式* @returns 匹配情況*/
function isMatch (str) {const match = {match: true,position: -1}const left = new Stack()const right = new Stack()const ml = ['(', '[', '{']const mr = [ ')', ']', '}']for (let i = 0; i < str.length; i ++) {if (ml.includes(str[i])) {left.push({value: str[i],position: i})}if (mr.includes(str[i])) {right.push({value: str[i],position: i})}}while (left.length() || right.length()) {const l = left.pop()const r = right.pop()let indexif (l) index = ml.findIndex((item) => item === l.value)else index = mr.findIndex((item) => item === r.value)if (mr[index] !== r?.value || ml[index] !== l?.value) {match.match = falsematch.position = l ? l.position : r.positonreturn match}}return match
}const string = '2.3 + 23/12 + (3.14159 * 0.24'
if (!isMatch(string).match) {console.log(`表達式${string}括號不匹配，不匹配位置為：`, isMatch(string).position)
} else {console.log(`表達式${string}括號匹配成功`)
}
const string1 = '({ab}(c)ccc['
if (!isMatch(string1).match) {console.log(`表達式${string1}括號不匹配，不匹配位置為：`, isMatch(string1).position)
} else {console.log(`表達式${string1}括號匹配成功`)
}

好了，文章就到這里了，大家如果想了解更多就去看《數據結構與算法javascript描述》這本書吧，希望大家都能有所收獲~