从数组到栈与队列

什么是数组，栈，队列？

数组是数据的有序列表。在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》里面的一道面试题。
由题意，我们知道需要不断挪动滑块去获取窗口的最大值。
我们设第一次的滑动窗口的位置为(xi, yj)，并将这三个值入队列，求出其最大值入数组。
然后移动滑块，得到第二次的位置为(xi+1, yj+1)，可知，相对于第一次，队列出队列了xi，入队列了yj+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数据结构与算法

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 194,390评论 5赞 459
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 81,821评论 2赞 371
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 141,632评论 0赞 319
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 52,170评论 1赞 263
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 61,033评论 4赞 355
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 46,098评论 1赞 272
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 36,511评论 3赞 381
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 35,204评论 0赞 253
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 39,479评论 1赞 290
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 34,572评论 2赞 309
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 36,341评论 1赞 326
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 32,213评论 3赞 312
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 37,576评论 3赞 298
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 28,893评论 0赞 17
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,171评论 1赞 250
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 41,486评论 2赞 341
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 40,676评论 2赞 335