js數據結構-隊列

newtrek 發布于2019-08-23 14:23 / 3503人閱讀

摘要：隊列上一篇數據結構講到了棧，隊列和棧非常類似。棧入棧后假設數據為，隊列遵循先入先出，所以的時候的順序應該是那么下面我們看如何利用棧出棧。首先棧出棧后的數據則為正好倒過來我們利用循環將棧出棧的數據到棧，則棧中的數據就會是。

隊列

上一篇數據結構講到了棧，隊列和棧非常類似。隊列也是一種特殊的列表，它與棧的區別在于，棧是先入后出，而隊列則是遵循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這幾個數據了

后續

下一張的數據結構會為大家介紹鏈表

GPU云服務器云服務器 js隊列加載鏈表數據結構隊列 java隊列處理數據順序隊列

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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