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

$.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 {

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 

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 

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 

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 {

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 {

private int size;

//队头

private Node head;

//队尾

private Node tail;

public LinkedQueue() {

}

public boolean enqueue(E value) {

if (tail == null) {//表示队列是空队列 插入第一个

Node 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 temp = head;

for (int i = 0; i 

System.out.println("value:" + temp.value);

temp = temp.next;

}

}

public static class Node {

public Node next;

public E value;

public Node(Node next, E value) {

this.next = next;

this.value = value;

}

}

}

基于链表实现的队列，支持无限排队的无界队列。

另外还有几种高级的队列结构，阻塞队列、并发队列，阻塞队列就是入队、出队操作可以阻塞，并发队列就是队列的操作多线程安全