JavaScript数据结构

一、什么是数据结构?

数据结构是向相互之间存在一种或者多种特定关系的数据组成的集合, 采用合适的数据结构能给开发者提高开发和储存效率.比如我们在学习Es6中的我们新接触的到的(Set, map), 在合适的时候使用它们能帮助我们更快的的解决问题.

我们每个在编码是都会用到数据结构,数据最简单的内存数据结构,下面是常用的数据结构

1. 栈 (Stack)
2. 队列 (Queue)
3. 链表(Linked List)
4. 集合(assemble)
5. 字典(Dict)
6. 哈希表(HashTable)
7. 树 (Tree)
8. 图(Map)

二、 栈

1.创建栈的结构

栈是一种遵循后进先出(LIFO)原则的有序数据集.新添加的元素或带删除的元素都保存再去在栈的同一端,叫做栈顶, 另一端就叫做栈顶,在栈里, 新元素都接近栈顶, 旧元素都在栈顶.

栈是一种特殊的线性表, 它只能在一个表的固定端进行数据节点的插入和删除操作.栈按照先进后出的原则,也就是说先插入的元素将被压入栈顶,最后插入的元素在栈顶. 可以类比我们现实生活中的物件,例如一摞书或者堆放在一起的盘子

普通的栈大概有以下的需求

1. 添加数据(push)
2. 返回栈顶元素(peek)
3. 从栈顶中删除栈顶元素并返回()
4. 清空栈(clear)
5. 返回栈中数据的个数(size)
6. 返回栈中是否有无元素(isEmpty), 无元素返回true,否者返回false

class Stack{
    constructor(){
        this.items = []
    }
    // 添加数据
    push(...rest){
        rest.forEach(v=>this.items.push(v));
        return this.items.length;
    }
    // 返回栈顶数据
    peek(){
        return this.items[this.items.length-1]
    }
    // 删除栈顶元素并返回
    pop(){
        return this.items.pop()
    }
    // 清空栈
    clear(){
        this.items = []
    }
    // 返回栈的长度
    size(){
        return this.items.length;
    }
    // 返回栈是否为空
    isEmpty(){
        return this.items.length === 0 ? true : false
    }
}

下面我们简单测试一下

let stack1 = new Stack();
stack1.push(1,2,3,4)
console.log(stack1.peek());//4
console.log(stack1.pop());//4
console.log(stack1.pop());//3
console.log(stack1.pop());//2
console.log(stack1.pop());//1
console.log(stack1.size())//0
console.log(stack1.isEmpty())// true

上面的栈结构有一个问题就是类的外部可以直接通过Stack实例对象的items直接访问到对应的数据,显然这并不安全,不符合开闭原则, 我们可以闭包和Symbol来避免外界直接访问到.

let Stack = (function () {
    let data = {};
    return class {
        constructor() {
            this.sym =   Symbol("key");
            data[this.sym] = []
        }
        // 添加数据
        push(...rest) {
            rest.forEach(v =>  data[this.sym].push(v) );
            return data[this.sym].length;
        }
        // 返回栈顶数据
        peek() {
            return data[this.sym][ data[this.sym].length - 1]
        }
        // 删除栈顶元素并返回
        pop() {
            return  data[this.sym].pop()
        }
        // 清空栈
        clear() {
            data[this.sym] = []
        }
        // 返回栈的长度
        size() {
            return data[this.sym].length;
        }
        // 返回栈是否为空
        isEmpty() {
            return data[this.sym].length === 0 ? true : false
        }
        // 打印栈的数据
          print(){
            data[this.sym].forEach(item =>{
                console.log(item)
            })
        }
    }
})()

利用Symbol的特性来生成一个独一无二的key,确保了数据的唯一性.并将其数据保存在data中,实例上只有一个sym属性暴露在外面, 将数据利用闭包保存在data上 使得外部无法访问到数据.

2. 栈结构的应用

2.1进制转换

js自带机制转换的Api, 此案例并不实用, 仅仅作为理解原理;

