成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

js數(shù)據(jù)結(jié)構(gòu)-隊列

newtrek / 3513人閱讀

摘要：隊列上一篇數(shù)據(jù)結(jié)構(gòu)講到了棧，隊列和棧非常類似。棧入棧后假設(shè)數(shù)據(jù)為，隊列遵循先入先出，所以的時候的順序應(yīng)該是那么下面我們看如何利用棧出棧。首先棧出棧后的數(shù)據(jù)則為正好倒過來我們利用循環(huán)將棧出棧的數(shù)據(jù)到棧，則棧中的數(shù)據(jù)就會是。

隊列

上一篇數(shù)據(jù)結(jié)構(gòu)講到了棧，隊列和棧非常類似。隊列也是一種特殊的列表，它與棧的區(qū)別在于，棧是先入后出，而隊列則是遵循FIFO先入先出的原則，換言之隊列只能在隊尾插入元素，而在隊列的頭部去刪除元素。

舉個簡單的例子，隊列就相當于在生活中排隊購物，后來的人需要排在隊尾，而隊伍最前面的人會一次結(jié)賬后出列。隊列的應(yīng)用非常廣泛，常用于實現(xiàn)緩沖區(qū)，廣度優(yōu)先搜索，優(yōu)先級隊列等等。

隊列最主要的兩個操作分別是enqueue(入列)和dequeue(出列)

隊列的實現(xiàn)邏輯

通過上面這張圖我們可以看到隊列的幾個特點

初始化

有一塊連續(xù)的空間用來去存儲隊列

有一個頭部指向第一個數(shù)據(jù)的地址

有一個尾部指向數(shù)據(jù)后一個空位的地址

空間的大小

隊列內(nèi)部數(shù)據(jù)的長度

    class Queue {
        constructor(max=1000){
            // 定義一塊連續(xù)的存儲空間用來存儲數(shù)據(jù)
            this.data = new Array(1000);
            // 開辟的空間大小
            this.max = max;
            // 頭部位置
            this.head = 0;
            // 尾部位置
            this.tail = 0;
            // 數(shù)據(jù)長度
            this.size = 0;
        }
    }

enqueue 入列

當數(shù)據(jù)長度超出了開辟的空間大小會報overflow的錯誤

向尾部添加新數(shù)據(jù)

尾部指針向后挪動一位，如果尾部沒有空間，則指向0（見上圖的兩個enqueue操作）

    enqueue(x) {
        // 溢出
        if(this.size === this.max){
            throw "overflow"
        }
        // 添加新數(shù)據(jù)到尾部
        this.data[this.tail] = x;
        // 數(shù)據(jù)長度+1
        this.size++;
        // 尾部指針向后挪動一位，如果后面沒有空間，則指向0
        if(this.tail === this.max-1){
            this.tail = 0;
        }else{
            this.tail++
        }
    }

dequeue出列

如果當前數(shù)據(jù)長度為0，則拋出underflow的錯誤

取出頭部位置的數(shù)據(jù)

頭部指針向后挪動一位

數(shù)據(jù)長度-1

返回該數(shù)據(jù)

    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;
擴展--棧實現(xiàn)隊列

隊列也可以通過兩個棧來實現(xiàn)，不了解棧的同學可以看上一篇關(guān)于棧文章，接下來會引入之前寫好的棧，具體代碼見下面。

    // 上一節(jié)中，棧的實現(xiàn)代碼
    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();
        }
    }

在這里大致簡單的說明一下以上用兩個棧來實現(xiàn)隊列的邏輯吧。

棧s1 入棧后假設(shè)數(shù)據(jù)為 1,2,3,4,5，隊列遵循先入先出，所以dequeue的時候的順序應(yīng)該是1,2,3,4,5,那么下面我們看如何利用棧s2出棧。

首先棧s1 pop()出棧后的數(shù)據(jù)則為 5,4,3,2,1 正好倒過來, 我們利用循環(huán)將棧s1出棧的數(shù)據(jù)push到棧s2，則棧s2中的數(shù)據(jù)就會是5,4,3,2,1。下面我們再執(zhí)行s2.pop()的時候，是不是就能剛好能依次拿到1,2,3,4,5這幾個數(shù)據(jù)了

后續(xù)

下一張的數(shù)據(jù)結(jié)構(gòu)會為大家介紹鏈表

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/100531.html

