js数据结构-队列

newtrek 发布于2019-08-23 14:23 / 3407人阅读

摘要：队列上一篇数据结构讲到了栈，队列和栈非常类似。栈入栈后假设数据为，队列遵循先入先出，所以的时候的顺序应该是那么下面我们看如何利用栈出栈。首先栈出栈后的数据则为正好倒过来我们利用循环将栈出栈的数据到栈，则栈中的数据就会是。

队列

上一篇数据结构讲到了栈，队列和栈非常类似。队列也是一种特殊的列表，它与栈的区别在于，栈是先入后出，而队列则是遵循FIFO先入先出的原则，换言之队列只能在队尾插入元素，而在队列的头部去删除元素。

举个简单的例子，队列就相当于在生活中排队购物，后来的人需要排在队尾，而队伍最前面的人会一次结账后出列。队列的应用非常广泛，常用于实现缓冲区，广度优先搜索，优先级队列等等。

队列最主要的两个操作分别是enqueue(入列)和dequeue(出列)

队列的实现逻辑

通过上面这张图我们可以看到队列的几个特点

初始化

有一块连续的空间用来去存储队列

有一个头部指向第一个数据的地址

有一个尾部指向数据后一个空位的地址

空间的大小

队列内部数据的长度

    class Queue {
        constructor(max=1000){
            // 定义一块连续的存储空间用来存储数据
            this.data = new Array(1000);
            // 开辟的空间大小
            this.max = max;
            // 头部位置
            this.head = 0;
            // 尾部位置
            this.tail = 0;
            // 数据长度
            this.size = 0;
        }
    }

enqueue 入列

当数据长度超出了开辟的空间大小会报overflow的错误

向尾部添加新数据

尾部指针向后挪动一位，如果尾部没有空间，则指向0（见上图的两个enqueue操作）

    enqueue(x) {
        // 溢出
        if(this.size === this.max){
            throw "overflow"
        }
        // 添加新数据到尾部
        this.data[this.tail] = x;
        // 数据长度+1
        this.size++;
        // 尾部指针向后挪动一位，如果后面没有空间，则指向0
        if(this.tail === this.max-1){
            this.tail = 0;
        }else{
            this.tail++
        }
    }

dequeue出列

如果当前数据长度为0，则抛出underflow的错误

取出头部位置的数据

头部指针向后挪动一位

数据长度-1

返回该数据

    dequeue(){
        if(this.size === 0){
            throw "underflow";
        }
        const x = this.data[this.head];
        this.head++;
        this.size--;
        return x;
    }

整个代码

    class Queue {
      constructor(max = 1000) {
        this.data = new Array(max);
        this.max = max;
        this.head = 0;
        this.tail = 0;
        this.size = 0;
      }
    
      // 入列
      enqueue(x) {
        if (this.size === this.max) {
          throw "overflow";
        }
        this.data[this.tail] = x;
        this.size++;
        if (this.tail === this.max - 1) {
          this.tail = 0;
        } else {
          this.tail++;
        }
      }
    
      // 出列
      dequeue() {
        if (this.size === 0) {
          throw "underflow";
        }
        const x = this.data[this.head];
        this.head++;
        this.size--;
        return x;
      }
    
      get length() {
        return this.size;
      }
    }
    
    module.exports = Queue;

扩展--栈实现队列

队列也可以通过两个栈来实现，不了解栈的同学可以看上一篇关于栈文章，接下来会引入之前写好的栈，具体代码见下面。

    // 上一节中，栈的实现代码
    const Stack = require("./stack");
    
    class Queue {
        constructor(max=1000){
            // 实例化两个栈，分别是s1和s2, s1栈用来做入列,s2栈用来出列使用
            this.s1 = new Stack(max);
            this.s2 = new Stack(max);
            this.max = max;
        }
        // 入列
        enqueue(x) {
            if(this.s1.length === this.max){
                throw "overflow"
            }
            // s1作为入列
            this.s1.push(x);
        }
        // 出列
        dequeue(){
            if(this.s2.length>0){
                return this.s2.pop;
            }
            while(this.s1.length){
                this.s2.push(this.s1.pop());
            }
            return this.s2.pop();
        }
    }

