JavaScript數據結構《隊列》

saucxs 發布于2019-08-21 16:47 / 495人閱讀

摘要：在隊列的這種數據結構里面，新增的元素都在尾部，要移除的元素都在頂部。代碼實現下面用代碼來實現隊列這個數據結構，同樣都采用的語法，我們先定義一個類來表示隊列，然后在這個類的基礎上定義一下方法來模擬隊列的行為。

隊列和棧非常的類似，但是他們采用了不同的原則，棧采用的是后進先出，隊列正好相反，采用的是先進先出的原則。隊列的定義如下

隊列是遵循FIFO(先進先出)原則的有序集合，新添加的元素保存在隊列的尾部，要移除的元素保存在隊列的頂部。在隊列的這種數據結構里面，新增的元素都在尾部，要移除的元素都在頂部。

舉一個生活中的例子，在我們平時去吃肯德基吃飯時肯定要排隊，這條隊伍就可以看做是一個隊列，排在隊伍前面的就是隊列的頂部，隊伍后面的就是隊列的尾部，后來的人都要排在隊伍的后面（隊列的尾部），這就符合了隊列先進先出的原則了（先排隊的可以先點餐）。

代碼實現

下面用代碼來實現隊列這個數據結構，同樣都采用ES6的語法，我們先定義一個類Queue來表示隊列，然后在這個類的基礎上定義一下方法來模擬隊列的行為。

class Queue {

  constructor() {
    // 定義一個數組來保存隊列里面的元素
    this.items = []
  }

  // 在隊列尾部添加一個或者多個元素
  enqueue(element) { }
    
  // 移除隊列頂部的元素，并返回被移除的元素
  dequeue() { }
    
  // 清空隊列
  remove() { }
    
  // 返回隊列頂部的元素，不對隊列本身做修改
  front() { }
    
  // 判斷隊列是否為空
  isEmpty() { }
    
  // 返回隊列里面元素的個數
  length() { }
}

這樣我們就定義好一個基類了，下面來分別實現隊列的行為方法

enqueue

第一個要實現的就是enqueue方法，這個方法接收一個參數，然后把該參數插入隊列的尾部，因為這里我們是用數組來存儲隊列的元素的，所以可以用數組的push方法來實現該操作，代碼如下

 enqueue (element) {
   this.items.push(element)
 }

dequeue

下面接著實現dequeue方法，這個方法會從隊列里面移除項，由于隊列遵循的是先進先出的原則，所以我們要移除的元素就是隊列頂部的元素，同樣因為這里我們是用數組來存儲隊列的元素的，所以可以用數組的shift方法來實現該操作。代碼如下

dequeue () {
    return this.items.shift()
}

remove

接著來實現remove方法，改方法會移除隊列里面所有的項，同理我們把保存隊列元素的數組置空就好了，代碼如下

remove () {
    this.items = []
}

front

上面的方法都是對隊列本身有修改的，接下來要實現的方法front做的是只讀操作，front方法會返回隊列頂部的元素但不對隊列本身進行修改，代碼實現如下

front () {
    return this.items[0]
}

isEmpty

isEmpty方法判斷隊列是否為空，也就是保存隊列的數組的長度是否等于0，代碼實現如下

isEmpty () {
    return this.items.length === 0
}

length

最后一個方法返回隊列的長度，同理就是返回保存隊列元素的數組的長度就好了，代碼如下

length () {
    return this.item.length
}

這里和棧一樣添加一個輔助方法print來打印棧里面的元素，方便我們觀察調試，這個方法和隊列的行為無關，只是一個輔助方法

print（）{
    this.items.forEach((item, index) => {
        console.log(`${index+1}:${item}`)
    })
}

這樣隊列的方法就全部寫好了，最后完整Queue類的代碼如下

class Queue {

  constructor() {
    // 定義一個數組來保存隊列里面的元素
    this.items = []
  }

  // 在隊列尾部添加一個或者多個元素
  enqueue (element) {
      this.items.push(element)
  }
  // 移除隊列頂部的元素，并返回被移除的元素
  dequeue() { 
      return this.items.shift()
  }
  // 清空隊列
  remove() {
      this.items = []
  }
  // 返回隊列頂部的元素，不對隊列本身做修改
  front() { 
      return this.items[0]
  }
  // 判斷隊列是否為空
  isEmpty() { 
      return this.items.length === 0
  }
  // 返回隊列里面元素的個數
  length() { 
      return this.item.length
  }
    
