关于前端:前端内练基础你应该知道的数据结构之栈和队列

4次阅读

共计 5769 个字符，预计需要花费 15 分钟才能阅读完成。

前言：为什么要学数据结构，它能帮忙咱们什么？能解决什么问题呢，首页数据结构并不是一门具体的编程语言，它教会咱们的是一种思维形式，即如何以更优的形式存储数据和解决的一些问题，通过学习数据结构，能够大大拓宽咱们的思维模式。把握了数据结构与算法，咱们对待问题的深度、解决问题的角度会大有不同，对于集体逻辑思维的晋升，也是质的飞跃。

上面从以下几个点呈现逐个的理解他们实现的原理和场景：

  • 什么是栈
  • 什么是队列
  • 什么是链表
  • 什么是汇合
  • 什么是字典
  • 什么 二叉树

什么是栈

在介绍 栈的时候 咱们须要理解 数组 的概念、以及数组罕用的办法是什么 能力更好的理解栈的原理是什么。

Array：JavaScript 数组用于在繁多变量中存储多个值，实质上是对象。

如何创立数组：

let arr1 = [1,2,3] // [element0, element1, ..., elementN]
let arr2 = new Array(1,2,3) // new Array(element0, element1[, ...[, elementN]])
let arr3 = new Array(3); // new Array(arrayLength)

数组的罕用办法有哪些：

console.log(Object.getOwnPropertyNames(Array.prototype);)
// ["length", "constructor", "concat", "copyWithin", "fill", "find", "findIndex", "lastIndexOf", "pop", "push", "reverse", "shift", "unshift", "slice", "sort", "splice", "includes", "indexOf", "join", "keys", "entries", "values", "forEach", "filter", "flat", "flatMap", "map", "every", "some", "reduce", "reduceRight", "toLocaleString", "toString"]

来几个栗子热热身

const arrs = ['篮球','足球','乒乓球'];

拜访数组元素

console.log(arrs[0])    // 篮球
console.log(arrs[arrs.length - 1])    // 乒乓球

增加元素到数组的开端

const arrs = ['篮球', '足球', '乒乓球'];
arrs.push('羽毛球')
console.log(arrs)    // ["篮球", "足球", "乒乓球", "羽毛球"]

栈的准则：后进先出（LIPO）

新增加的或者删除的元素都在 栈顶 ，另一端叫 栈底 ，在栈里，新元素都凑近栈顶， 旧元素都靠近栈顶，能够把试想它就是一摞书、或者是一摞盘子都能够、只有能了解其含意即可。

那么 如何实现一个栈 呢？

首先咱们要思考几点：栈都有那些办法或者都有什么作用：

  • push()：增加一个或者多个新元素
  • pop()：移除栈顶的元素、同时返回被移除的元素
  • peek()：返回栈顶的元素、不会对栈做任何的批改
  • isEmpty()：判断栈是否为空的状态、返回布尔值
  • clear()：清空栈的元素
  • size()：返回栈的元素个数

实现一个 Stack 栈：

    class Stack {constructor () {this.items = []
        }

        push(data){this.items.push(data)
        }

        pop() {return this.items.pop()
        }

        peek() {return this.items[this.items.length - 1]
        }

        isEmpty(){return this.items.length === 0}

        size () {return this.items.length}

        clear() {this.items = []
        }
    }

测试：

const foo = new Stack()
foo.push(1)  // [1]
foo.push(2)  // [1,2]
foo.push(3)  // [1,2,3]
foo.push(4)  // [1,2,3,4] 
foo.pop()    // [1,2,3]
foo.clear()  // []

以上是简略的实现形式。

不过在数组的操作如果存在大量的操作数据这可能不是最高效的、大部分的办法的工夫复杂度是 O(n), 意思就是要迭代整个数组晓得找到那个元素、n 代表数组的长度、如果数组有很多的元素、那么所需的工夫会更长，那么有没有更好的形式来实现呢？

答：有的 。 应用对象代替存储、同时申明变量记录以后栈的大小。

class Stack {constructor () {this.items = {}
        this.count = 0
    }

    push(data){this.items[this.count] = data
        this.count ++ 
    }

    pop() {if(this.isEmpty()) {return undefined}

        this.count -- 
        const result = this.items[this.count]
        delete this.items[this.count]
        return result
    }

    peek() {if(this.isEmpty()) {return undefined}
        return this.items[this.count - 1]
    }

    isEmpty(){return this.count === 0}

    size () {return this.count}

    clear() {this.items = {}
        this.count = 0
    }
}

其实以上的版本还不是很完满、如果咱们间接扭转数据的构造或对象时就会导致数据结构的凌乱吗，比方：

const foo = new Stack()
foo.items = null
foo.push(1) // TypeError

JavaScript 没有公有属性的概念、然而能够通过 Symbol 属性进行模仿、或者应用 WeakMap 数据结构进行模仿、请参考以下 简略的代码 示例：

模仿公有属性：Symbol

const _items = Symbol('item') // 申明一个 key
class Stack {constructor () {
        // 申明约定下划线命名为【公有属性】this[_items] = {}
        this._count = 0
    }

    push(data){this[_items][this._count] = data
        this._count ++ 
    }
    ...
}

模仿公有属性：WeakMap

    const _items = new WeakMap()

    class Stack {constructor () {
            // 以 Stack 为本人的援用为键值，存储 items
            _items.set(this,[])
        }

        push(data){const list = _items.get(this)
           list.push(data)
        }

        pop(){const list = _items.get(this)
            const result = list.pop()
            return result
        }

        ...
}