在这里大致简单的说明一下以上用两个栈来实现队列的逻辑吧。

栈s1 入栈后假设数据为 1,2,3,4,5，队列遵循先入先出，所以dequeue的时候的顺序应该是1,2,3,4,5,那么下面我们看如何利用栈s2出栈。

首先栈s1 pop()出栈后的数据则为 5,4,3,2,1 正好倒过来, 我们利用循环将栈s1出栈的数据push到栈s2，则栈s2中的数据就会是5,4,3,2,1。下面我们再执行s2.pop()的时候，是不是就能刚好能依次拿到1,2,3,4,5这几个数据了

后续

下一张的数据结构会为大家介绍链表

私有云服务器托管 js队列加载链表数据结构队列 java队列处理数据顺序队列

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

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

JS事件循环，了解一下

摘要：任务队列中的代码被加载到函数调用栈中去执行。说到这里，你基本上对事件循环有个大致的了解了。在理解事件循环之前，我总会遇到一些奇奇怪怪的问题：比如明明已经调接口拿到了数据，可是跟在调数据之后的操作却没有正常执行；又或者不知道为啥，代码里非得加个setTimeout才能正常跑通；特别是在运用Promise的时候，更是有各种问题百思不得解。遇上问题要解决，更要知道问题产生的原因，这样才能h...

xbynet 2019-08-26 11:59 评论0 收藏0
js堆,栈与队列

摘要：内存空间又被分为两种，栈内存与堆内存。今天就堆栈队列的内容就大概说到这里下一篇博客在继续说一下，有什么说的不对或者不足的地方，请大家批评指正栈的定义栈是计算机科学中的一种抽象数据类型，只允许在有序的线性数据集合的一端（称为堆栈顶端，英语：top）进行加入数据（英语：push）和移除数据（英语：pop）的运算。因而按照后进先出（LIFO, Last In First Out）的原理运...

Kosmos 2019-08-23 18:36 评论0 收藏0
【js4agls】数据结构JavaScript描述-队列篇

摘要：队列是一种先进先出的数据结构，与栈不同的是，它操作的元素是在两端，而且进行的是不一样的操作。队列(Queue)是一种先进先出(First-In-First-Out, FIFO)的数据结构，与栈不同的是，它操作的元素是在两端，而且进行的是不一样的操作。向队列的队尾加入一个元素叫做入队列(enQueue)，向队列的队首删除一个元素叫做出队列(delQueue). showImg(http...

Anonymous1 2019-08-19 18:13 评论0 收藏0
[ JavaScript ] 数据结构与算法 —— 队列

摘要：而且目前大部分编程语言的高级应用都会用到数据结构与算法以及设计模式。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。前言 JavaScript是当下最流行的编程语言之一，它可以做很多事情：数据可视化（D3.js，Three.js，Chart.js）; 移动端应用(React Native,Weex,AppCan,Flutter,Hybrid App,小程...

Yi_Zhi_Yu 2019-08-23 15:05 评论0 收藏0
【笔记】你不知道的JS读书笔记——异步

摘要：异步请求线程在在连接后是通过浏览器新开一个线程请求将检测到状态变更时，如果设置有回调函数，异步线程就产生状态变更事件，将这个回调再放入事件循环队列中。基础：浏览器 -- 多进程，每个tab页独立一个浏览器渲染进程（浏览器内核）每个浏览器渲染进程是多线程的，主要包括：GUI渲染线程 JS引擎线程也称为JS内核，负责处理Javascript脚本程序。（例如V8引擎） JS引擎线程负...

junnplus 2019-08-22 15:43 评论0 收藏0
JS与Node.js中的事件循环

摘要：的单线程，与它的用途有关。特点的显著特点异步机制事件驱动。队列的读取轮询线程，事件的消费者，的主角。它将不同的任务分配给不同的线程，形成一个事件循环，以异步的方式将任务的执行结果返回给引擎。这两天跟同事同事讨论遇到的一个问题，js中的event loop，引出了chrome与node中运行具有setTimeout和Promise的程序时候执行结果不一样的问题，从而引出了Nodejs的...

abson 2019-08-22 11:14 评论0 收藏0