數據結構棧

NO IMAGE

一 目錄

不折騰的前端,和鹹魚有什麼區別

目錄
一 目錄
二 前言
三 模擬實現棧
四 進制轉換算法
4.1 十進制轉二進制
4.2 十進制和十六以內任意進制轉換
五 平衡圓括號
六 總結

二 前言

返回目錄

經典開局:什麼是棧?

棧是一種遵從後進先出(LIFO)原則的有序集合。

沒聽懂?舉個例子:

  • 有一摞書,先放的在最底下,在書非常多的情況你拿不到底部的書的情況下,如果你要拿到最底下的書,你每次需要先將最後放的先挪開,最後才能拿到最底下的書。
  • 廚房堆放的盤子,每次拿的是最上面的,最後才拿底層(最先疊的)。

看到這裡,相信小夥伴們會聯想起兩個數組的方法:push()pop()

是的,假設有一個數組:

  • const arr = [1, 2, 3, 4];

如果我們需要往裡面進行堆棧行為,那麼就是通過 arr.push() 往裡面添加元素,通過 arr.pop() 往外推出元素。

當然,模擬棧還不止這些方法,我們繼續往下瞧~

三 模擬實現棧

返回目錄

首先,為棧聲明一些方法:

  • push(element):添加一個或者多個元素到棧頂
  • pop():移除棧頂的元素,同時返回該元素
  • peek():查看棧頂的元素
  • isEmpty():判斷棧是否空了,是則返回 true,否則返回 false
  • clear():清除棧中的所有元素
  • size:返回棧裡的元素個數,方法和 length 類似

然後,我們嘗試實現這些方法:

實現代碼:

function Stack() {
let items = [];
this.push = function(element) {
items.push(element);
};
this.pop = function() {
const pop = items.pop();
return pop;
};
this.peek = function() {
return items[items.length - 1];
};
this.isEmpty = function() {
return items.length === 0;
};
this.clear = function() {
items = [];
};
this.size = function() {
return items.length;
};
}
let stack = new Stack();
stack.push(1);
// stack: [1]
stack.pop();
// stack: []
stack.push(1);
stack.push(2);
// stack: [1, 2]
stack.peek();
// Console: 2
stack.isEmpty();
// Console: false
stack.clear();
// stack: []
stack.size();
// 0

當然,如果純粹看 jsliang 寫的,沒圖沒視頻,小夥伴們很容易懵逼,這裡 jsliang 建議看各個大佬的文章或者通過下面章節的幾個案例進一步瞭解:

四 進制轉換算法

返回目錄

如果小夥伴大學走過流程,應該會碰到個老教授,跟你講十進制轉二進制。

如果小夥伴還沒聽過,那麼 jsliang 來介紹一下~

4.1 十進制轉二進制

返回目錄

10 進制轉換成 2 進制,是怎麼走的呢?

  • 10 進制的 10 轉 2 進制
10 % 2 = 0 | 10 / 2 = 5
5 % 2 = 1 |  5 / 2 = 2
2 % 2 = 0 |  2 / 2 = 1
1 % 2 = 1 |  1 / 2 = 0

在這裡,10 進制的 10 轉換成 2 進制變成 1010

  • 10 進制的 25 轉 2 進制
25 % 2 = 1 | 25 / 2 = 12
12 % 2 = 0 | 12 / 2 = 6
6 % 2 = 0 |  6 / 2 = 3
3 % 2 = 1 |  3 / 2 = 1
1 % 2 = 1 |  1 / 2 = 0

在這裡,10 進制的 25 轉換成 2 進制變成 11001

那麼,下面開始解密:

  1. 已知 10 進制的數為 n
  2. 將 n 每次取餘 2 的值放入棧底部。
  3. 將 n 每次除於 2 的值當成下一次循環的數字(向下取整,捨棄小數部位)。
  4. 循環步驟 2 和步驟 3,直至 n 等於 0 為止。
  5. 將棧的數值依序推出來,從而得到最終結果。

說這麼多,且看代碼:

const decimalToBinary = (num) => {
const result = [];
while (num > 0) {
result.push(num % 2);
num = Math.floor(num / 2);
}
return result.reverse().join('');
};
console.log(decimalToBinary(10)); // '1010'
console.log(decimalToBinary(25)); // '11001'

怎麼樣,是不是感覺 So easy~

當然,為了防止看不懂,咱們還可以再修改修改:

const decimalToBinary = (num) => {
const stack = [];
let result = '';
while (num > 0) {
stack.push(num % 2);
num = Math.floor(num / 2);
}
for (let i = stack.length - 1; i >= 0; i--) {
result += stack[i];
}
return result;
};
console.log(decimalToBinary(10)); // '1010'
console.log(decimalToBinary(25)); // '11001'

這樣,我們就完成了十進制轉二進制啦~

4.2 十進制和十六以內任意進制轉換

返回目錄

那麼,既然這個這麼好用,我們能不能改改,變成十進制轉換成十六進制以內任意進制呢?

答案是可以的,上代碼:

