什么是數(shù)組，棧，隊(duì)列？
數(shù)組是數(shù)據(jù)的有序列表。在JS中，數(shù)組的每一項(xiàng)可以保存任何類型的數(shù)據(jù)，且不限制操作。
棧是一種后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。又被稱為堆棧，對(duì)其的增刪操作只能在棧頂操作。
隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)，是一種特殊的線性表。對(duì)其的插入操作需要在隊(duì)尾進(jìn)行，刪除操作需要在隊(duì)頭操作。
如何實(shí)現(xiàn)棧與隊(duì)列
因?yàn)閿?shù)組的靈活性，且在JS中，提供了一些類似于棧和隊(duì)列的方法，所以可以很方便的用數(shù)組去實(shí)現(xiàn)棧和隊(duì)列。
用數(shù)組實(shí)現(xiàn)棧
先看棧都有哪些方法。
| 方法 | 解釋 |
|---|---|
| pop() | 執(zhí)行出棧操作，刪除棧頂元素 |
| peek() | 查看棧頂元素，不執(zhí)行刪除操作 |
| push(item) | 元素入棧 |
| empty() | 棧是否為空 |
| search(item) | 在棧中查找元素位置 |
然后看看JS給我們提供了哪些原生方法和屬性可以幫助我們?nèi)?shí)現(xiàn)棧的方法。
let arr = [1, 2, 3, 4, 5]
arr.pop() // 5
console.log(arr) // [1, 2, 3, 4]
arr.push(7) // 5
console.log(arr) // [1, 2, 3, 4, 7]
console.log(arr.length) // 5
arr.findIndex(item => item === 4) // 3
是的，能用到的就是這幾個(gè)，但是，實(shí)現(xiàn)起來(lái)也很簡(jiǎn)單，大概思路就是通過(guò) pop() 實(shí)現(xiàn)棧的出棧操作， push() 實(shí)現(xiàn)棧的入棧操作，恰好可以滿足棧的后進(jìn)先出的規(guī)律。
下面我們嘗試用這些方法去實(shí)現(xiàn)一個(gè)棧。
class Stack {
// 私有屬性
#stack
constructor() {
this.#stack = []
}
get size() {
return this.#stack.length
}
empty = () => !this.#stack.length
pop = () => this.#stack.pop()
push = item => this.#stack.push(item)
peek = () => this.#stack[this.#stack.length - 1]
search = item => this.#stack.findIndex(ele => ele === item)
// 展示棧的內(nèi)容
print = () => this.#stack
}
const stack = new Stack()
stack.empty() // true
stack.push(1) // 1
stack.push(2) // 2
stack.push(3) // 3
stack.push(4) // 4
stack.peek() // 4
stack.pop() // 4
stack.size // 3
stack.search(2) // 1
stack.print() // [1, 2, 3]
在這里我還用到了 #stack 私有屬性，這個(gè)是一個(gè)新提案，處于第三階段。
對(duì)于私有屬性，可以用其他方案替代，比如：Symbol、WeakMap、閉包等。下面說(shuō)明一下如何使用 Symbol 實(shí)現(xiàn)私有變量。
const _stack = Symbol() // 定義一個(gè)Symbol，作為假的私有變量
class Stack {
constructor() {
this[_stack] = []
}
get size() {
return this[_stack].length
}
empty = () => !this[_stack].length
pop = () => this[_stack].pop()
push = item => this[_stack].push(item)
peek = () => this[_stack][this[_stack].length - 1]
search = item => this[_stack].findIndex(ele => ele === item)
print = () => this[_stack]
}
用數(shù)組實(shí)現(xiàn)隊(duì)列
先看隊(duì)列都有哪些常用的方法或?qū)傩?。（看了一下Java的隊(duì)列，方法有點(diǎn)多，這里只拿一部分做實(shí)現(xiàn)）
| 方法 | 解釋 |
|---|---|
| push(item) | 添加一個(gè)元素 |
| pop() | 移除并返回隊(duì)列頭部的元素 |
| peek() | 返回隊(duì)列頭部的元素 |
| empty() | 隊(duì)列是否為空 |
然后看看JS給我們提供了哪些原生方法和屬性可以幫助我們?nèi)?shí)現(xiàn)隊(duì)列的方法。
let arr = [1, 2, 3, 4, 5]
arr.shift() // 1
console.log(arr) // [2, 3, 4, 5]
arr.push(7) // 5
console.log(arr) // [2, 3, 4, 5, 7]
console.log(arr.length) // 5
下面我們開(kāi)始用這些方法去實(shí)現(xiàn)。大概思路就是通過(guò) shift() 實(shí)現(xiàn)棧的出棧操作， push() 實(shí)現(xiàn)棧的入棧操作。
class Queue {
#queue
constructor() {
this.#queue = []
}
get size() {
return this.#queue.length
}
push = item => this.#queue.push(item)
pop = () => this.#queue.shift()
peek = () => this.#queue[0]
empty = () => !this.#queue.length
print = () => this.#queue
}
const que = new Queue()
que.empty() // true
que.push(1) // 1
que.push(2) // 2
que.push(3) // 3
que.push(4) // 4
que.empty() // false
que.size // 4
que.peek() // 1
que.pop() // 1
que.print() // [2, 3, 4]
用棧實(shí)現(xiàn)隊(duì)列
這是力扣中的一道面試題。
題意很好理解，就是給你一個(gè)只支持后進(jìn)先出的list，實(shí)現(xiàn)一個(gè)有先進(jìn)先出功能的list。
實(shí)現(xiàn)的重點(diǎn)在于pop()這個(gè)方法。放在數(shù)組里面說(shuō)，棧的pop()是移除數(shù)組最后一位元素，而要實(shí)現(xiàn)的隊(duì)列的pop()是要移除數(shù)組第一位元素，那么我們就想到可以將棧反轉(zhuǎn)過(guò)來(lái)，然后pop出來(lái)的就是反轉(zhuǎn)前的第一個(gè)元素了。而要反轉(zhuǎn)就需要用到兩個(gè)棧。下面是實(shí)現(xiàn)過(guò)程。
class Queue2 {
constructor() {
this.stack = new Stack()
this.aidStack = new Stack()
}
get size() {
return this.stack.size
}
push = item => this.stack.push(item)
pop = () => {
if (this.aidStack.size < 1) {
while(this.stack.size) {
this.aidStack.push(this.stack.pop())
}
}
let popItem = this.aidStack.pop()
while(this.aidStack.size) {
this.stack.push(this.aidStack.pop())
}
return popItem
}
peek = () => {
if (this.aidStack.size < 1) {
while(this.stack.size) {
this.aidStack.push(this.stack.pop())
}
}
let peekItem = this.aidStack.peek()
while(this.aidStack.size) {
this.stack.push(this.aidStack.pop())
}
return peekItem
}
empty = () => this.stack1.empty()
}
棧的使用場(chǎng)景
進(jìn)制轉(zhuǎn)換
我之前寫過(guò)一個(gè)JS位運(yùn)算符的博客，里面有涉及到進(jìn)制的轉(zhuǎn)換。而在計(jì)算機(jī)里的所有內(nèi)容都是用二進(jìn)制數(shù)字表示的（0和1）。要把十進(jìn)制轉(zhuǎn)化成二進(jìn)制，我們可以將該十進(jìn)制數(shù)字和2整除（二進(jìn)制是滿二進(jìn)一），直到結(jié)果是0為止，而將所有的余數(shù)反向排列起來(lái)組成數(shù)字就是最終的結(jié)構(gòu)。將棧的思維加進(jìn)去，就是說(shuō)每一次除2都將余數(shù)入棧，然后根據(jù)棧后進(jìn)先出的特性，將余數(shù)一個(gè)個(gè)出棧，就可以得到正確的二進(jìn)制。而推廣一下對(duì)其他進(jìn)制也是相同的思維。下面實(shí)現(xiàn)一下。
/**
* 整數(shù)進(jìn)制轉(zhuǎn)換， 最大支持16進(jìn)制
* @param {Number} number 要轉(zhuǎn)換的十進(jìn)制數(shù)字
* @param {Number} hex 進(jìn)制
*/
const hexConversion = (number = 0, hex = 10) => {
const stack = new Stack()
// 余數(shù)
let rem = 0
// 結(jié)果
let result = 0
// 存放特殊字符，轉(zhuǎn)換為16進(jìn)制的時(shí)候需要用到
let aidStr = '0123456789ABCDEF'
if (number === 0) return 0
// 循環(huán)求余，并把余數(shù)入棧
while(number > 0) {
rem = Math.floor(number % hex)
stack.push(rem)
number = Math.floor(number / hex)
}
// 將棧中內(nèi)容全部出棧，并轉(zhuǎn)換為其進(jìn)制對(duì)應(yīng)的字符
while(!stack.empty()) {
result += aidStr[stack.pop()]
}
// 將高位的無(wú)效0刪去
return result.replace(/^0+/,'')
}
console.log(hexConversion(2, 2)) // '010'
console.log(hexConversion(11, 16)) // 'B'
最長(zhǎng)有效括號(hào)
這是力扣里面的一道題。
利用棧，可以很簡(jiǎn)單的解答此題。我們將字符串一位一位入棧，當(dāng)其中一位和棧頂元素匹配時(shí)，兩個(gè)均出棧，最后獲取棧的長(zhǎng)度，用字符串的長(zhǎng)度減去棧的長(zhǎng)度就是最長(zhǎng)的包含有效括號(hào)的子串的長(zhǎng)度。
例如對(duì)于'(()'，我們一個(gè)個(gè)壓棧，當(dāng)?shù)?)'時(shí)，和第二個(gè)'('匹配成功，則他不入棧，且第二個(gè)'('出棧。最后獲取棧的長(zhǎng)度為1，用字符串的長(zhǎng)度3減去1得到2，與正確結(jié)果一致。
下面是實(shí)現(xiàn)過(guò)程。
// 假設(shè)在此處定義了第一節(jié)的棧
/**
* @param {string} s
* @return {number}
*/
var longestValidParentheses = function(s) {
if (!s) return 0
const stack = new Stack()
for (let i = 0; i < s.length; i ++) {
// 當(dāng)當(dāng)前字符為左括號(hào)或者當(dāng)棧頂元素不為左括號(hào)時(shí)才入棧
if (s[i] === '(' || (s[i] === ')' && stack.peek() !== '(')) {
stack.push(s[i])
} else {
stack.pop()
}
}
return s.length - stack.size
};
console.log(longestValidParentheses('(()')) // 2
console.log(longestValidParentheses(')()())')) // 4
其他
棧的應(yīng)用場(chǎng)景還有迷宮求解、漢諾塔實(shí)現(xiàn)等等，這里不再做討論。
隊(duì)列的使用場(chǎng)景
滑動(dòng)窗口的最大值
這是《劍指offer》里面的一道面試題。
由題意，我們知道需要不斷挪動(dòng)滑塊去獲取窗口的最大值。
我們?cè)O(shè)第一次的滑動(dòng)窗口的位置為(xi, yj)，并將這三個(gè)值入隊(duì)列，求出其最大值入數(shù)組。
然后移動(dòng)滑塊，得到第二次的位置為(xi+1, yj+1)，可知，相對(duì)于第一次，隊(duì)列出隊(duì)列了xi，入隊(duì)列了yj+1，然后求出其最大值入數(shù)組。
以此類推，直到右邊達(dá)到數(shù)組邊界。
其中的難點(diǎn)在于求隊(duì)列中的最大值。我們可以通過(guò)遍歷這個(gè)隊(duì)列，用輔助變量去求得最大值。
// 設(shè)已有隊(duì)列que
let max = 0
let aidQue = new Queue()
while(que.size) {
let popItem = que.pop()
max = Math.max(max, popItem)
aidQue.push(popItem)
}
// 恢復(fù)que的值
while(aidQue.size) {
que.push(aidQue.pop())
}
知道了如何去求最大值，整個(gè)題就變得迎刃而解了。
// 假設(shè)已定義Queue類
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function(nums, k) {
let slideQue = new Queue()
let maxArr = []
let r = k - 1 // 滑窗右側(cè)坐標(biāo)
// 確定初始滑窗
for (let i = 0; i < k; i ++) {
slideQue.push(nums[i])
}
const getQueueMax = (que) => {
let max = 0
let aidQue = new Queue()
while(que.size) {
let popItem = que.pop()
max = Math.max(max, popItem)
aidQue.push(popItem)
}
while(aidQue.size) {
que.push(aidQue.pop())
}
return max
}
// 遍歷計(jì)算所有可能的滑窗的值
while(r < nums.length) {
maxArr.push(getQueueMax(slideQue))
slideQue.pop()
slideQue.push(nums[r + 1])
r += 1
}
return maxArr
};
當(dāng)然，用數(shù)組就會(huì)更加簡(jiǎn)單，這里只是為了體現(xiàn)出隊(duì)列的用法。
其他
隊(duì)列還可用于像擊鼓傳花這種循環(huán)隊(duì)列、買票排隊(duì)時(shí)的優(yōu)先隊(duì)列以及JavaScript的任務(wù)隊(duì)列。JS的任務(wù)隊(duì)列又被稱為事件循環(huán)。
總結(jié)
數(shù)據(jù)結(jié)構(gòu)涉及的范圍非常之廣，而這只是冰山一角，學(xué)習(xí)下去，只會(huì)感覺(jué)到JS越來(lái)越有趣。
參考
JavaScript高級(jí)程序設(shè)計(jì)
棧
隊(duì)列
學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法
