數據結構之Stack | 讓我們一塊來學習數據結構
- 2021 年 4 月 26 日
- 筆記
- javascript, Stack, 數據結構
棧的介紹
棧就是和列表類似的一種數據結構，它可用來解決計算機世界裏的很多問題。棧是一種高 效的數據結構，因為數據只能在棧頂添加或刪除，所以這樣的操作很快，而且容易實現。 棧的使用遍布程序語言實現的方方面面，從表達式求值到處理函數調用
棧是一種特殊的列表，棧內的元素只能通過列表的一端訪問，這一端稱為棧頂。咖啡廳內 的一摞盤子是現實世界中常見的棧的例子。只能從最上面取盤子，盤子洗凈後，也只能摞 在這一摞盤子的最上面。棧被稱為一種後入先出（LIFO，last-in-first-out）的數據結構。
由於棧具有後入先出的特點，所以任何不在棧頂的元素都無法訪問。為了得到棧底的元 素，必須先拿掉上面的元素。
對棧的兩種主要操作是將一個元素壓入棧和將一個元素彈出棧。入棧使用 push() 方法，出 棧使用 pop() 方法。圖 一演示了入棧和出棧的過程。
另一個常用的操作是預覽棧頂的元素。pop() 方法雖然可以訪問棧頂的元素，但是調用該方 法後，棧頂元素也從棧中被永久性地刪除了。peek() 方法則只返回棧頂元素，而不刪除它。
棧的實現
實現一個棧，當務之急是決定存儲數據的底層數據結構。這裡採用的是數組。
我們的實現以定義 Stack 類開始：
class Stack {
constructor() {
this.dataStore = [];
this.top = 0;
}
push() { }
pop() { }
peek() { }
clear() { }
length() { }
empty() { }
toString(){ }
}
我們用數組 dataStore 保存棧內元素，構造函數將其初始化為一個空數組。變量 top 記錄 棧頂位置，被構造函數初始化為 0，表示棧頂對應數組的起始位置 0。如果有元素被壓入 棧，該變量的值將隨之變化。
實現push方法
先來實現 push() 方法。當向棧中壓入一個新元素時，需要將其保存在數組中變量 top 所對 應的位置，然後將 top 值加 1，讓其指向數組中下一個空位置。代碼如下所示：
push(element) {
this.dataStore[++this.top] = element;
}
這裡要特別注意 ++ 操作符的位置，它放在 this.top 的後面，這樣新入棧的元素就被放在 top 的當前值對應的位置，然後再將變量 top 的值加 1，指向下一個位置。
實現pop方法
pop() 方法恰好與 push() 方法相反——它返回棧頂(被刪除的)元素，同時將變量 top 的值減 1：
pop() {
return this.dataStore[this.top--];
}
實現peek方法
peek() 方法返回數組的第 top-1 個位置的元素，即棧頂元素：
peek() {
return this.dataStore[this.top - 1];
}
如果對一個空棧調用 peek() 方法，結果為 undefined。這是因為棧是空的，棧頂沒有任何 元素。
實現length方法
有時候需要知道棧內存儲了多少個元素。length() 方法通過返回變量 top 值的方式返回棧內的元素個數：
length() {
return this.top
}
實現clear方法
可以將變量 top 的值設為 0，輕鬆清空一個棧：
clear() {
this.top = 0;
}
實現empty方法
empty()方法可以知道一個Stack是否是空的
empty() {
return this.top === 0;
}
使用Stack類解決問題
數制間的轉化
可以利用棧將一個數字從一種數制轉換成另一種數制。假設想將數字 n 轉換為以 b 為基數 的數字，實現轉換的算法如下。
- 最高位為
n % b，將此位壓入棧。 - 使用
n/b代替n。 - 重複步驟 1 和 2，直到 n 等於 0，且沒有餘數。
- 持續將棧內元素彈出，直到棧為空，依次將這些元素排列，就得到轉換後數字的字符 串形式
此算法只針對基數為2~9的情況
代碼實現
function mulBase(num, base=2) {
let tmp = new Stack();
while (num > 0) {
tmp.push(num % base)
num = Math.floor(num /= base);
}
let target = '';
while(tmp.length() > 0) {
target = target + tmp.pop();
}
return target;
}
console.log(mulBase(3,2)) // "11"
console.log(mulBase(3,6)) // "6"
迴文字符串的判斷
迴文是指這樣一種現象：一個單詞、短語或數字，從前往後寫和從後往前寫都是一樣的。 比如，單詞「dad」、「racecar」就是迴文；如果忽略空格和標點符號，下面這個句子也是回 文，「A man, a plan, a canal: Panama」；數字 1001 也是迴文。
使用棧，可以輕鬆判斷一個字符串是否是迴文。我們將拿到的字符串的每個字符按從左至 右的順序壓入棧。當字符串中的字符都入棧後，棧內就保存了一個反轉後的字符串，最後 的字符在棧頂，第一個字符在棧底。
function isPalindrome(word) {
if (typeof word !== "string") {
throw TypeError(`參數不是string類型`);
}
let tmp = new Stack();
for (let element of word) {
tmp.push(element)
}
let rword = '';
while (tmp.length() > 0) {
rword += tmp.pop()
}
console.log(rword);
return word === rword;
}
console.log(isPalindrome("racecar")) // true
console.log(isPalindrome("hello")) // false
參考資料
- 數據結構與算法JavaScript描述