/**
* @name 任意進制轉換
* @param {Number} number 需要轉換的數字
* @param {Number} binarySystem 需要轉換成的進制
*/
const arbitraryBaseConversion = (number, binarySystem) => {
const stack = [];
const digits = '0123456789ABCDEF';
while (number > 0) {
stack.push(digits[Math.floor(number % binarySystem)]);
number = Math.floor(number / binarySystem);
}
return stack.reverse().join('');
}
console.log(arbitraryBaseConversion(10, 2)); // '1010'
console.log(arbitraryBaseConversion(100, 2)); // '1100100'
console.log(arbitraryBaseConversion(10, 16)); // 'A'
console.log(arbitraryBaseConversion(100, 16)); // '64'

這樣,我們就完成了十進制轉十六進制內任意進制的方法啦~

五 平衡圓括號

返回目錄

下面我們再嘗試一下平衡圓括號的問題:

leetcode-cn.com/problems/va…

給定一個只包括 '(',')','{','}','[',']' 的字符串,判斷字符串是否有效。
有效字符串需滿足:
左括號必須用相同類型的右括號閉合。
左括號必須以正確的順序閉合。
注意空字符串可被認為是有效字符串。
示例 1:
輸入: "()"
輸出: true
示例 2:
輸入: "()[]{}"
輸出: true
示例 3:
輸入: "(]"
輸出: false
示例 4:
輸入: "([)]"
輸出: false
示例 5:
輸入: "{[]}"
輸出: true

如果小夥伴們希望能自己嘗試一下,可以拿下面的代碼試用:

/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
};

用棧的話,怎麼實現呢?

/**
* @name 平衡圓括號
* @param {string} s
* @return {boolean}
*/
const isValid = (s) => {
const stack = [];
for (let i = 0; i < s.length; i++) {
if (
(s[i] === ')' && stack[stack.length - 1] === '(')
|| (s[i] === ']' && stack[stack.length - 1] === '[')
|| (s[i] === '}' && stack[stack.length - 1] === '{')
) {
stack.pop();
} else {
stack.push(s[i]);
}
}
console.log(stack);
return stack.length === 0;
};
console.log(isValid('()'));     // true
console.log(isValid('()[]{}')); // true
console.log(isValid('(]'));     // false
console.log(isValid('([)]'));   // false
console.log(isValid('{[]}'));   // true

案例 1

()[]{} 舉例:

  1. 判斷 ( 不是閉合括號,所以推入棧,stack = [ '(' ]
  2. 判斷 ) 是閉合括號,所以推出棧,stack = []
  3. 判斷 [ 不是閉合括號,所以推入棧,stack = [ '[' ]
  4. 判斷 ] 是閉合括號,所以推出棧,stack = []
  5. 判斷 { 不是閉合括號,所以推入棧,stack = [ '{' ];
  6. 判斷 } 是閉合括號,所以推出棧,stack = []

最後 stack.length 為 0 了,所以它是 true 的。

案例 2

再拿 ([)] 舉例:

  1. 判斷 ( 不是閉合括號,所以推入棧,stack = [ '(' ]
  2. 判斷 [ 不是閉合括號,所以推入棧,stack = [ '(', '[' ]
  3. 判斷 ) 是閉合括號,但是棧頂層的元素是 [ 而不是 (,所以還是推入棧,stack = [ '(', '[', ')' ]
  4. 判斷 ] 是閉合括號,但是棧頂層的元素是 ) 而不是 [,所以還是推入棧,stack = [ '(', '[', ')', ']' ]

最後 stack.length 為 4 了,所以它是 false 的。

這樣,我們通過平衡圓括號進一步瞭解了棧的一些形式。

六 總結

返回目錄

經過 進制轉換 以及 平衡圓括號 這兩道題目,想必小夥伴們應該對棧有了更深層次的瞭解。

當然,我們還有一些問題沒有解決,例如:漢諾塔 等等,但是因為 jsliang 一時沒有找到對應的題目(只有漢諾塔描述),所以這裡就不哆嗦啦,下次碰到咱們再加上這裡來。


不折騰的前端,和鹹魚有什麼區別!

數據結構棧

jsliang 會每天更新一道 LeetCode 題解,從而幫助小夥伴們夯實原生 JS 基礎,瞭解與學習算法與數據結構。

浪子神劍 會每天更新面試題,以面試題為驅動來帶動大家學習,堅持每天學習與思考,每天進步一點!

掃描上方二維碼,關注 jsliang 的公眾號(左)和 浪子神劍 的公眾號(右),讓我們一起折騰!

數據結構棧
jsliang 的文檔庫 由 樑峻榮 採用 知識共享 署名-非商業性使用-相同方式共享 4.0 國際 許可協議進行許可。
基於github.com/LiangJunron…上的作品創作。
本許可協議授權之外的使用權限可以從 creativecommons.org/licenses/by… 處獲得。

相關文章

精讀《正交的React組件》

如何封裝一個flutter的多語言plugin

我在真實項目中使用了AST大法!

SpringBoot如何優雅的校驗參數