相關(guān)文章

  • JS事件循環(huán)，了解一下

    摘要：任務(wù)隊列中的代碼被加載到函數(shù)調(diào)用棧中去執(zhí)行。說到這里，你基本上對事件循環(huán)有個大致的了解了。 在理解事件循環(huán)之前，我總會遇到一些奇奇怪怪的問題：比如明明已經(jīng)調(diào)接口拿到了數(shù)據(jù)，可是跟在調(diào)數(shù)據(jù)之后的操作卻沒有正常執(zhí)行；又或者不知道為啥，代碼里非得加個setTimeout才能正常跑通；特別是在運用Promise的時候，更是有各種問題百思不得解。遇上問題要解決，更要知道問題產(chǎn)生的原因，這樣才能h...

    xbynet 評論0 收藏0

  • js堆,棧與隊列

    摘要：內(nèi)存空間又被分為兩種，棧內(nèi)存與堆內(nèi)存。今天就堆棧隊列的內(nèi)容就大概說到這里下一篇博客在繼續(xù)說一下，有什么說的不對或者不足的地方，請大家批評指正 棧的定義 棧是計算機科學中的一種抽象數(shù)據(jù)類型，只允許在有序的線性數(shù)據(jù)集合的一端（稱為堆棧頂端，英語：top）進行加入數(shù)據(jù)（英語：push）和移除數(shù)據(jù)（英語：pop）的運算。因而按照后進先出（LIFO, Last In First Out）的原理運...

    Kosmos 評論0 收藏0

  • 【js4agls】數(shù)據(jù)結(jié)構(gòu)JavaScript描述-隊列篇

    摘要：隊列是一種先進先出的數(shù)據(jù)結(jié)構(gòu)，與棧不同的是，它操作的元素是在兩端，而且進行的是不一樣的操作。 隊列(Queue)是一種先進先出(First-In-First-Out, FIFO)的數(shù)據(jù)結(jié)構(gòu)，與棧不同的是，它操作的元素是在兩端，而且進行的是不一樣的操作。向隊列的隊尾加入一個元素叫做入隊列(enQueue)，向隊列的隊首刪除一個元素叫做出隊列(delQueue). showImg(http...

    Anonymous1 評論0 收藏0

  • [ JavaScript ] 數(shù)據(jù)結(jié)構(gòu)與算法 —— 隊列

    摘要：而且目前大部分編程語言的高級應(yīng)用都會用到數(shù)據(jù)結(jié)構(gòu)與算法以及設(shè)計模式。隊列在尾部添加新元素，并從頂部移除元素。最新添加的元素必須排在隊列的末尾。 前言 JavaScript是當下最流行的編程語言之一，它可以做很多事情： 數(shù)據(jù)可視化（D3.js，Three.js，Chart.js）; 移動端應(yīng)用(React Native,Weex,AppCan,Flutter,Hybrid App,小程...

    Yi_Zhi_Yu 評論0 收藏0

  • 【筆記】 你不知道的JS讀書筆記——異步

    摘要：異步請求線程在在連接后是通過瀏覽器新開一個線程請求將檢測到狀態(tài)變更時，如果設(shè)置有回調(diào)函數(shù)，異步線程就產(chǎn)生狀態(tài)變更事件，將這個回調(diào)再放入事件循環(huán)隊列中。 基礎(chǔ)：瀏覽器 -- 多進程，每個tab頁獨立一個瀏覽器渲染進程（瀏覽器內(nèi)核） 每個瀏覽器渲染進程是多線程的，主要包括：GUI渲染線程 JS引擎線程 也稱為JS內(nèi)核，負責處理Javascript腳本程序。（例如V8引擎） JS引擎線程負...

    junnplus 評論0 收藏0

  • JS與Node.js中的事件循環(huán)

    摘要：的單線程，與它的用途有關(guān)。特點的顯著特點異步機制事件驅(qū)動。隊列的讀取輪詢線程，事件的消費者，的主角。它將不同的任務(wù)分配給不同的線程，形成一個事件循環(huán)，以異步的方式將任務(wù)的執(zhí)行結(jié)果返回給引擎。 這兩天跟同事同事討論遇到的一個問題，js中的event loop，引出了chrome與node中運行具有setTimeout和Promise的程序時候執(zhí)行結(jié)果不一樣的問題，從而引出了Nodejs的...

    abson 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<