JavaScript隊列數據結構詳解

Posted on by

寫在前面：

在上一篇文章中介紹瞭棧這個數據結構，這篇文章介紹一下隊列。

什麼是隊列？

隊列是一種先進先出的數據結構，隊列中允許兩種基礎操作，也就是插入和刪除，也就是入隊和出隊；我們將隊列中允許插入的一端稱為隊尾、允許刪除的一端稱為隊頭；

如下圖展示瞭棧這個數據結構：

JavaScript中的隊列

JavaScript並沒有隊列這個數據類型，但是可以通過數組進行模擬，而且數組中提供的push()和shift()選項，正好實現先入後出的的操作，

示例代碼如下：

const queue = []

// 入隊
stack.push(1)
stack.push(2)
// 出隊
const v1 = stack.shift() // 1
const v2 = stack.shift() // 2

JavaScript中的應用場景

隊列和棧一樣，是算法和程序中最常用的輔助結構，其的應用十分廣泛，比如以下場景：

  • 現實生活中的排隊，就比如說買飯排隊，先去的先買，也就是先進先出；
  • 銀行、營業廳等號叫號，例如：到瞭營業廳先去排號機哪裡排號，然後等待叫號，叫號會依次叫號；
  • JavaScript中的異步任務隊列，異步任務隊列是一個典型的應用隊列的例子。

最近的請求次數

現在我們來做一個力扣的題來熟悉一下隊列這個數據結構，這個題是【933. 最近的請求次數】，主要題目描述是寫一個 **** 類來計算特定時間范圍內最近的請求。

解題思路如下：

  • 在類中創建一個隊列，用於保存最近請求；
  • ping時保存請求；
  • 判斷隊頭請求時間是否比t-3000的時間少，如果是則出隊，並繼續判斷，如果不是則返回隊列長度。

實現代碼如下：

var RecentCounter = function() {
    this.q = []
};

/** 
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function(t) {
    this.q.push(t)
    while(this.q[0] < t - 3000) {
        this.q.shift()
    }
    return this.q.length
};

補充

概念和結構：

  • 隊列是一種先進先出（FIFO）的數據結構。
  • 隊列的第一個元素所在位置稱為隊頭，最後一個元素所在位置稱為隊尾。
  • 不包含任何元素的隊列稱為空隊列。

隊列的操作：隊列有五種常用操作，分別為：

  • 入隊 enqueue(element)
  • 出隊 dequeue()
  • 檢查隊頭元素 front()
  • 檢查隊列是否為空 isEmpty()
  • 獲取隊列的長度 size()

JS實現：

JS裡面的隊列結構也是通過數組（Array）來實現的。

function Queue(){
    //私有變量不被外界獲取
    let queue = [];
    //入隊
    this.enqueue = function(element){
        queue.push(element);
    }
    //出隊
    this.dequeue = function(){
        return queue.shift();
    }
    //檢查隊頭元素
    this.front = function(){
        return queue[0];
    }
    //檢查隊列是否為空
    this.isEmpty = function(){
        return queue.length === 0;
    }
    //獲取隊列長度
    this.size = function(){
        return queue.length;
    }
}

總結

文本介紹瞭什麼是隊列以及JavaScript中可以使用數組模擬隊列，在最後還講解一個力扣中的算法題目。

到此這篇關於JavaScript隊列數據結構詳解的文章就介紹到這瞭,更多相關JS隊列數據結構內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：