js堆,栈与队列

Kosmos 发布于2019-08-23 18:36 / 2996人阅读

摘要：内存空间又被分为两种，栈内存与堆内存。今天就堆栈队列的内容就大概说到这里下一篇博客在继续说一下，有什么说的不对或者不足的地方，请大家批评指正

栈的定义

栈是计算机科学中的一种抽象数据类型，只允许在有序的线性数据集合的一端（称为堆栈顶端，英语：top）进行加入数据（英语：push）和移除数据（英语：pop）的运算。因而按照后进先出（LIFO, Last In First Out）的原理运作。（百科全书）

栈的常用操作

栈中有两个基本的操作

推入：从栈的顶端推入一个数据，依次往下推

弹出：讲栈顶端的数据移除

栈的基本提点就是

先进后出，后进先出

除了头尾的节点，每个元素都有一个先驱和一个后继

对于栈的画面的理解，可以想象成一个步枪弹夹添加子弹和射击的过程
弹夹只有一个出入口进行推入和弹出

js模拟实现一个栈

效果图如下

栈被创建的时机

上边说了栈的基本结构和方法，那么栈被创建的时候又做了什么事情呢

首先在我们的js在解释执行代码的时候，最先遇到的就是全局代码，所以在一开始的时候首先就会向栈里边压入一个全局执行上下文

全局上下文只有在全局执行环境被销毁的时候才会被弹出销毁
全局执行上下文只有一个就是浏览器中的window对象，this默认指向这个全局对象

然后当执行一个函数的时候，会在开始先创建一个执行上下文压入栈中，如果里边又执行其他的函数的时候，又会创建一个新的执行上下文压入执行栈中，直到函数执行完毕，就会把函数的上下文从执行栈中弹出

function fun3() {
console.log("3")
}

function fun2() {
    fun3();
}

function fun1() {
    fun2();
}

fun1();

比如说上边这段代码，他的进栈出栈顺序就是一开始我们放的那两张图的效果

function fun1() {
     console.log("1")
}
function fun2() {
     console.log("2")
}
function fun3() {
     console.log("3")
}

如果是这种的话则会是最下边有一个全局的栈，然后三个函数分别进栈出栈

栈中的执行上下文

刚才我们在上边提到了执行上下文的概念，执行上下文是跟函数相关的，执行上下文分为两个阶段

创建阶段

执行阶段

首先创建阶段

扫描变量和函数（确定变量环境）

确定this指向

确定词法环境

简单说一下词法环境和变量环境的区别，我个人理解的就是说词法环境是包含变量环境的

在js里边原型链大家都不陌生，js在当前的对象里边找不到所使用的属性的话会去他的上一级去找
直到Object，再找不到就会undefined ，这里边当前对象的作用域就是他的变量环境，而词法环境则是与之关联的的执行上下文中声明的变量

在创建阶段函数的声明会被储存在当前的变量环境之中，var的变量的话则会被设置成undefined
，所以我们在声明之前就可以访问到var声明的变量，but他是一个undfined

然后就是执行阶段了

这个时候已经完成了对所有变量的分配，开始执行代码

队列的定义

队列是一种比较高效的数据结构，他与栈不同的是，队列只能在队尾插入元素，在队首删除元素，
队列用生活中的事物距离的话，大家可以想想一下沙漏，先进入的沙子先出去，后进去的沙子后出去

队列比栈高效的地方就在于，循环的时候，栈会开辟一个新的临时栈，然后进行排序，再循环，最后在确保不打乱原有顺序的情况下排列回去

队列则不需要这么多步骤

js模拟队列实现

队列常用的一些操作有

向队尾添加一个元素

删除队首元素

显示所有元素

清空队列

队列是否为空

