前端应该了解的数据结构-栈与队列

喜欢ヅ旅行 2022-01-19 03:07 256阅读 0赞

# 一、为什么需要学习数据结构？ #

## 1、编程思维是相通的 ##

人们常说，编程语言是相通的，掌握了一门，其他语言很容易掌握。个人觉得这个观点需要辩证看待。

每门编程语言都离不开变量、数组、条件判断、循环等知识概念，这似乎能支持上面的观点。但是，每种编程语言都有自己的适用范围，都有自己的优缺点。像nodejs这种语言适合I/O密集型、并发大的应用，但也有不能胜任的工作，比如机器学习。像python这样近乎万能的语言，也总有无能为力的时候，比如面对高性能计算，许多python库的底层都是C语言实现。

从事前端开发2年多，我越来越觉得真正相通的不是语言，而是编程思维——数据结构和算法。数据结构和算法是脱离编程语言存在的，不同语言有不同的实现方式，但内在的逻辑和编程思想是一致的。

## 2、高质量编码离不开数据结构做指导 ##

我曾在工作中有过这样一次经历，在使用socket.io接收后端发送的socket连接数据，页面渲染推送消息提示时，后端有可能同时推送很多消息过来，无法完全呈现给用户。当时产品要求实现同一时刻同一用户接收的消息最多5条，多余5条消息不再叠加显示。

于是我们前端使用队列知识，当同一时刻接收到后端推送过来超过5条消息，使用shift()方法截取消息队列中的首条消息渲染消息提示，解决了过多消息重叠的问题，实现产品功能。从此，我就开始对数据结构和算法产生了深入研究的兴趣。

# 二、数据结构——栈 #

## 1、栈的定义 ##

**栈**，是限定仅在表尾进行插入和删除操作的线性表，允许插入和删除的一端称为栈顶，另一端称为栈底，有着后进先出（last in first out）的特性。

日常生活中有很多栈的例子，例如，一叠摞在一起的盘子，要从这叠盘子中取出或放入一个盘子，只有在其顶部操作是最为方便的。

## 2、栈的实现 ##

我们写一个栈，是为了使用它，那么必须先定义数据存储在哪里，提供什么方法实现。

### 2.1 数据存储 ###

从数据存储的角度来看，实现栈有2种方式，一种是以数组为基础，一种是以链表做基础。数组是大家平时使用最频繁，最为了解熟悉的数据类型，我们就以数组为示例，展开研究。 我们先定义一个简单的Stack类，数据存储在items数组中。

function Stack() {
        var items = [];// 使用数组存储数据
    }
    复制代码

### 2.2 栈的方法 ###

栈有以下几个方法：

*  push 添加一个元素到栈顶（向一叠盘子放入一个盘子）
 *  pop 弹出栈顶元素（从一叠盘子取出一个盘子）
 *  top 返回栈顶元素，注意不是弹出（看一眼最顶端的盘子，但是不拿）
 *  isEmpty 判断栈是否为空（看盘子是不是都用完了）
 *  size 返回栈里元素的个数（数一下一叠盘子有多少盘子）
 *  clear 清空栈（把一叠盘子都扔掉）

#### 2.2.1 push方法 ####

// push方法向栈压入一个元素
    this.push = function(item) {
        items.push(item);
    }
    复制代码

#### 2.2.2 pop方法 ####

// pop方法把栈顶的元素弹出
    this.pop = function() {
        return items.pop();
    }
    复制代码

#### 2.2.3 top方法 ####

// top方法返回栈顶元素
    this.top = function() {
        return items[items.length-1];
    }
    复制代码

#### 2.2.4 isEmpty方法 ####

// isEmpty返回栈是否为空
    this.isEmpty = function() {
        return items.length == 0;
    }
    复制代码

#### 2.2.5 size方法 ####

// size返回栈的大小
    this.size = function() {
        return items.length;
    }
    复制代码

#### 2.2.6 clear方法 ####

// clear清空栈
    this.clear = function() {
        items = [];
    }
    复制代码

## 3、栈的应用 ##

### 3.1 计算逆波兰表达式 ###

#### 3.1.1 题目要求 ####

逆波兰表达式，也叫后缀表达式，它将复杂的表达式转换为可以依赖简单操作得到计算结果的表达式，例如(a+b) \* (c+d) = ab+cd+ \*。 示例：

["4","13","5","/","+"] 等价于(4+(13/5)) = 6
    复制代码

请编写函数calc\_exp(exp)实现逆波兰表达式计算结果，exp的类型是数组。

#### 3.1.2 思路分析 ####

\["4","13","5","/","+"\]就是一个数组，在数组层面思考解题思路，遇到/时，把13和5拿出来计算，然后把13和5删除，并把结果放到4的后面，天呐，这样解题思路有些复杂。 如果使用栈的特性来解决这个问题，一切都简单明了，使用for循环遍历数组，对每个元素做如下操作：

