JS數據結構學習：隊列

OpenDigg 發布于2019-08-23 15:10 / 2537人閱讀

隊列的定義

隊列是遵循先進先出原則的一組有序的項，與棧的不同的是，棧不管是入棧還是出棧操作都是在棧頂操作，隊列則是在隊尾添加元素，隊頂移除，用一個圖來表示大概是這樣事的：

用一個更形象的例子就是：排隊服務，總是先排隊的人會先接受服務，當然不考慮插隊的情況

隊列的創建

與棧的創建類似，首先創建一個表示隊列的函數，然后定義一個數組用來保存隊列里的元素：

function Queue() {
  let items = []
}

創建隊列后需要為其定義一些方法，一般來說隊列包含以下方法：

enqueue(element)：向隊的尾部添加一個新的項

dequeue()：移除隊列第一項，并返回被移除的元素

front()：返回隊列第一項，隊列不做任何變動

isEmpty()：如果隊列中沒有任何元素返回true，否則返回false

size()：返回隊列包含的元素個數

具體實現：

function Queue() {
  let items = []
  // 向隊列的尾部添加新元素
  this.enqueue = function (element) {
    items.push(element)
  }
  // 遵循先進先出原則，從隊列的頭部移除元素
  this.dequeue = function () {
    return items.shift()
  }
  // 返回隊列最前面的項
  this.front = function () {
    return items[0]
  }
  // 返回隊列是否為空
  this.isEmpty = function () {
    return items.length === 0
  }
  // 返回隊列的長度
  this.size = function () {
    return items.length
  }
  // 打印隊列，方便觀察
  this.print = function () {
    console.log(items.toString())
  }
}

隊列的使用

接下來讓我們看看隊列的使用：

let queue = new Queue()
queue.enqueue("a")
queue.enqueue("b")
queue.enqueue("c")
queue.dequeue()
queue.print()

首先向隊列中添加三個元素：a,b,c,然后移除隊列中的一個元素，最后打印現有隊列，讓我們一起圖解這個過程：

es6實現Queue

和實現Stack類一樣，也可以用es6的class語法實現Queue類，用WeakMap保存私用屬性items，并用閉包返回Queue類，來看具體實現：

let Queue = (function () {
  let items = new WeakMap
  class Queue {
    constructor () {
      items.set(this, [])
    }
    enqueue (element) {
      let q = items.get(this)
      q.push(element)
    }
    dequeue () {
      let q = items.get(this)
      return q.shift()
    }
    front () {
      let q = items.get(this)
      return q[0]
    }
    isEmpty () {
      let q = items.get(this)
      return q.length === 0
    }
    size () {
      let q = items.get(this)
      return q.length
    }
    print () {
      let q = items.get(this)
      console.log(q.toString())
    }
  }
  return Queue
})()
let queue = new Queue()
queue.enqueue("a")
queue.enqueue("b")
queue.enqueue("c")
queue.dequeue()
queue.print()

優先隊列

優先隊列顧名思義就是：隊列中的每個元素都會有各自的優先級，在插入的時候會根據優先級的高低順序進行插入操作，和前面隊列實現有點不太一樣的地方，隊列中的元素多了有先級的屬性，下面來看具體代碼：

function PriorityQueue() {
  let items = []
  // 隊列元素，多定義一個優先級變量
  function QueueElement(element, priority) {
    this.element = element
    this.priority = priority
  }
  this.enqueue = function (element, priority) {
    let queueElement = new QueueElement(element, priority)
    let added = false
    for (let i = 0; i < items.length; i++) {
      //數字越小優先級越高
      if (queueElement.priority < items[i].priority) {
        items.splice(i, 0, queueElement)
        added = true
        break
      }
    }
    if (!added) {
      items.push(queueElement)
    }
  }
  this.dequeue = function () {
    return items.shift()
  }
  this.front = function () {
    return items[0]
  }
  this.isEmpty = function () {
    return items.length === 0
  }
  this.size = function () {
    return items.length
  }
  this.print = function () {
    for (let i = 0; i < items.length; i++) {
      console.log(`${items[i].priority}-${items[i].element}`)
    }
  }
}
let priorityQueue = new PriorityQueue()
priorityQueue.enqueue("a", 3)
priorityQueue.enqueue("b", 2)
priorityQueue.enqueue("c", 1)
priorityQueue.dequeue()
priorityQueue.print()

