简单理解JavaScript数据结构的栈和列队

青年码农

发布于 2021-03-04 14:50:52

3930

发布于 2021-03-04 14:50:52

文章被收录于专栏：青年码农青年码农

在了解JavaScript栈和列队之前，我们先了解下栈和列队的基本概念，栈和队列都是动态的集合，在栈中，栈实现了后进先出。在队列中，队列实现了先进先出的策略。一个简单的比喻，吃多了拉就是列队，吃多了吐就是栈。

上面总结的比较简短，我们结合代码来做进一步解释。

1 栈

我们先看一张图，

栈是一种LIFO（Last-In-First-Out，后进先出）的数据结构，也就是最新添加的项最早被移除。而栈中项的插入（叫做推入）和移除（叫做弹出），只发生在一个位置，那就是栈的顶部。

最开始栈中不含有任何数据，叫做空栈，此时栈顶就是栈底。然后数据从栈顶进入，栈顶栈底分离，整个栈的当前容量变大。数据出栈时从栈顶弹出，栈顶下移，整个栈的当前容量变小。

比如我们有一个书箱子，里面堆满了书。最下面的书，肯定是最早放进去的，如果你想拿最下面的书，你只能从上面一本一本拿出来，这就是栈。

JavaScript数组提供了内置方法，可以实现类似出栈入栈的功能，入栈push()、出栈pop()；

创建list

let arr = []

入栈

arr.push(1, 2, 3, 4)

出栈

arr.pop()

封装方法，实现栈结构

function Stack (){
    let items = []

    this.push = function(element){
        items.push(element)
    }
    this.pop = function(){
       return items.pop()
    }
    this.peek = function(){
        return items[items.length - 1]
    }
    this.isEmpty = function(){
        return items.length === 0
    }
    this.size = function(){
        return items.length
    }
    this.clear = function(){
        items = []
    }
    this.print = function(){
        console.log(items.toString())
    }
}

ES6方式实现

class Stack {
    constructor() {
        this.items = [];
    }
    push(element) {
        this.items.push(element)
    }
    pop() {
        return this.items.pop()
    }
    peek() {
        return this.items[items.length - 1]
    }
    isEmpty() {
        return this.items.length === 0
    }
    size() {
        return this.items.length
    }
    clear() {
        this.items = []
    }
    print() {
        console.log(this.items.toString())
    }
}

2 列队

我们还是先看一张图，

队列是一种FIFO(Fist-In-First-Out,先进先出)的数据结构，队列在列表的末端添加项，从列表的前端移除项。就好像排队买票，取餐，先来的，最先买票，取餐。

JavaScript数组提供了内置方法，可以实现列队的功能，入队unshift()、出队pop()；

创建list

let arr = []

入队

arr.unshift(1)

出队

arr.pop()

封装方法，实现列队结构

function Queue () {
    let items = []

    this.unshift = function (element) {
        items.unshift(element)
    }
    this.pop = function () {
        return items.pop()
    }
    this.peek = function () {
        return items[items.length - 1]
    }
    this.isEmpty = function () {
        return items.length === 0
    }
    this.size = function () {
        return items.length
    }
    this.clear = function () {
        items = []
    }
    this.print = function () {
        console.log(items.toString())
    }
}

ES6方式实现

class Queue {
    constructor() {
        this.items = [];
    }
    unshift(element) {
        this.items.unshift(element)
    }
    pop() {
        return this.items.pop()
    }
    peek() {
        return this.items[items.length - 1]
    }
    isEmpty() {
        return this.items.length === 0
    }
    size() {
        return this.items.length
    }
    clear() {
        this.items = []
    }
    print() {
        console.log(this.items.toString())
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-02-26，如有侵权请联系 cloudcommunity@tencent.com 删除

javascript