*  如果元素不是+ - \* /中的某一个，就压入栈中
 *  如果元素是+ - \* /中的某一个，则从栈里连续弹出2个元素，并对这2个元素进行计算，将计算结果压入栈中 for循环结束之后，栈里只有一个元素，这个元素就是整个表达式的计算结果。

#### 3.1.3 实现代码 ####

# 三、数据结构——队列 #

## 1、队列的定义 ##

**队列**，是只允许在一端进行插入操作，在另一端进行删除操作的线性表。允许插入（也称入队、进队）的一端称为队尾，允许删除（也称出队）的一端称为队头。队列具有先进先出（first in first out）的特性。

日常生活中，排队就是典型的数据结构队列，先排队者先办理事务。

## 2、队列的实现 ##

有了上面栈数据结构做铺垫，队列就容易理解学习了。

### 2.1 数据存储 ###

同栈一样，队列的实现也可以使用数组来存储数据。定义一个简单的Queue类。

function Queue() {
        var items = [];// 存储数据
    }
    复制代码

### 2.2 队列的方法 ###

队列的方法如下：

*  enqueue 从队列尾部添加一个元素（新来的一个排队人，文明礼貌，站在了队伍末尾）
 *  dequeue 从队列头部删除一个元素（队伍最前面的人办理完事务，离开了队伍）
 *  head 返回头部的元素，注意，不是删除（只是看一下，谁排在最前面）
 *  size 返回队列大小（数一数有多少人在排队）
 *  clear 清空队列（队列解散）
 *  isEmpty 判断队列是否为空（看看是否有人在排队）

#### 2.2.1 enqueue方法 ####

// 向队列尾部添加一个元素
    this.enqueue = function(item) {
        items.push(item);
    }
    复制代码

#### 2.2.2 dequeue方法 ####

// 移除队列头部的元素
    this.dequeue = function() {
        return items.shift();
    }
    复制代码

#### 2.2.3 head方法 ####

// 返回队列头部的元素
    this.head = function() {
        return items[0];
    }
    复制代码

#### 2.2.4 size方法 ####

// 返回队列大小
    this.size = function() {
        return items.length;
    }
    复制代码

#### 2.2.5 clear方法 ####

// 清空队列
    this.clear = function() {
        items = [];
    }
    复制代码

#### 2.2.6 isEmpty方法 ####

// 判读是否为空队列
    this.isEmpty = function() {
        return items.length == 0;
    }
    复制代码

## 3、队列的应用 ##

### 3.1 斐波那契数列 ###

斐波那契数列数列是指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368........ ，有着各种各样的解法，比较常见的是递归法，其实也可以使用队列来实现。

#### 3.1.1 题目要求 ####

使用队列计算裴波那契数列的第n项。

#### 3.1.2 思路分析 ####

裴波那契数列的前2项是1 1，此后每一项都是该项前面2项之和，即f(n) = f(n-1)+f(n-2)。如果从数组层面来实现，比较麻烦，因此直接考虑使用队列来实现。 先将两个1添加到队列中，之后使用while循环，使用index计数，循环终止的条件是index < n-2。

*  使用dequeue方法从队列头部删除一个元素，该元素为del\_item
 *  使用head方法获得队列头部的元素，该元素为head\_item
 *  del\_item + head\_item = next\_item， 将next\_item放入队列，注意，只能从尾部添加元素
 *  index+1

#### 3.1.3 实现代码 ####

function fibonacci(n) {
        var queue = new Queue();
        var index = 0;
        // 先放入裴波那契数列的前两个数值
        queue.enqueue(1);
        queue.enqueue(1);
        while(index < n-2) {
            // 取队列第一个元素
            var del_item = queue.dequeue();
            // 取队列头部元素
            var head_item = queue.head();
            // 计算下个元素
            var next_item = del_item + head_item;
            // 将计算结果放入队列
            queue.enqueue(next_item);
            index += 1;
        }
        queue.dequeue();
        return queue.head();
    }
    console.log(fibonacci(8));
    复制代码

# 四、小结 #

栈和队列的底层是不是使用数组实现不重要，重要的是栈有后进先出的特性，队列有先进先出的特性。我们要抓住其数据结构的特性，灵活应用于系统编码中，有效地解决具体问题。

数据结构在系统设计中应用非常广泛，只是我们水平暂未达到那个级别，知道的较少，但如果能理解并掌握数据结构的算法思想，那么就有机会在工作中使用并解决问题，当我们手里除了锤子还有电锯时，那么我们的眼里就不只是钉子，解决问题的思路也会更加开阔，解决方案也会多样化。

转载于:https://juejin.im/post/5cf7c06ff265da1b9612f38a