入隊時如果隊列為空直接加入隊列，否則進行比較，priority小的優先級高，優先級越高放在隊列的越前面，下面用一個圖來看調用過程：

循環隊列

循環隊列顧名思義就是：給定一個數，然后迭代隊列，從隊列開頭移除一項，然后再將其加到隊列末尾，當循環到給定數字時跳出循環，從隊首移除一項，直至剩余一個元素，下面來看具體代碼：

unction Queue() {
  let items = []
  this.enqueue = function (element) {
    items.push(element)
  }
  this.dequeue = function () {
    return items.shift()
  }
  this.front = function () {
    return items[0]
  }
  this.isEmpty = function () {
    return items.length === 0
  }
  this.size = function () {
    return items.length
  }
  this.print = function () {
    console.log(items.toString())
  }
}
function loopQueue(list, num) {
  let queue = new Queue()
  for (let i = 0; i 1) {
    for (let j = 0; j
總結
這篇文章主要對隊列做了簡單介紹，對隊列以及相關應用做了簡單實現。如果有錯誤或不嚴謹的地方，歡迎批評指正，如果喜歡，歡迎點贊。

GPU云服務器云服務器 js隊列加載鏈表數據結構隊列 java隊列處理數據 js腳本學習

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/101627.html

我對JS隊列的學習

摘要：我對隊列的學習什么是隊列隊列是遵循先進先出原則的一組有序的項。最新添加的元素必須排在隊列的末尾。隊列的學習隊列的操作其實是和棧是差不多的，但是隊列只允許新數據在后端進行添加。這里是最小優先隊列，優先值較小的元素被放置在隊列最前面。我對JS隊列的學習什么是隊列隊列是遵循FIFO（先進先出）原則的一組有序的項。隊列在尾部添加新元素，并從頂部移除元素。最新添加的元素必須排在隊列的末尾。...

Cristic 2019-08-21 11:37 評論0 收藏0
學習JavaScript異步、事件循環

摘要：使用關鍵字來表示，在函數內部使用來表示異步。執行完了后，執行棧再次為空，事件觸發線程會重復上一步操作，再取出一個消息隊列中的任務，這種機制就被稱為事件循環機制。 async 函數是 Generator 函數的語法糖。使用關鍵字 async 來表示，在函數內部使用 await 來表示異步。想較于 Generator，Async 函數的改進在于下面四點：內置執行器 Generato...

nemo 2019-08-23 13:52 評論0 收藏0
[js高手之路]javascript騰訊面試題學習封裝一個簡易的異步隊列

摘要：這道的面試題，是這樣的，頁面上有一個按鈕，一個，點擊按鈕的時候，每隔秒鐘向的后面追加一個一共追加個，的內容從開始技術，首先我們用閉包封裝一個創建元素的函數頁面上的個元素點我代碼點擊按鈕的時候，用回調函數嵌套方式，這里我加入個，就已經快受不了這道js的面試題，是這樣的，頁面上有一個按鈕，一個ul，點擊按鈕的時候，每隔1秒鐘向ul的后面追加一個li, 一共追加10個，li的內容從0開始技...

hzx 2019-08-21 16:23 評論0 收藏0
JS數據結構與算法_棧&隊列

摘要：下一篇數據結構與算法鏈表寫在前面說明數據結構與算法系列文章的代碼和示例均可在此找到原計劃是把你不知道的三部全部看完的，偶然間朋友推薦了數據結構與算法的一套入門視頻，學之。手頭上恰好有學習數據結構與算法的書籍，便轉而先把數據結構與算法學習。下一篇：JS數據結構與算法_鏈表寫在前面說明：JS數據結構與算法系列文章的代碼和示例均可在此找到原計劃是把《你不知道的Javascript》...

AndroidTraveler 2019-08-23 14:45 評論0 收藏0
Promise學習總結

摘要：引擎線程也稱為內核，負責處理腳本程序例如引擎引擎線程負責解析腳本，運行代碼。對象代表一個未完成但預計將來會完成的操作。注意一旦新建就會立即執行它屬于，無法取消。寫在前面: 第一遍學Promise時, 只是大概過了一遍, 感覺學的不夠深入, 這一篇算是對之前的一個總結吧. Promise在ES6中也屬于一個較難理解的一部分; 所以在學習一個比較難理解的知識點時, 我們可以圍繞這個知識點...

twohappy 2019-08-23 15:58 評論0 收藏0