数据结构与算法是什么？
前言
计算机是现代社会中用于解决问题的重要工具，支撑这个工具高效运转的就是其后的各种系统程序、应用程序。数据结构，是抽象的表示数据的方式；算法，则是计算的一系列有效、通用的步骤。算法与数据结构是程序设计中相辅相成的两个方面，是计算机学科的重要基石。 [1]
一、算法是什么？
算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制
也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出
如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题
一个程序=算法+数据结构，数据结构是算法实现的基础，算法总是要依赖于某种数据结构来实现的，两者不可分割
因此，算法的设计和选择要同时结合数据结构，简单地说数据结构的设计就是选择存储方式，如确定问题中的信息是用数组存储还是用普通的变量存储或其他更加复杂的数据结构
针对上述，可以得出一个总结：不同的算法可能用不同的时间、空间或效率来完成同样的任务
应用场景
在前端领域中，数据结构与算法无法不在，例如现在的vue或者react项目，实现虚拟DOM或者Fiber结构，本质就是一种数据结构，如下一个简单的虚拟DOM：
{
type: 'div',
props: {
name: 'lucifer'
},
children: [{
type: 'span',
props: {},
children: []
}]
}
vue与react都能基于基于对应的数据结构实现diff算法，提高了整个框架的性能以及拓展性
二、数据结构是什么
数据结构是计算机存储、组织数据的方式，是指相互之间存在一种或多种特定关系的数据元素的集合
前面讲到，一个程序 = 算法 + 数据结构，数据结构是实现算法的基础，选择合适的数据结构可以带来更高的运行或者存储效率
数据元素相互之间的关系称为结构，根据数据元素之间关系的不同特性，通常有如下四类基本的结构：
集合结构：该结构的数据元素间的关系是“属于同一个集合”
线性结构：该结构的数据元素之间存在着一对一的关系
树型结构：该结构的数据元素之间存在着一对多的关系
图形结构：该结构的数据元素之间存在着多对多的关系，也称网状结构
由于数据结构种类太多，逻辑结构可以再分成为：
线性结构：有序数据元素的集合，其中数据元素之间的关系是一对一的关系，除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的
非线性结构：各个数据元素不再保持在一个线性序列中，每个数据元素可能与零个或者多个其他数据元素发生关联
常见的数据结构有哪些？
常见的数据结构有如下：
数组
栈
队列
链表
树
图
堆
散列表
数组
在程序设计中，为了处理方便， 一般情况把具有相同类型的若干变量按有序的形式组织起来，这些按序排列的同类数据元素的集合称为数组
栈
一种特殊的线性表，只能在某一端插入和删除的特殊线性表，按照先进后出的特性存储数据
栈（stack）又名堆栈，它是一种运算受限的线性表，限定仅在表尾进行插入和删除操作的线性表
表尾这一端被称为栈顶，相反地另一端被称为栈底，向栈顶插入元素被称为进栈、入栈、压栈，从栈顶删除元素又称作出栈
所以其按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据，具有记忆作用
先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据
简单的栈实现如下：
class Stack {
constructor() {
this.items = [];
}
/**
* 添加一个（或几个）新元素到栈顶
* @param {*} element 新元素
*/
push(element) {
this.items.push(element)
}
/**
* 移除栈顶的元素，同时返回被移除的元素
*/
pop() {
return this.items.pop()
}
/**
* 返回栈顶的元素，不对栈做任何修改（这个方法不会移除栈顶的元素，仅仅返回它）
*/
peek() {
return this.items[this.items.length - 1]
}
/**
* 如果栈里没有任何元素就返回true,否则返回false
*/
isEmpty() {
return this.items.length === 0
}
/**
* 移除栈里的所有元素
*/
clear() {
this.items = []
}
/**
* 返回栈里的元素个数。这个方法和数组的length属性很类似
*/
size() {
return this.items.length
}
}
使用pop方法出栈，push方法入栈
队列
跟栈基本一致，也是一种特殊的线性表，其特性是先进先出，只允许在表的前端进行删除操作，而在表的后端进行插入操作
进行插入操作的端称为队尾，进行删除操作的端称为队头，当队列中没有元素时，称为空队列
在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出
简单实现一个队列的方式，如下：
class Queue {
constructor() {
this.list = []
this.frontIndex = 0
this.tailIndex = 0
}
enqueue(item) {
this.list[this.tailIndex++] = item
}
unqueue() {
const item = this.list[this.frontIndex]
this.frontIndex++
return item
}
}
上述这种入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用
当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作，出该现象称为"假溢"
在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进：
无论插入或删除，一旦rear指针增1或front指针增1 时超出了所分配的队列空间，就让它指向这片连续空间的起始位置，这种队列也就是循环队列
下面实现一个循环队列，如下：
class Queue {
constructor(size) {
this.k = size; // 长度需要限制, 来达到空间的利用, 代表空间的长度
this.list = [];
this.font = 0; // 指向首元素
this.rear = 0; // 指向准备插入元素的位置
}
enQueue() {
if (this.isFull() == true) {
return false
}
this.rear = this.rear % this.k;
this._data[this.rear++] = value;
return true
}
deQueue() {
if(this.isEmpty()){
return false;
}
this.font++;
this.font = this.font % this.k;
return true;
}
isEmpty() {
return this.font == this.rear - 1;
}
isFull() {
return this.rear % this.k == this.font;
}
}
队列的使用广泛应用在广度优先搜索中，例如层次遍历一个二叉树的节点值
生活中的例子，排队买票，排在队头的永远先处理，后面的必须等到前面的全部处理完毕再进行处理，这也是典型的先进先出模型
链表
是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的
链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成
一般情况，每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域
链表（Linked List）是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的，由一系列结点（链表中每一个元素称为结点）组成
每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域
节点用代码表示，则如下：
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)
链表的结构也十分多，常见的有四种形式：
单链表：除了头节点和尾节点，其他节点只包含一个后继指针
循环链表：跟单链表唯一的区别就在于它的尾结点又指回了链表的头结点，首尾相连，形成了一个环
双向链表：每个结点具有两个方向指针，后继指针(next)指向后面的结点，前驱指针(prev)指向前面的结点，其中节点的前驱指针和尾结点的后继指针均指向空地址NULL
双向循环链表：跟双向链表基本一致，不过头节点前驱指针指向尾迹诶单和尾节点的后继指针指向头节点
树
树是典型的非线性结构，在树的结构中，有且仅有一个根结点，该结点没有前驱结点。在树结构中的其他结点都有且仅有一个前驱结点，而且可以有两个以上的后继结点
图
一种非线性结构。在图结结构中，数据结点一般称为顶点，而边是顶点的有序偶对。如果两个顶点之间存在一条边，那么就表示这两个顶点具有相邻关系
堆
堆是一种特殊的树形数据结构，每个结点都有一个值，特点是根结点的值最小（或最大），且根结点的两个子树也是一个堆
散列表
若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上，不需比较便可直接取得所查记录