野生前端的資料結構基礎練習(1)——棧

摘要： 習題主要選自Orelly出版的《資料結構與演算法javascript描述》一書。 參考程式碼可見: https://github.com/dashnowords/blogs/tree/master/Structure/Stack 基本練習 根據棧的特性實現一...

習題主要選自Orelly出版的《資料結構與演算法javascript描述》一書。

參考程式碼可見: ofollow,noindex" target="_blank">https://github.com/dashnowords/blogs/tree/master/Structure/Stack

基本練習

1. 根據棧的特性實現一個 Stack 類，並在後續題目中需要用棧時使用它。
2. 編寫一個函式 unitTrans(num, unit) , num 為一個10進位制數字， unit 要轉換的進位制數，求轉換結果。
3. 編寫一個函式 recursion(num) , num 為一個10進位制數字，要求輸出 num! 的結果。
4. 編寫一個函式 palindrome(str) , str 是一個字串,如果它是一個迴文字串，則返回 true ，否則返回 false 。

課後習題（書中第四節習題）

1. 一個算數表示式中有 {} , () , [] 三種括號，編寫一個函式，接受一個算數表示式作為引數，如果括號完全匹配則返回 true ,否則返回括號缺失的位置。
2. 一個表示式的字尾表示式形式為 opt1 opt2 operator ,編寫一個函式，接受一個算數表示式作為引數（平時使用的算數表示式形式即為中綴表示式），將其轉換為字尾表示式（可暫不考慮運算優先順序）。
3. 盒子裡從上到下放有不定數量的【紅色】，【白色】，【黃色】三種糖果，編寫一個程式，可以使用一個或多個棧，在保證原糖果順序不變的情況下，取出所有的【黃色】糖果。

習題思路

1. 按字元逐個解析表示式，遇到左括號即將其壓入棧中，遇到右括號就從棧頂彈出一個元素，檢視兩者是否匹配，若匹配則繼續，若不匹配則返回位置。需要注意的是，如果所有括號均配，則棧的最終狀態需要為空。
2. 逆向解析原表示式，將 運算元 和 操作符 分別壓入兩個棧中，接著先從運算元棧中彈出第一個元素，在輪流從運算元棧和操作符棧中彈出元素直至棧為空即可。如果從前到後解析，則棧頂的是最後的元素，出棧時考慮到順序即可。
3. 只用一個額外的棧即可，將【紅色】【白色】糖果壓入新棧，將黃色糖果移除，當糖果盒為空後，再從新的糖果棧中逐個彈出元素重新放回糖果盒的棧即可。