  print（）{
      this.items.forEach((item, index) => {
          console.log(`${index+1}:${item}`)
      })
  }
}

使用Queue類

要使用這個類我們得先實例化它

const queue = new Queue()

queue.isEmpty() // true

queue.push("我是隊列的第一個元素")
queue.push("我是隊列的第二個元素")

queue.print() // 1: 我是隊列的第一個元素 2：我是隊列的第二個元素

queue.dequeue() // 我是隊列的第一個元素

queue.front() // 我是隊列的第二個元素

queue.length() // 1

queue.isEmpty() // false

queue.remove() // 這時隊列里面已經沒有元素了

queue.isEmpty() // true

總結

隊列這種數據結構運用的是非常的廣泛的，就比如javaScript的運行機制，我們都知道javaScript是單線程的，是不能同時執行多個任務，但是單線程就意味著所有任務需要排隊。但是在javaScript里面，很多時候阻止線程運行的很慢的是網絡IO之類，這時候CPU是空閑的，這樣就會造成資源的浪費。所以javaScript在主線程之外實現了一個任務隊列，像IO之類比較慢的操作暫時都會掛在任務隊列上，這樣不會影響到主線程上任務的執行，等到IO的響應回來后再回到主線程上來執行掛起的任務。例子就是我們的Ajax請求，定時器等。

GPU云服務器云服務器 javascript實現隊列鏈表數據結構隊列 java隊列處理數據 javascript數據結構

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

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

學習javascript數據結構(一)——棧和隊列

摘要：原文地址學習數據結構一棧和隊列博主博客地址的個人博客幾乎所有的編程語言都原生支持數組類型，因為數組是最簡單的內存數據結構。他們就是棧和隊列。我們稱作棧頂，而另一端我們稱作棧底。移除棧頂的元素，同時返回被移除元素。前言只要你不計較得失，人生還有什么不能想法子克服的。原文地址：學習javascript數據結構(一)——棧和隊列博主博客地址：Damonare的個人博客幾乎所有的編程...

doodlewind 2019-08-21 14:42 評論0 收藏0
【Javascript】探究javascript中的堆/棧/任務隊列與并發模型 event loop

摘要：而函數調用結束返回時，運行時會將棧頂的調用結構彈出。并發模型與引擎是單線程的，它的并發模型基于事件循環當線程中的同步任務執行完，執行棧為空時，則從任務隊列中取出異步任務進行處理。在當前的微任務沒有執行完成時，是不會執行下一個宏任務的。堆/棧/隊列在javascript中，存在調用棧 (call stack)和內存堆(memory heap) ,程序中函數依次進入棧中等待執行,若執行...

desdik 2019-08-26 13:47 評論0 收藏0
Javascript系列之javascript機制

摘要：異步任務必須指定回調函數，當異步任務從任務隊列回到執行棧，回調函數就會執行。事件循環主線程從任務隊列中讀取事件，這個過程是循環不斷的，所以整個的這種運行機制又稱為。事件循環事件循環是指主線程重復從消息隊列中取消息執行的過程。參考鏈接：這一次，徹底弄懂 JavaScript 執行機制https://zhuanlan.zhihu.com/p/...從瀏覽器多進程到JS單線程，JS運行機制...

13651657101 2019-08-22 15:50 評論0 收藏0
泡杯茶，我們坐下聊聊Javascript的事件環

摘要：是怎么執行的一開始先簡單聊了聊基本的數據結構，它和我們現在說的事件環有什么關系么當然有，首先要明確的一點是，代碼的執行全都在棧里，不論是同步代碼還是異步代碼，這個一定要清楚。棧和隊列在計算機內存中存取數據，基本的數據結構分為棧和隊列。棧（Stack）是一種后進先出的數據結構，注意，有時候也管棧叫做堆棧，但是堆又是另一種復雜的數據結構，它和棧完全是兩碼事。棧的特點是操作只在一端進行...

douzifly 2019-08-23 11:50 評論0 收藏0
JavaScript隊列數據結構詳解

　　今天我們講講JavaScript隊列數據結構詳解。什么是隊列？　　隊列是一種先進先出的數據結構，隊列有兩種操作：插入和刪除；入隊和出隊。簡單來說就是允許插入的一端稱為隊尾、允許刪除的一端稱為隊頭；　　如下圖展示了棧這個數據結構：　　JavaScript中的隊列　　要知道JavaScript中沒有有關隊列的數據模型，因此我們需要通過數組進行模擬，當數組中提供的push()和shift()選...

3403771864 2022-09-21 22:28 評論0 收藏0