分析: 进制转换的本质就是: 将目标值一次一次除以进制基数, 得到的取整为新目标值,并记录下余数, 直至目标值小于0,最后将余数逆序组合即可,利用栈,记录余数入栈, 组合是出栈.

function baseConverter2(number){
    let stack = new Stack();
    // 保存最终的返回值
    let result = "";
    //取出所有余数
    while(number>0){
        // 余数入栈
        stack.push(number%2);
        // 每次取商
        number = Math.floor(number/2);
    };
    // 余数出栈
    while(stack.size()){
        result += stack.pop();
    };
    return result || "0"
}
// 16进制转换
function baseConverter16(number,base=2) {
    let stack = new Stack();
    //六进制中需要依次对应A~F
    let sign = "0123456789abcdef";
    let result = "";
    while (number>0){
        let remainder = number%base;
        stack.push(sign[remainder]);
        number = Math.floor(number/base);
    }
    while(stack.size()){
        result += stack.pop();
    }
    return result||"0";
}
console.log(baseConverter16(15,16));//f

2.2判断回文字符串

分析 回文字符串表示正读反读都是一样的字符串, 判断一个字符串是否为回文字符

最简单的方法就是将字符串反转, 然后判断新的字符串是否等于原字符串即可,我们可以利用栈的先进后出的特性可以和很方便的反转一个字符串,因为先进后出的特性,我们可以和方便的取出字符串从后往前依次的每个字符并拼接在一起,然后与原字符串进行比较即可.

// 判断回文
function isPlalindrome(word){
    // 限定参数的类型为字符串,且不能为空
    if(!word || typeof word != "string"){
        throw new TypeError('the arguments type if not String or null');
        return false
    }
    let stack = new Stack();
    // 用于与原字符串比较的新字符串
    let back = "";
    // 入栈 将字符串通过...语法展开字符串
    stack.push(...word);
    //从后往前依次出栈
    while(stack.size()){
        back += stack.pop()
    }
    // 判断并返回新字符串和老字符串是否相等
    return back === word
}
//利用数组的reverse方法将字符串反转
function test(str){
   return  [...str].reverse().join("") === str
} 
console.log(isPlalindrome('我爱你爱我'));// true
console.log(isPlalindrome("123456"));// false

2.3 括号匹配

括号匹配是栈应用中比较经典的问题,它的问题描述具体如下

给定一个字符串，里边可能包含“()”、"{}"、“[]”三种括号，请编写程序检查该字符串的括号是否成对出现。

输出true: 代表括号成对出现并且嵌套正确, 或字符串无括号字符

输出false: 表示为正确使用括号字符

分析: 依次检测给定的字符串, 若是左括号就入栈, 如果是右括号就与栈顶元素进行匹配, 匹配成功则继续访问下一个字符, 否者返回false.

function ifSignMatch(str){
    let leftSign = "{[(",
        rightSign = "}])";
    let stack = new Stack();
    // 依次遍历字符串每个字符
    for(let i =0,len = str.length; i<len; i++){
        let char = str.charAt(i);
        //检测是否有左括号
        if(leftSign.indexOf(char) !== -1){
            // 入栈
            stack.push(char)
        }
        // 检测是否有右括号
        else if(rightSign.indexOf(char) !== -1){
            // 判断当前栈顶符号是否与当前符号匹配,如果不匹配则返回false
            if(leftSign.indexOf(stack.pop()) !== rightSign.indexOf(char)){
                return false
            }
        }
    }
    // 返回栈是否为空, 当栈为空说明匹配成功 返回true
    return stack.isEmpty()
}
console.log(ifSignMatch("{[{}]}"));// true
console.log(ifSignMatch("{[{]}"));// false

总结:栈作为一种数据结构,是一种只能在一段进行插入删除操作的特殊线性表.栈的体性就是先进后出.这种体性在计算机中有着广泛的运用,其实我们程序员无时无刻不在使用栈,函数的调用是我们间接使用栈的最好的例子.