从数组到栈与队列

什么是数组，栈，队列？

数组是数据的有序列表。在JS中，数组的每一项可以保存任何类型的数据，且不限制操作。
栈是一种后进先出的数据结构。又被称为堆栈，对其的增删操作只能在栈顶操作。
队列是一种先进先出的数据结构，是一种特殊的线性表。对其的插入操作需要在队尾进行，删除操作需要在队头操作。

如何实现栈与队列

因为数组的灵活性，且在JS中，提供了一些类似于栈和队列的方法，所以可以很方便的用数组去实现栈和队列。

用数组实现栈

先看栈都有哪些方法。

方法	解释
pop()	执行出栈操作，删除栈顶元素
peek()	查看栈顶元素，不执行删除操作
push(item)	元素入栈
empty()	栈是否为空
search(item)	在栈中查找元素位置

然后看看JS给我们提供了哪些原生方法和属性可以帮助我们去实现栈的方法。

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

是的，能用到的就是这几个，但是，实现起来也很简单，大概思路就是通过 pop() 实现栈的出栈操作， push() 实现栈的入栈操作，恰好可以满足栈的后进先出的规律。
下面我们尝试用这些方法去实现一个栈。

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)

    // 展示栈的内容
    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 私有属性，这个是一个新提案，处于第三阶段。
对于私有属性，可以用其他方案替代，比如：Symbol、WeakMap、闭包等。下面说明一下如何使用 Symbol 实现私有变量。

const _stack = Symbol() // 定义一个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]
}

用数组实现队列

先看队列都有哪些常用的方法或属性。（看了一下Java的队列，方法有点多，这里只拿一部分做实现）

方法	解释
push(item)	添加一个元素
pop()	移除并返回队列头部的元素
peek()	返回队列头部的元素
empty()	队列是否为空

然后看看JS给我们提供了哪些原生方法和属性可以帮助我们去实现队列的方法。

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

下面我们开始用这些方法去实现。大概思路就是通过 shift() 实现栈的出栈操作， push() 实现栈的入栈操作。

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]

用栈实现队列

这是力扣中的一道面试题。
题意很好理解，就是给你一个只支持后进先出的list，实现一个有先进先出功能的list。
实现的重点在于pop()这个方法。放在数组里面说，栈的pop()是移除数组最后一位元素，而要实现的队列的pop()是要移除数组第一位元素，那么我们就想到可以将栈反转过来，然后pop出来的就是反转前的第一个元素了。而要反转就需要用到两个栈。下面是实现过程。

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()
}

栈的使用场景

进制转换

我之前写过一个JS位运算符的博客，里面有涉及到进制的转换。而在计算机里的所有内容都是用二进制数字表示的（0和1）。要把十进制转化成二进制，我们可以将该十进制数字和2整除（二进制是满二进一），直到结果是0为止，而将所有的余数反向排列起来组成数字就是最终的结构。将栈的思维加进去，就是说每一次除2都将余数入栈，然后根据栈后进先出的特性，将余数一个个出栈，就可以得到正确的二进制。而推广一下对其他进制也是相同的思维。下面实现一下。

/**
 * 整数进制转换， 最大支持16进制
 * @param {Number} number 要转换的十进制数字
 * @param {Number} hex 进制
 */
const hexConversion = (number = 0, hex = 10) => {
    const stack = new Stack()
    // 余数
    let rem = 0 
    // 结果
    let result = 0 
    // 存放特殊字符，转换为16进制的时候需要用到
    let aidStr = '0123456789ABCDEF' 
    if (number === 0) return 0

    // 循环求余，并把余数入栈
    while(number > 0) { 
        rem = Math.floor(number % hex)
        stack.push(rem)
        number = Math.floor(number / hex)
    }

    // 将栈中内容全部出栈，并转换为其进制对应的字符
    while(!stack.empty()) { 
        result += aidStr[stack.pop()]
    }

    // 将高位的无效0删去
    return result.replace(/^0+/,'') 
}
console.log(hexConversion(2, 2)) // '010'
console.log(hexConversion(11, 16)) // 'B'

最长有效括号

这是力扣里面的一道题。
利用栈，可以很简单的解答此题。我们将字符串一位一位入栈，当其中一位和栈顶元素匹配时，两个均出栈，最后获取栈的长度，用字符串的长度减去栈的长度就是最长的包含有效括号的子串的长度。
例如对于'(()'，我们一个个压栈，当到')'时，和第二个'('匹配成功，则他不入栈，且第二个'('出栈。最后获取栈的长度为1，用字符串的长度3减去1得到2，与正确结果一致。
下面是实现过程。

// 假设在此处定义了第一节的栈
/**
 * @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 ++) {
        // 当当前字符为左括号或者当栈顶元素不为左括号时才入栈
        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

其他

栈的应用场景还有迷宫求解、汉诺塔实现等等，这里不再做讨论。

队列的使用场景

滑动窗口的最大值

这是《剑指offer》里面的一道面试题。
由题意，我们知道需要不断挪动滑块去获取窗口的最大值。
我们设第一次的滑动窗口的位置为(xⁱ, y^j)，并将这三个值入队列，求出其最大值入数组。
然后移动滑块，得到第二次的位置为(xⁱ⁺¹, y^j+1)，可知，相对于第一次，队列出队列了xⁱ，入队列了y^j+1，然后求出其最大值入数组。
以此类推，直到右边达到数组边界。
其中的难点在于求队列中的最大值。我们可以通过遍历这个队列，用辅助变量去求得最大值。

// 设已有队列que
let max = 0
let aidQue = new Queue()
while(que.size) {
    let popItem = que.pop()
    max = Math.max(max, popItem)
    aidQue.push(popItem)
}
// 恢复que的值
while(aidQue.size) {
    que.push(aidQue.pop())
}

知道了如何去求最大值，整个题就变得迎刃而解了。

// 假设已定义Queue类
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    let slideQue = new Queue()
    let maxArr = []
    let r = k - 1 // 滑窗右侧坐标
    // 确定初始滑窗
    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
    }
    // 遍历计算所有可能的滑窗的值
    while(r < nums.length) {
        maxArr.push(getQueueMax(slideQue))
        slideQue.pop()
        slideQue.push(nums[r + 1])
        r += 1
    }
    return maxArr
};

当然，用数组就会更加简单，这里只是为了体现出队列的用法。

其他

队列还可用于像击鼓传花这种循环队列、买票排队时的优先队列以及JavaScript的任务队列。JS的任务队列又被称为事件循环。

总结

数据结构涉及的范围非常之广，而这只是冰山一角，学习下去，只会感觉到JS越来越有趣。

参考

JavaScript高级程序设计
栈
队列
学习JavaScript数据结构与算法