数据结构的那些事（一）-白红宇

前端早已不是当年的切图仔了。想要升职加薪，进军大厂，在前端的路上走的更远，你不得不了解一下数据结构。

常用的数据结构有：数组，列表，栈，队列，链表，字典，散列表，树，图。

我们会在接下来一个一个的介绍，并且实现它们！

1.数组：最常见也是用的最多的数据结构就是数组了。它通过索引来实现元素的任意存储。

大多数语言都有数组，值得一提的是，JavaScript中的数组是一种特殊的对象，因此索引在内部会被转换成字符串类型，所以效率会有所折扣。

因为数组大家了解的比较多，在这里只提下数组的迭代器方法：

不生成新数组的迭代器方法：

forEach():接收一个函数作为参数，对数组中每个元素使用该函数every()：接收一个返回值为布尔值的函数，遍历数组，对于所有函数返回true，该方法返回truesome()：接收一个返回值为布尔值的函数，遍历数组，只要有一个函数返回true，该方法返回truereduce():使用接收的函数操作数组，最后返回一个结果复制代码

生成新数组的迭代器方法

map()filter()复制代码

2.列表：适用于保存元素不多，不需要在一个很长的序列中查找元素，或对其排序。

列表是一组有序的数据，每个列表中的数据项称为元素。首先我们来设计一下这个列表应该具有哪些属性和方法：

function List() {    this.listSize = 0;    this.pos = 0;    this.dataStore = []; // 初始化一个空数组来保存列表元素    this.clear = clear;    this.find = find;    this.toString = toString;    this.insert = insert;    this.append = append;    this.remove = remove;    this.front = front;    this.end = end;    this.prev = prev;    this.next = next;    this.length = length;    this.currPos = currPos;    this.moveTo = moveTo;    this.getElement = getElement;    this.length = length;    this.contains = contains;}复制代码

当我们设计好一个列表类后，接下来开始实现里面的方法：

//appendfunction append(e){    this.dataStore[this.listSize++] = e;}//remove方法要求我们首先要找到删除的元素，我们需要一个辅助方法find()function find(e){    for(let i = 0; i
    
      -1){        this.dataStore.splice(findCode, 1);        --this.listSize;        return true;    }    return false;}//insert 向列表中插入一个元素function insert(e, where){    let insetPos = this.find(where);    if(insertPos > -1){        this.datastore.splice(insertPos+1, 0 , e);        ++this.listSize;        return true;    }    return false;}//lengthfunction length(){    return this.listSize;}//清空列表中的元素function clear(){    delete this.dataStore;    this.dataStore = [];    this.listSize = this.pos = 0;}//cotains判断给定值是否在列表中function coatains(e){    for(let i = 0; i

最后，我们还需要一组方法来遍历列表

function front() {    this.pos = 0;}function end() {    this.pos = this.listSize-1;}function prev() {    if (this.pos > 0) {        --this.pos;    }}function next() {    if (this.pos < this.listSize-1) {        ++this.pos;    }}function currPos() {    return this.pos;}function moveTo(position) {    this.pos = position;}function getElement() {    return this.dataStore[this.pos];}复制代码

到这里，我们就自己实现了一个列表类。有自己的属性，可以增删改查，可以遍历。

3.栈：栈是和列表类似的一种数据结构，但是它遵循后进先出的规则

因为数据只能在栈顶添加或删除，所以这样的操作很快，而且容易实现。对栈的两种主要操作是将一个元素压入栈和讲一个元素弹出栈，另一个常用操作是访问栈顶元素。一样的，在实现之前，我们先来设计一下栈应该具有的属性和方法：

function Stack() {    this.dataStore = [];//存储    this.top = 0;//栈顶    this.push = push;//入栈操作    this.pop = pop;//出栈操作    this.peek = peek;//获取栈顶元素}复制代码

接下来我们来实现这些方法：

function push(e){    this.dataStore[this.top++] = e;}function pop(){    return this.dataStore(--this.top);}function peek(){    return this.dataStore[this.top - 1];}复制代码

有时候需要知道栈内存储元素个数，可以定义一个length方法：

function length(){    return this.top}复制代码

清空栈也很简单：

function clear(){    this.top = 0;}复制代码

适合使用栈的场景：

（1）数制间的相互转换

eg:将数字转换为二进制和八进制function changeBase(num, base){    let s = new Stack();    do{        s.push(num % base);        num = Math.floor(num /= base);    }while(num > 0)    let convert = "";    while(s.length() > 0){        convert += s.pop();    }    return convert;}复制代码

（2）回文：回文指从前往后写和从后往前写都是一样的结构。使用栈可以轻松地判断一个字符串是否是回文。

字符串完整压入栈内后，通过持续弹出栈中的每个字母就可以得到一个新的字符串，该字符串刚好与原来的字符串顺序相反。我们只需要比较这连个字符串是否一样即可判断是不是回文。

（3）用栈来模拟递归

function fact(n){    let s = new Stack();    while(n > 1){        s.push(n--);    }    let product = 1;    while(s.length() > 0){        product *= s.pop();    }    return product;}复制代码

避免一篇博客过长，我会将数据结构分成几篇来写，喜欢的帮忙点个赞，给博主一点动力~~