以上其实都不是很完满，然而鱼和熊掌不可兼得，还是依据本人的利用场景做一些取舍。

用栈能解决什么问题？

参考力扣的原题为例，试着用栈的思维来解决

来自力扣 20 题无效的括号：

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {let stack = []

    let left = ['(','[',"{"]

    for (let i = 0; i< s.length; i++) {let ch = s[i]

    if(left.includes(ch)) {stack.push(ch)
    }

    if(stack.length === 0) return false

    if (ch == ')' && stack.pop() != '(') return false
    if (ch == ']' && stack.pop() != '[') return false
    if (ch == '}' && stack.pop() != '{') return false
    }

    return  stack.length === 0
};

什么是队列

队列遵循 先进先出 (FIFO) 准则 的一组有序的项，队列在尾部增加新元素、并从顶部移除元素、最新增加的元素必须在队列开端。常见的了解队列：排队买票

队列罕用的办法：

  • enqueue()：增加一个或者多个新元素。
  • dequeue()：移除队列的第一项（即排在队列最后面的项）并返回被移除的元素。
  • peek()：返回队列中第一个元素——最先被增加，也将是最先被移除的元素。
  • isEmpty()：判断队列是否为空的状态、返回布尔值。
  • clear()：清空队列的元素。
  • size()：返回队列的元素个数。

实现一个 Queue 队列：

class Queue {constructor(){
        this.count = 0; // 记录对象的 size
        this.lowestCount = 0;   // 跟踪第一个元素
        this.items = {} // 初始化对象}
    enqueue(data) {this.items[ this.count] = data
        this.count ++ 
    }

    dequeue(){if(this.isEmpty()) {return undefined}
        const result = this.items[this.lowestCount]
        delete this.items[this.lowestCount] 
        this.lowestCount ++ 
        return result
    }

    peek(){if(this.isEmpty()) {return undefined}  

        return this.items[this.lowestCount]
    }

    isEmpty(){return this.size() === 0
    }

    size () {return this.count - this.lowestCount}

    clear(){
        this.count = 0; 
        this.lowestCount = 0;  
        this.items = {}}
}

队列的利用场景：能够试想一个 javascript 的事件循环、其实底层就是听从先进先出的实现原理。

进阶版：双端队列

容许咱们同时在 前端和后端增加和移除的元素 的非凡队列，仔细的童鞋能够实现的形式其实是交融了 栈和 队列 的办法。请看以下代码：

class Deque {constructor(){
        this.count = 0; // 记录对象的 size
        this.lowestCount = 0;   // 跟踪第一个元素
        this.items = {} // 初始化对象}
    // 在队列前端增加元素
    addFront(data) {if(this.isEmpty()) {this.addBack(data)
        }else if(this.lowestCount > 0) {
            this.lowestCount -- 
            this.items[this.lowestCount] = data
        }else {for (let i = this.count; i > 0 ; i--) {this.items[i] = this.items[i - 1]
            }
            this.count ++;
            this.lowestCount = 0;
            this.items[0] = data
        }
        
    }
    // 在队列后端增加元素
    addBack(data) {this.items[ this.count] = data
        this.count ++ 
    }

    // 在队列后端删除元素
    removeBack() {if(this.isEmpty()) {return undefined}

        this.count -- 
        const result = this.items[this.count]
        delete this.items[this.count]
        return result
    }

    // 在队列前端删除元素
    removeFront(){if(this.isEmpty()) {return undefined}

        const result = this.items[this.lowestCount]
        delete this.items[this.lowestCount] 
        this.lowestCount ++ 
        return result
    }

    // 返回在队列前端第一个元素
    peekBack() {if(this.isEmpty()) {return undefined}
        return this.items[this.count - 1]
    }

    // 返回在队列后端第一个元素
    peekFront(){if(this.isEmpty()) {return undefined}  

        return this.items[this.lowestCount]
    }

    // 是否回空
    isEmpty(){return this.size() === 0
    }

    // 队列大小
    size () {return this.count - this.lowestCount}

    // 革除队列
    clear(){
        this.count = 0; 
        this.lowestCount = 0;  
        this.items = {}}
}

通过一个例子在深刻理解一下它的底层原理实现：

验证简略的回文数

let strings = `madam`

function isPalindrome(aString) {const deque = new Deque()
    const lowerString = aString.toLocaleLowerCase().split('').join('')

    let isEqual = true;
    let firstChar, lastChar;

    for (let i = 0; i < aString.length; i++) {deque.addBack(lowerString.charAt(i))
    }

    while (deque.size() > 1 && isEqual) {firstChar = deque.removeFront()
        lastChar = deque.removeBack()

        if(firstChar !== lastChar) {isEqual = false}
    }

    return isEqual
}

以上就是内容介绍了 JavaScript 的最简略的数据结构，其实万变不离其宗只有从底层把握了数据结构的各种演变的状态，利用它们的个性和实现的原理，那么遇到一些难解的问题的时候就有很多的发散性想法，当然也是咱们在解决数据结构的必须把握的方法论。

最初

本文系列参照《学习 JavaScript 数据结构与算法第 3 版》进行的整顿演绎、心愿能帮忙大家。

正文完
前端
发表至： 前端
2021-06-22
 0
mapboxgl中style的规范属性transition
关于前端:前端工程师-2022-年必备的-7-个工具
关于前端:移动端长按事件模拟vue指令封装
关于前端:从0到1搭建自己的组件vuecodeview库上

站内搜索

-「」