javascript入门到进阶 - js系列一：三种基本的数据结构
javascript入门到进阶 - js系列一：三种基本的数据结构
做一件事首先有三个步骤：第一步：是什么，也就是 what 第二步：为什么，也就是 why 第三步：如何应用，也就是 how
「栈」如果说要单单从子面去理解，肯定是死活不知道「栈」到底是个什么样的东西，到底长成什么样子，有什么作用。在此之前，我们先来说说 「栈」 的规则， 「栈」 其实是遵循“先进后出”的规则，所以我们可以从生活中的例子去理解这个「栈」 这个概念，我把抽象具体化，我把「栈」 具体化成 我们平时打羽毛球时的「羽毛球筒」 ，上图
我们的羽毛球是怎么放进羽毛球筒的呢，或者怎么取出羽毛球的，是不是遵循刚才那个规则，「先进后出」（就跟吃饭拉屎一个道理）。我们先放的羽毛球是不是被放在最下面呢（我们叫他「栈底」），我们最后放的就被放在最上面（我们叫他「栈顶」）「我就把羽毛球筒当成栈」「最经典的一个例子就是 js 中的 数组，他就是一个典型的栈类型的数据结构的具体实现」那么数组是怎么样获取元素的呢：我们当然可以使用索引的方式：
var arr = ["ken","Ken","coding"];
arr[0] ==> 栈底
arr[1]
arr[2] ==> 栈顶
对应获取栈底的方法为 pop(就是弹出数组最末尾的元素)
arr.pop()
对应添加末尾的元素的方法为 push (向数组末尾添加元素)
arr.push("hahah")
总的来说 1 栈是一种数据结构，他表达了数据的一种存取方式 2 栈可用来规定代码的执行顺序，在javascript中叫做函数调用栈 3 栈表达的是一种数据在内存中的存储空间，通常叫栈区。
大家在进行javascript开发的时候，有没有想过，我们写的代码是怎么样运行的呢？下面我们就来剖析一下代码的执行过程。
「一 什么是调用栈」代码在运行过程中，会有一个叫做调用栈(call stack)的概念。调用栈是一种栈结构,它用来存储计算机程序执行时候其活跃子程序的信息。（比如什么函数正在执行，什么函数正在被这个函数调用等等信息）。调用栈是解析器的一种机制。call stack
我们以一段简单代码为示例，来看一看到底什么是调用栈，它是一个怎么样的运行机制
function boo (a) {
return a * 3
}
function foo (b) {
return boo(4) * 2
}
console.log(foo(3))
二 详解代码执行
下面我们来分析一下上述代码的执行过程
- （1）console.log(foo(3)) 执行，形成一个栈帧，调用foo函数，再形成另一个栈帧。
- （2）新的栈帧压在上一个栈帧之上，继续执行代码，foo函数中又调用了boo函数，形成了另一个栈帧压在旧栈帧之上。然后执行boo。
- （3）当执行完boo时候，返回值给foo函数之后,boo被推出调用栈,foo函数继续执行，然后foo函数执行完，返回值给console.log,foo函数被推出调用栈，console.log得到foo函数的返回值，运行，输出结果，最后console.log也被推出调用栈，该段程序执行完成。
图解代码运行过程：图片描述
在这里插入图片描述
三 一个更复杂的例子
// 省略一部分html
<button>click</button>
$.on('button', 'click', function onClick() {
setTimeout(function timer() {
console.log('You clicked the button!');
}, 0);
});
console.log("Hi!");
setTimeout(function timeout() {
console.log("Click the button!");
}, 5000);
console.log("My Name Is Chirs.")
大家看看上叙的代码，结合一下前面的的分析，思考一下调用栈是怎么工作的？
- （1）先运行绑定事件函数，把onClick事件绑定在button标签上。该函数没有没有调用其他函数。
- （2）接下来运行console.log("hi"),该函数没有调用任何其他函数。
- （3）然后继续执行下面的setTimeout，setTimeout是一个异步函数，经过5秒之后，在运行队列里面插入这个回调函数，然后如果该队列之前没有其他函数，就执行该队列，有则等待前面的函数执行完成，再执行。
- （4）console.log("My Name Is Chirs")不会等待5s之后，再执行，因为settimeout并不会在调用栈中执行5秒，实际上它在调用栈中是立即执行完的。
- （5)假设在这个时候，我们点击了按钮，按钮绑定的回调事件被添加到运行队列中。（运行队列中的代码要等调用栈被清空之后才会执行）由于调用栈中还有代码需要执行，所以会继续执行下面的console.log(）
- （6）然后执行完console.log之后，由于时间还没有经过5s,所以点击的回调事件会被先压入栈中去执行，由于该回调事件里面又是一个settimeout事件，由于它的事件间隔只有0s，所以这个settimeout的回调会先被压入运行队列。先输出You clicked the button! 再过几秒之后，间隔为5s的settimeout把回调函数压入队列，这时候调用栈中没有代码在执行，所以会执行这个代码，输出"Click the button“。结束代码运行。
同样来看一个运行示意图：
四 总结 调用栈其实就是一种解析器去处理程序的机制，它是栈数据结构。它能追踪子程序的运行状态。（1）当脚本要调用一个函数时，解析器把该函数添加到栈中并且执行这个函数。并形成一个栈帧 （2）任何被这个函数调用的函数会进一步添加到调用栈中，形成另一个栈帧,并且运行到它们被上个程序调用的位置。（3）当执行完这个函数后，如果它没有调用其他函数，则它会从调用栈中推出。然后调用栈继续运行其他部门。（4) 异步函数的回调函数一般都会被添加到运行队列里面，如settimeout会在响应的时间后把回调函数放入队列中，队列里的函数需要等栈为空时才会被推入栈中执行。如果队列中有其他函数，需要等队列前面的函数被堆入调用栈中之后才会运行。
「堆」堆数据结构其实是一种树状结构
var obj = {
"name": "Ken",
"work": "Coder",
"sex": "男",
"age": "永远18",
"hobby": "摄影，健身，跑步"
}，
堆可以理解成一种无序的东西，就像我们农村中的谷堆一样，你可以从任何一个位置拿走一粒谷，但是你不清楚他所在的位置。深入理解“堆”和对象本质
「队列」队列这个东西是我们再熟悉不过了，平时买东西的排队，坐地铁排队候车，有个规则就是“先进先出”。队列：彻底理解队列 什么是队列 先进者先出，就是"队列" 我们可以想象成，排队买票，先来的先买，后来的只能在末尾，不允许插队。
队列的两个基本操作：入队 将一个数据放到队列尾部；出队 从队列的头部取出一个元素。队列也是一种操作受限的线性表数据结构 它具有先进先出的特性，支持队尾插入元素，在队头删除元素。
队列的概念很好理解，队列的应用也非常广泛如：循环队列、阻塞队列、并发队列、优先级队列等。
顺序队列 顺序队列都是基于数组的方式实现的，是连续的一块内存空间。如下图
我们看下代码实现，非常简单
public class ArrayQueue<T> {
private Object queue[];
private int head = 0;//队头
private int tail = 0;//队尾
private int n;//数组的容量
public ArrayQueue(int count) {
this.n = count;
queue = new Object[count];
}
public ArrayQueue() {
this(10);
}
/**
* 加入队列
*
* @param t
* @return
*/
public boolean enqueue(T t) {
//表示队列队容量已满
if (tail == n) {
//表示整个队列已经存满了
if (head == 0) {
System.out.println("队列已存满，没有队列移出");
return false;
} else {
System.out.println("队列已满，有队列移出，进行数据搬移，然后插入队列");
//表示还剩 （tail - head）的数据 进行数据搬移 将队头的下标改为从0开始 入队时保证了数组的连续性
for (int i = head; i < tail; i++) {
queue[i - head] = queue[i];
}
//重置队尾的大小等于head
tail -= head;
//重置队头head = 0
head = 0;
}
}
System.out.println("插入队列:" + t);
//加入队列 队尾+1
queue[tail++] = t;
return true;
}
/**
* 移除队列
* 如果每次出队操作 都从下标为0队位置开始，那么每次都要进行数据搬移
* 时间复杂度O(1) 就变成了 O(n),
* 优化：再出队时不进行数据搬移，虽然会导致数组的不连续，
* 当没有空闲当空间时入队时在进行数据搬移，这样也就保持了数组的连续性
*
* @return
*/
public T dequeue() {
//表示队列为空
if (head == tail) return null;
//tail 队尾 从0开始 移除队列 已知
T t = (T) queue[head++];
System.out.println("移除队列:" + t);
return t;
}
}
需要注意的是，正常的思路，当我们每次移出队列的时候，都要进行一次数据搬移，时间复杂度O(1) 变成了 O(n),
for (int i = head; i < tail; i++) {
queue[i - head] = queue[i];
}
如何进行优化呢？在上述的代码中已经给出了答案，出队时不进行数据搬移，虽然会导致数组的不连续，入队时当没有空闲当空间时也就是tail == n 入队时在进行数据搬移，这样也就保持了数组的连续性,同时也解决了频繁的入队、出队操作，导致的频繁的数据搬移。
如下图所示：
核心代码如下：
if (tail == n) {
//表示整个队列已经存满了
if (head == 0) {
System.out.println("队列已存满，没有队列移出");
return false;
} else {
System.out.println("队列已满，有队列移出，进行数据搬移，然后插入队列");
//表示还剩 （tail - head）的数据 进行数据搬移 将队头的下标改为从0开始 入队时保证了数组的连续性
for (int i = head; i < tail; i++) {
queue[i - head] = queue[i];
}
//重置队尾的大小等于head
tail -= head;
//重置队头head = 0
head = 0;
}
}
从上述代码和图片中，当队列的tail队尾标志位，移动到数组的最右边后，如果有新的数据入队，将head - tail 之间的数据，整体搬移到数组中的 0 - （tail-head）的位置。
循环队列 上述通过数组来实现的队列，我们虽然进行了优化，但是当tail == n时，还是会进行一次数据搬移，性能也会收到影响，能否避免数据呢？答案是肯定的，看一下循环队列的解决思路。
循环队列就相当于一个圆环，数组可以想象成一条直线，我们吧这条直线掰成一个圆环，就是循环队列，为了更形象的表示，可以看下图所示：
如上图所示，队列的大小为size = 11，队列head指向 5 ，队尾fail指向10，当向队尾添加一个元素F，这时fail = 0，这时再向队尾添加一个元素G，这时fail = 1.队列就变为下图所示
循环队列很显然的避免了数组的搬移操作。
循环队列的难点在于如何确定队空和队满的判定条件以及head和fail的变化.
总结一下规律，fail的变化，当fail=10，如何让fail = 0呢？很显然 fail = (fail+1)%size; 那么head同理也遵循这样的变化head=(head+1)%size.
如何判定队满呢？从上面的规律来看，我们可以发现(fail+1)%size == head的时候，队列就满了，但是fail指向的位置实际上是没有数据的，这就意味这循环队列浪费了一个存储空间，以空间换取时间。
下面就是，show time代码时间，理解了上面的思路，代码就很好实现了。
public class CycleQueue<E> {
private Object cQ[];
private int head = 0;
private int tail = 0;
private int size;
public CycleQueue(int size) {
this.size = size;
cQ = new Object[size];
}
public CycleQueue() {
this(10);
}
public boolean enqueue(E e) {
//表示队列满了
if ((tail+1) % size == head) return false;
cQ[tail] = e;
tail = (tail + 1) % size;
return true;
}
public E dequeue() {
if (head == tail) return null;
E o = (E) cQ[head];
head = (head + 1) % size;
return o;
}
}
链式队列
基于链表的实现队列，同理也需要两个指针标志这队头和队尾，如下图所示：
449ED9D2-1994-45E0-A852-5BD3CFF86FD4.png
代码很简单，如下：
public class LinkedQueue<E> {
private int size;
//队头
private Node<E> head;
//队尾
private Node<E> tail;
public LinkedQueue() {
}
public boolean enqueue(E value) {
if (tail == null) {//表示队列是空队列 插入第一个
Node<E> eNode = new Node<>(null, value);
head = eNode;
tail = eNode;
} else {
Node temp = tail;
tail = new Node<>(null, value);
temp.next = tail;
}
size++;
return true;
}
public E dequeue() {
if (head == null) return null;
E value = null;
if (head.next != null) {
value = head.value;
head = head.next;
} else {//临界点 队列只剩下一个了
value = head.value;
head = null;
}
size--;
return value;
}
public void traversing() {
Node<E> temp = head;
for (int i = 0; i < size; i++) {
System.out.println("value:" + temp.value);
temp = temp.next;
}
}
public static class Node<E> {
public Node<E> next;
public E value;
public Node(Node<E> next, E value) {
this.next = next;
this.value = value;
}
}
}
基于链表实现的队列，支持无限排队的无界队列。
另外还有几种高级的队列结构，阻塞队列、并发队列，阻塞队列就是入队、出队操作可以阻塞，并发队列就是队列的操作多线程安全