就先拿这些常用的方法实现以下，老规矩，请大家看代码

     // 队列类
    class Queue {
        constructor() {
            this.dataStore = []
        }

        //新增
        addQueue(val) {
            this.dataStore.push(val);
        }


        //删除队列首的元素
        delQueue() {
            return this.queueIsNone()?console.log("队列空了"):this.dataStore.shift()
        }

        //队列是否为空
        queueIsNone() {
            return this.dataStore.length == 0
        }

        //查看所有元素
        showQueue() {
            return this.dataStore.join("
");
        }

        //清空队列
        clearQueue() {
            this.dataStor = [];
            this.showQueue()
            console.log("队列空了")
        }
    }

    // 队列实例
    let queueOne = new Queue()
    /**
     * @author: 周靖松
     * @information: 进队
     * @Date: 2019-06-11 21:01:28
     */
    function QueueIn (){
        queueOne.addQueue(funStackBox.value)
        console.log(queueOne.showQueue())
    }
    /**
     * @author: 周靖松
     * @information: 出队
     * @Date: 2019-06-11 21:01:35
     */
    function QueueOut (){
        queueOne.delQueue()
        console.log(queueOne.showQueue())
    }
    /**
    * @author: 周靖松
    * @information: 清空队列
    * @Date: 2019-06-11 21:05:35
    */    
    function QueueClear(){
        queueOne.clearQueue()
    }

上边的代码大家可以自己写个html试一下哈，html就不写了直接贴一下效果图

另外虽然刚才我们再例子中是用数据去模拟的栈和队列的实现，but 数组他其实并不是一个栈内存，他是一个堆内存

堆的定义

若是满足以下特性，即可称为堆：是计算机科学中的一种特别的树状数据结构。可以给堆中的任意节点添加新的节点（百科全书）

堆和栈的区别

在JS中，每一个数据都需要一个内存空间。内存空间又被分为两种，栈内存(stack)与堆内存(heap)。

栈为自动分配的内存空间，它由系统自动释放

堆是动态分配的内存，大小不定也不会自动释放

也不是说不会自动释放，堆在没有引用的时候，下一次垃圾回收机制出现的时候会回收他的内存

js 的变量分为基本类型和引用类型

基本类型（Undefined、Null、Boolean、Number和String）

基本类型在内存中占据空间小、大小固定，他们的值保存在栈(stack)空间，是按值来访问

引用类型（对象、数组、函数）

引用类型占据空间大、大小不固定, 栈内存中存放地址指向堆(heap)内存中的对象。是按引用访问的

盗个图举个例子

js不允许直接访问堆内存中的位置，因此我们不能直接操作对象的堆内存空间，所以栈中存的是一个指向堆内存的一个地址

当我们要访问堆内存中的引用数据类型时，实际上我们首先是从栈中获取了该对象的地址引用（或者地址指针），然后再从堆内存中取得我们需要的数据。

今天就堆栈队列的内容就大概说到这里下一篇博客在继续说一下，有什么说的不对或者不足的地方，请大家批评指正

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/105532.html

【译】JavaScript数据结构（2）：栈与队列

摘要：栈和队列是开发中最常用的两种数据结构。如果又有数据入栈，的值将增加到。如果一个数据从栈中被取出，的值将会减少为。队列与栈类似，队列也是一个线性数据结构。与栈不同的是，队列只删除最先添加的数据。现在，让我们将栈大小的实现应用到队列中。翻译：疯狂的技术宅英文：https://code.tutsplus.com/art...说明：本文翻译自系列文章《Data Structures With...

zlyBear 2019-08-20 18:18 评论0 收藏0
学习数据结构与算法之栈与队列

摘要：于是翻出了机房里的这本学习数据结构与算法开始学习程序员的基础知识。这本书用了我最熟悉的来实现各种数据结构和算法，而且书很薄，可以说是一本不错的入门教程。队列在头部删除元素，尾部添加元素。本系列所有文章：第一篇文章：学习数据结构与算法之栈与队列第二篇文章：学习数据结构与算法之链表第三篇文章：学习数据结构与算法之集合第四篇文章：学习数据结构与算法之字典和散列表第五篇文章：学习数据结构与算...

pingan8787 2019-08-20 18:37 评论0 收藏0
栈与堆的理解

摘要：对于栈和堆的理解栈栈是有结构的，存储的时候按顺序存储，先存进去的在栈的最下面，遵循先进后出的原则，栈中存放的是基本数据类型变量的值，以及引用数据类型中指向堆的引用地址，占据的空间大小一般是确定的。对于栈和堆的理解栈（stack）栈是有结构的，存储的时候按顺序存储，先存进去的在栈的最下面，遵循’先进后出‘的原则，栈中存放的是基本数据类型变量的值，以及引用数据类型中指向堆的引用（地址...

appetizerio 2019-08-30 15:44 评论0 收藏0
学习JavaScript数据结构与算法（一）：栈与队列

摘要：之数组操作接下来就是数据结构的第一部分，栈。以字符串显示栈中所有内容方法的实现说明需要往栈中添加新元素，元素位置在队列的末尾。的前端乐园原文链接寒假前端学习学习数据结构与算法，栈与队列本系列的第一篇文章: 学习JavaScript数据结构与算法（一），栈与队列第二篇文章：学习JavaScript数据结构与算法（二）：链表第三篇文章：学习JavaScript数据结构与算法（三）：集合第...

Flink_China 2019-08-19 17:23 评论0 收藏0
浅谈JavaScript中的事件循环机制

摘要：事件循环背景是一门单线程非阻塞的脚本语言，单线程意味着，代码在执行的任何时候，都只有一个主线程来处理所有的任务。在意识到该问题之际，新特性中的可以让成为一门多线程语言，但实际开发中使用存在着诸多限制。这个地方被称为执行栈。事件循环（Event Loop）背景 JavaScript是一门单线程非阻塞的脚本语言，单线程意味着，JavaScript代码在执行的任何时候，都只有一个主线程来...

Pluser 2019-08-23 15:22 评论0 收藏0