专栏首页志学Pythonjavascript入门到进阶 - 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;
        }
    }
}

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

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

本文分享自微信公众号 - 志学Python(lijinwen1996329ken),作者:志学Python

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 从头创建您自己的vue.js——第4部分(构建反应性)

    状态反应是当应用程序(一组变量)的状态发生变化时,我们做某事(反应)。我们分两步来完成:

    公众号---志学Python
  • 网络基础HTTP协议进化篇

    就像人类已经从猿猴开始慢慢的进化为现在的人类,一开始是只会走路,慢慢就会奔跑,慢慢还会说话,慢慢还会思考,等等到现在的华夏上下5000年的文化,就这样人类一直在...

    公众号---志学Python
  • 利用Python进行数据分析(6) NumPy基础: 矢量计算

    NumPy提供的通用函数(既ufunc函数)是一种对ndarray中的数据进行元素级别运算的函数。例如,square函数计算各元素的平方,rint函数将各元素四...

    公众号---志学Python
  • 数据结构与算法学习笔记之先进先出的队列 数据结构与算法学习笔记之写链表代码的正确姿势(下)数据结构与算法学习笔记之 提高读取性能的链表(上)数据结构与算法学习笔记之 从0编号的数组数据结构与算法学

      队列是一种非常实用的数据结构,类似于生活中发排队,可应用于生活,开发中各个方面,比如共享打印机(先请求先打印),消息队列。你想知道他们是怎么工作的么。那就来...

    Dawnzhang
  • 究极面试题:如何用有限个栈模拟常数效率操作的队列?

    写这篇博客来源于一次面试的经历。经典面试题:如何用两个栈实现一个队列?它经常被拿来面试。如果对栈和队列比较掌握的人,就可以轻松的答出来。

    ShenduCC
  • 什么是队列?

    与前面提到的数据结构相同,队列中的数据也呈线性排列。虽然与栈有些相似,但队列中添加和删除数据的操作分别是在两端进行的,就和队列这个名字一样,把它想象成排成一队的...

    武培轩
  • 如果你问我R代码调试我就会告诉你head,str,help

    比如R语言编程,简单的R代码调试,其实靠head,str,help函数即可。所以我从强调初学者应该是要至少把这3个函数敲1000遍以上。比如,群里有人问它的表达...

    生信技能树
  • 自己动手制作elasticsearch-head的Docker镜像

    通过elasticsearch-head插件可以更方便的查询es,观察es状态,插件官方地址:https://github.com/mobz/elasticse...

    程序员欣宸
  • elasticsearch教程--中文分词器作用和使用

    本文都是基于elasticsearch安装教程 中的elasticsearch安装目录(/opt/environment/elasticsearch-6.4.0...

    IT小白龙
  • Android使用Ant进行apk多渠道打包

    Android使用Ant进行apk多渠道打包 前言: Ant 是什么? 详细介绍请看http://ant.apache.org/ 总之一句话:Ant是一个Apa...

    用户1289394

扫码关注云+社区

领取腾讯云代金券