夯下數(shù)據(jù)結(jié)構(gòu)和算法基礎(chǔ)，JS 里沒有棧、隊(duì)列、鏈表巴拉巴拉明顯的結(jié)構(gòu)，只能用類去偽造，不然做算法題真的費(fèi)勁。
先造最簡(jiǎn)單的棧類吧，這邊底層使用數(shù)組，當(dāng)然有空的話，你也可以試試對(duì)象。

棧是一種遵從后進(jìn)先出（LIFO）原則的有序集合
新添加或待刪除的元素都保存在棧的同一端，稱作棧頂，另一端就叫棧底（類似，疊盤子）
在棧里，新元素都靠近棧頂，舊元素都靠近棧底。

基本方法

push(i) 添加一個(gè)（或幾個(gè)）新元素到棧頂。
pop() 移除棧頂?shù)脑?，同時(shí)返回被移除的元素。
peek() 返回棧頂?shù)脑兀粚?duì)棧做任何修改（該方法不會(huì)移除棧頂?shù)脑?，僅僅返回它）。
isEmpty() 如果棧里沒有任何元素就返回 true，否則返回 false。
clear() 移除棧里的所有元素。
size() 返回棧里的元素個(gè)數(shù)。這個(gè)方法和數(shù)組的 length 屬性很類似。

類實(shí)現(xiàn)

class Stack {
  stack: any[];
  constructor() {
    this.stack = [];
  }
  size() {
    return this.stack.length;
  }
  peek() {
    return this.stack[this.stack.length - 1];
  }
  push(value: any) {
    this.stack.push(value);
  }
  pop() {
    return this.stack.pop();
  }
  isEmpty() {
    return this.size() === 0;
  }
  clear() {
    this.stack = [];
  }
}

可以頭上頂個(gè)注釋，就容易調(diào)用方法了

/**
 * 棧類
 * @class Stack
 * @description 棧是一種遵從后進(jìn)先出（LIFO）原則的有序集合。
 * 新添加或待刪除的元素都保存在棧的同一端，稱作棧頂，另一端就叫棧底。
 * 在棧里，新元素都靠近棧頂，舊元素都靠近棧底。
 * @property stack 棧內(nèi)部存儲(chǔ)的數(shù)組
 *
 * @method push(element(s)) 添加一個(gè)（或幾個(gè)）新元素到棧頂。
 * @method pop() 移除棧頂?shù)脑?，同時(shí)返回被移除的元素。
 * @method peek() 返回棧頂?shù)脑?，不?duì)棧做任何修改（該方法不會(huì)移除棧頂?shù)脑兀瑑H僅返回它）。
 * @method isEmpty() 如果棧里沒有任何元素就返回 true，否則返回 false。
 * @method clear() 移除棧里的所有元素。
 * @method size() 返回棧里的元素個(gè)數(shù)。這個(gè)方法和數(shù)組的 length 屬性很類似。
 *
 * @example
 * const s = new Stack()
 * s.push(1)
 * s.push(2)
 * s.push(3)
 * s.pop() // 3
 * s.pop() // 2
 * s.pop() // 1
 * s.pop() // undefined
 * s.push(1)
 * s.push(2)
 * s.push(3)
 * s.peek() // 3
 * s.size() // 3
 * s.isEmpty() // false
 * s.clear()
 * s.isEmpty() // true
 * s.size() // 0
 *
 */

應(yīng)用場(chǎng)景

棧的應(yīng)用場(chǎng)景：瀏覽器的歷史記錄、存儲(chǔ)訪問過的任務(wù)、撤銷的操作等等。

練習(xí) 1：十進(jìn)制數(shù)字轉(zhuǎn)化為二進(jìn)制

十進(jìn)制數(shù)字轉(zhuǎn)化為二進(jìn)制的邏輯是：

關(guān)鍵邏輯：用十進(jìn)制數(shù)除以 2，得到的余數(shù)存入棧中，得到的商（迭代）繼續(xù)除以 2，得到的余數(shù)再繼續(xù)存入棧中（循環(huán)），直到商為 0 為止（終止條件）。

function toBinary(decNumber: number) {
  const s = new Stack();
  // 迭代指針，每次得到的商，初始是原始值
  let p = decNumber;
  // 商不為0 就一直循環(huán)
  while (p !== 0) {
    // 余數(shù)進(jìn)棧
    s.push(p % 2);
    // 迭代
    p = Math.floor(p / 2);
  }
  let result = '';
  // 數(shù)字出棧，拼接，直至棧為空
  while (!s.isEmpty()) {
    result += s.pop();
  }
  return result;
}

加上注釋的話

/**
 * 十進(jìn)制轉(zhuǎn)二進(jìn)制
 * 1. 用十進(jìn)制數(shù)除以 2，得到的余數(shù)存入棧中，得到的商繼續(xù)除以2 得到的余數(shù)繼續(xù)存入棧中，直到商為 0 為止。
 * @param {number} decNumber 十進(jìn)制數(shù)
 * @returns {string} 二進(jìn)制數(shù)
 * @example
 * toBinary(2) // '10'
 * toBinary(3) // '11'
 * toBinary(4) // '100'
 * toBinary(5) // '101'
 */

練習(xí) 2：十進(jìn)制數(shù)字轉(zhuǎn)化為任意進(jìn)制

轉(zhuǎn)化邏輯和上面的二進(jìn)制大同小異，但這里有個(gè)限制，任意進(jìn)制的范圍是 2-36，然后超過 10 就是ABCD....，注意下這里就行

function toBaseConverter(decNumber: number, base: number) {
  // 范圍限定
  if (base < 2 || base > 36) throw new Error('base must between 2 and 36');
  const s = new Stack();
  let p = decNumber;
  // 加了這行，超過10的表示
  const baseStr = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
  while (p !== 0) {
    // s.push(p % 2) 換下，因?yàn)橛凶帜?，所以這樣寫法，沒有字母的話p % base就夠用
    s.push(baseStr[p % base]);
    // p = Math.floor(p / 2) 的2換成base
    p = Math.floor(p / base);
  }
  let result = '';
  while (!s.isEmpty()) {
    result += s.pop();
  }
  return result;
}

加上注釋的話

/**
 * 十進(jìn)制轉(zhuǎn)任意進(jìn)制
 * @param {number} decNumber 十進(jìn)制數(shù)
 * @param {number} base 進(jìn)制
 * @returns {string} 任意進(jìn)制數(shù)
 * @example
 * toBaseConverter(20,5) // '40'
 * toBaseConverter(20,2) // '10100'
 * toBaseConverter(20,8) // '24'
 * toBaseConverter(20,16) // '14'
 * toBaseConverter(20,36) // 'E'
 * toBaseConverter(20,37) // Error: base must between 2 and 36
 */

引用