做一件事首先有三个步骤:第一步:是什么,也就是 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;
}
}
}
基于链表实现的队列,支持无限排队的无界队列。
另外还有几种高级的队列结构,阻塞队列、并发队列,阻塞队列就是入队、出队操作可以阻塞,并发队列就是队列的操作多线程安全
领取专属 10元无门槛券
私享最新 技术干货