前端js框架推荐：前端 8种常见数据结构及其JS实现

威哥 2022-11-09 20:37:40 317

前端js框架推荐：前端 8种常见数据结构及其JS实现Javascript中的Array已经具备了Queue的一些特性，所以我们可以借助Array实现一个Queue类型：Queue一般具有以下常见方法：Javascript的Array天生具备了Stack的特性，但我们也可以从头实现一个 Stack类：function Stack() { this.count = 0; this.storage = {}; this.push = function (value) { this.storage[this.count] = value; this.count ; } this.pop = function () { if (this.count === 0) { return undefined; } this.count--; var result = this.storage[this.count]; delete

做前端的同学不少都是自学成才或者半路出家，计算机基础的知识比较薄弱，尤其是数据结构和算法这块，所以今天整理了一下常见的数据结构和对应的Javascript的实现，希望能帮助大家完善这方面的知识体系。

1. Stack（栈）

前端js框架推荐：前端 8种常见数据结构及其JS实现(1)

Stack的特点是后进先出（last in first out）。生活中常见的Stack的例子比如一摞书，你最后放上去的那本你之后会最先拿走；又比如浏览器的访问历史，当点击返回按钮，最后访问的网站最先从历史记录中弹出。

Stack一般具备以下方法：

push：将一个元素推入栈顶
pop：移除栈顶元素，并返回被移除的元素
peek：返回栈顶元素
length：返回栈中元素的个数

Javascript的Array天生具备了Stack的特性，但我们也可以从头实现一个 Stack类：

2. Queue（队列）

前端js框架推荐：前端 8种常见数据结构及其JS实现(2)

Queue和Stack有一些类似，不同的是Stack是先进后出，而Queue是先进先出。Queue在生活中的例子比如排队上公交，排在第一个的总是最先上车；又比如打印机的打印队列，排在前面的最先打印。

Queue一般具有以下常见方法：

enqueue：入列，向队列尾部增加一个元素
dequeue：出列，移除队列头部的一个元素并返回被移除的元素
front：获取队列的第一个元素
isEmpty：判断队列是否为空
size：获取队列中元素的个数

Javascript中的Array已经具备了Queue的一些特性，所以我们可以借助Array实现一个Queue类型：

Priority Queue（优先队列）

Queue还有个升级版本，给每个元素赋予优先级，优先级高的元素入列时将排到低优先级元素之前。区别主要是enqueue方法的实现：

测试一下：

var pQ = new PriorityQueue(); pQ.enqueue(['gannicus' 3]); pQ.enqueue(['spartacus' 1]); pQ.enqueue(['crixus' 2]); pQ.enqueue(['oenomaus' 4]); pQ.print();

结果：

[ [ 'spartacus' 1 ] [ 'crixus' 2 ] [ 'gannicus' 3 ] [ 'oenomaus' 4 ] ]

3. Linked List（链表）

前端js框架推荐：前端 8种常见数据结构及其JS实现(3)

顾名思义，链表是一种链式数据结构，链上的每个节点包含两种信息：节点本身的数据和指向下一个节点的指针。链表和传统的数组都是线性的数据结构，存储的都是一个序列的数据，但也有很多区别，如下表：

比较维度数组链表内存分配

静态内存分配，编译时分配且连续

动态内存分配，运行时分配且不连续

元素获取

通过Index获取，速度较快

通过遍历顺序访问，速度较慢

添加删除元素

因为内存位置连续且固定，速度较慢

因为内存分配灵活，只有一个开销步骤，

速度更快

空间结构

可以是一维或者多维数组

可以是单向、双向或者循环链表

一个单向链表通常具有以下方法：

size：返回链表中节点的个数
head：返回链表中的头部元素
add：向链表尾部增加一个节点
remove：删除某个节点
indexOf：返回某个节点的index
elementAt：返回某个index处的节点
addAt：在某个index处插入一个节点
removeAt：删除某个index处的节点

单向链表的Javascript实现：

/** * 链表中的节点 */ function Node(element) { // 节点中的数据 this.element = element; // 指向下一个节点的指针 this.next = null; } function LinkedList() { var length = 0; var head = null; this.size = function () { return length; } this.head = function () { return head; } this.add = function (element) { var node = new Node(element); if (head == null) { head = node; } else { var currentNode = head; while (currentNode.next) { currentNode = currentNode.next; } currentNode.next = node; } length ; } this.remove = function (element) { var currentNode = head; var previousNode; if (currentNode.element === element) { head = currentNode.next; } else { while (currentNode.element !== element) { previousNode = currentNode; currentNode = currentNode.next; } previousNode.next = currentNode.next; } length--; } this.isEmpty = function () { return length === 0; } this.indexOf = function (element) { var currentNode = head; var index = -1; while (currentNode) { index ; if (currentNode.element === element) { return index; } currentNode = currentNode.next; } return -1; } this.elementAt = function (index) { var currentNode = head; var count = 0; while (count < index) { count ; currentNode = currentNode.next; } return currentNode.element; } this.addAt = function (index element) { var node = new Node(element); var currentNode = head; var previousNode; var currentIndex = 0; if (index > length) { return false; } if (index === 0) { node.next = currentNode; head = node; } else { while (currentIndex < index) { currentIndex ; previousNode = currentNode; currentNode = currentNode.next; } node.next = currentNode; previousNode.next = node; } length ; } this.removeAt = function (index) { var currentNode = head; var previousNode; var currentIndex = 0; if (index < 0 || index >= length) { return null; } if (index === 0) { head = currentIndex.next; } else { while (currentIndex < index) { currentIndex ; previousNode = currentNode; currentNode = currentNode.next; } previousNode.next = currentNode.next; } length--; return currentNode.element; } }

4. Set（集合）

前端js框架推荐：前端 8种常见数据结构及其JS实现(4)