JavaScript數據結構03 - 隊列

Jonathan Shieber 發布于2019-08-23 10:23 / 2629人閱讀

摘要：但是，還有一種隊列叫優先隊列，元素的添加和移除是依賴優先級的。分類優先隊列分為兩類最小優先隊列最大優先隊列最小優先隊列是把優先級的值最小的元素被放置到隊列的最前面代表最高的優先級。那么最小優先隊列排序應該為，，，。

一、定義

前面我們學習了棧的實現，隊列和棧非常類似，但是使用了不同的原則，而非后進先出。

隊列是遵循FIFO（First In First Out，先進先出）原則的一組有序的項。隊列在尾部添加新元素，并從頂部移除元素。最新添加的元素必須排在隊列的末尾。

在計算機科學中，一個最常見的例子就是打印隊列。比如說我們要打印五份文檔。我們會打開每個文檔，然后點擊打印按鈕。每個文檔都會被發送至打印隊列。第一個發送到打印隊列的文檔會首先被打印，以此類推，直到打印完所有文檔。

二、隊列的實現 2.1 普通隊列

創建普通隊列類：

// Queue類
function Queue () {
  this.items = [];

  this.enqueue = enqueue;
  this.dequeue = dequeue;
  this.front = front;
  this.isEmpty = isEmpty;
  this.size = size;
  this.clear = clear;
  this.print = print;
}

隊列里面有一些聲明的輔助方法：

enqueue(element)：向隊列尾部添加新項

dequeue()：移除隊列的第一項（即排在隊列最前面的項），并返回被移除的元素

front()：返回隊列中第一個元素，隊列不做任何變動，和Stack的peek()方法類似

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

size()：返回隊列包含的元素個數，與數組的length屬性類似

print()：打印隊列中的元素

clear()：清空整個隊列

下面我們來一一實現這些輔助方法：

// 向隊列尾部添加元素
function enqueue (element) {
  this.items.push(element);
}

// 移除隊列的第一個元素，并返回被移除的元素
function dequeue () {
  return this.items.shift();
}

// 返回隊列的第一個元素
function front () {
  return this.items[0];
}

// 判斷是否為空隊列
function isEmpty () {
  return this.items.length === 0;
}

// 獲取隊列的長度
function size () {
  return this.items.length;
}

// 清空隊列
function clear () {
  this.items = [];
}

// 打印隊列里的元素
function print () {
  console.log(this.items.toString());
}

創建普通隊列實例進行測試：

// 創建Queue實例
var queue = new Queue();

console.log(queue.isEmpty());     // true
queue.enqueue("John");            // undefined
queue.enqueue("Jack");            // undefined
queue.enqueue("Camila");          // undefined
queue.print();                    // "John,Jack,Camila"
console.log(queue.size());        // 3
console.log(queue.isEmpty());     // false
queue.dequeue();                  // "John"
queue.dequeue();                  // "Jack"
queue.print();                    // "Camila"
queue.clear();                    // undefined
console.log(queue.size());        // 0

2.2 優先隊列 2.2.1 定義

普通隊列的添加和移除只依賴于先后順序，先來的先添加，后來的后添加，然后按照先后順序依次從隊列移除。

但是，還有一種隊列叫優先隊列，元素的添加和移除是依賴優先級的。

一個現實的例子就是機場登機的順序。頭等艙和商務艙乘客的優先級要高于經濟艙乘客。再比如火車，老年人、孕婦和帶小孩的乘客是享有優先檢票權的。

2.2.2 分類

優先隊列分為兩類：

最小優先隊列

最大優先隊列

最小優先隊列是把優先級的值最小的元素被放置到隊列的最前面（代表最高的優先級）。比如有四個元素："John", "Jack", "Camila", "Tom"，他們的優先級值分別為4，3，2，1。

那么最小優先隊列排序應該為："Tom"，"Camila"，"Jack"，"John"。

最大優先隊列正好相反，把優先級值最大的元素放置在隊列的最前面，以上面的為例，最大優先隊列排序應該為："John", "Jack", "Camila", "Tom"。

2.2.2 實現

實現一個優先隊列，有兩種選項：

設置優先級，根據優先級正確添加元素，然后和普通隊列一樣正常移除

設置優先級，和普通隊列一樣正常按順序添加，然后根據優先級移除

這里最小優先隊列和最大優先隊列我都采用第一種方式實現，大家可以嘗試一下第二種。

所以我只重寫enqueue()方法和print()方法，其他方法和上面的普通隊列完全相同。完整代碼見我的github。

實現最小優先隊列：

// 定義最小優先隊列
function MinPriorityQueue () {
  this.items = [];

  this.enqueue = enqueue;
  this.dequeue = dequeue;
  this.front = front;
  this.isEmpty = isEmpty;
  this.size = size;
  this.clear = clear;
  this.print = print;
}

實現最小優先隊列enqueue()方法和print()方法：

// 優先隊列添加元素，要根據優先級判斷在隊列中的插入順序
function enqueue (element, priority) {
  var queueElement = {
    element: element,
    priority: priority
  };

  if (this.isEmpty()) {
    this.items.push(queueElement);
  } else {
    var added = false;

    for (var i = 0; i < this.size(); i++) {
      if (queueElement.priority < this.items[i].priority) {
        this.items.splice(i, 0, queueElement);
        added = true;
        break ;
      }
    }

    if (!added) {
      this.items.push(queueElement);
    }
  }
}

// 打印隊列里的元素
function print () {
  var strArr = [];

  strArr = this.items.map(function (item) {
    return `${item.element}->${item.priority}`;
  });

  console.log(strArr.toString());
}

最小優先隊列測試：

// 創建最小優先隊列minPriorityQueue實例
var minPriorityQueue = new MinPriorityQueue();

console.log(minPriorityQueue.isEmpty());     // true
minPriorityQueue.enqueue("John", 1);         // undefined
minPriorityQueue.enqueue("Jack", 3);         // undefined
minPriorityQueue.enqueue("Camila", 2);       // undefined
minPriorityQueue.enqueue("Tom", 3);          // undefined
minPriorityQueue.print();                    // "John->1,Camila->2,Jack->3,Tom->3"
console.log(minPriorityQueue.size());        // 4
console.log(minPriorityQueue.isEmpty());     // false
minPriorityQueue.dequeue();                  // {element: "John", priority: 1}
minPriorityQueue.dequeue();                  // {element: "Camila", priority: 2}
minPriorityQueue.print();                    // "Jack->3,Tom->3"
minPriorityQueue.clear();                    // undefined
console.log(minPriorityQueue.size());        // 0

實現最大優先隊列

最大優先隊列只要將優先級的判斷改為大于號">"就可以了：

// 最大優先隊列MaxPriorityQueue類
function MaxPriorityQueue () {
  this.items = [];

  this.enqueue = enqueue;
  this.dequeue = dequeue;
  this.front = front;
  this.isEmpty = isEmpty;
  this.size = size;
  this.clear = clear;
  this.print = print;
}

// 優先隊列添加元素，要根據優先級判斷在隊列中的插入順序
function enqueue (element, priority) {
  var queueElement = {
    element: element,
    priority: priority
  };

  if (this.isEmpty()) {
    this.items.push(queueElement);
  } else {
    var added = false;

    for (var i = 0; i < this.items.length; i++) {
      // 注意，只需要將這里改為大于號就可以了
      if (queueElement.priority > this.items[i].priority) {
        this.items.splice(i, 0, queueElement);
        added = true;
        break ;
      }
    }

    if (!added) {
      this.items.push(queueElement);
    }
  }
}

最大優先隊列測試：

// 創建最大優先隊列maxPriorityQueue實例
var maxPriorityQueue = new MaxPriorityQueue();

console.log(maxPriorityQueue.isEmpty());     // true
maxPriorityQueue.enqueue("John", 1);         // undefined
maxPriorityQueue.enqueue("Jack", 3);         // undefined
maxPriorityQueue.enqueue("Camila", 2);       // undefined
maxPriorityQueue.enqueue("Tom", 3);          // undefined
maxPriorityQueue.print();                    // "Jack->3,Tom->3,Camila->2,John->1"
console.log(maxPriorityQueue.size());        // 4
console.log(maxPriorityQueue.isEmpty());     // false
maxPriorityQueue.dequeue();                  // {element: "Jack", priority: 3}
maxPriorityQueue.dequeue();                  // {element: "Tom", priority: 3}
maxPriorityQueue.print();                    // "Camila->2,John->1"
maxPriorityQueue.clear();                    // undefined
console.log(maxPriorityQueue.size());        // 0

2.3 循環隊列

還有一種隊列實現叫做循環隊列。

循環隊列的一個例子就是擊鼓傳花游戲（Hot Potato）。在這個游戲中，孩子們圍城一個圓圈，擊鼓的時候把花盡快的傳遞給旁邊的人。某一時刻擊鼓停止，這時花在誰的手里，誰就退出圓圈直到游戲結束。重復這個過程，直到只剩一個孩子（勝者）。

下面我們在普通隊列的基礎上，實現一個模擬的擊鼓傳花游戲：

// 實現擊鼓傳花
function hotPotato (nameList, num) {
  var queue = new Queue();

  for (var i = 0; i < nameList.length; i++) {
    queue.enqueue(nameList[i]);
  }

  var eliminated = "";

  while (queue.size() > 1) {
    // 循環num次，隊首出來去到隊尾
    for (var i = 0; i < num; i++) {
      queue.enqueue(queue.dequeue());
    }
    // 循環num次過后，移除當前隊首的元素
    eliminated = queue.dequeue();
    console.log(`${eliminated}在擊鼓傳花中被淘汰！`);
  }

  // 最后只剩一個元素
  return queue.dequeue();
}

// 測試
var nameList = ["John", "Jack", "Camila", "Ingrid", "Carl"];
var winner = hotPotato(nameList, 10);
console.log(`最后的勝利者是：${winner}`);

執行結果為：

// John在擊鼓傳花中被淘汰！
// Ingrid在擊鼓傳花中被淘汰！ 
// Jack在擊鼓傳花中被淘汰！
// Camila在擊鼓傳花中被淘汰！
// 最后的勝利者是：Carl

三、結束

本文會同步到我的個人博客，完整代碼可以到我的github倉庫查看，如果對你有幫助的話歡迎點一個Star~~

歡迎關注我的公眾號

GPU云服務器云服務器 javascript實現隊列服務器03還是08 服務器03和08 VoLLcloudh&amp03

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

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

分布式代理爬蟲:架構篇

摘要：降低的結果可能有三個隨著數據量的增大的性能受到了一定的影響知乎校驗器在把中的代理消費完之后，由于是定時任務，所以導致某段時間內新鮮的空缺。歷時大致兩個月，到現在終于完成了分布式代理抓取爬蟲，目前開源在了Github上。寫這個項目的原因主要有兩點，一是自己平時的部分工作需要和爬蟲打交道，代理IP在有的時候可以發揮非常重要的作用，調研過一些開源的代理IP采集程序，發現在抓取、解析、校驗、...

qujian 2019-07-31 11:04 評論0 收藏0
100行代碼實現任務隊列

摘要：最近剛看完多線程，為了加深印象，按照分鐘實現延遲消息功能的思路，實現了一個簡易版的異步隊列。讀取任務時，計算當前和，取出需要執行的任務，使用多線程的形式執行。加鎖的主要作用是防止多線程同時操作文件讀寫，影響數據一致性。最近剛看完python多線程，為了加深印象，按照1分鐘實現延遲消息功能的思路，實現了一個簡易版的異步隊列。高效延時消息，包含兩個重要的數據結構： 1.環形隊列，例...

xorpay 2019-07-25 11:40 評論0 收藏0
多線程+代理池爬取天天基金網、股票數據(無需使用爬蟲框架)

摘要：本次使用天天基金網進行爬蟲，該網站具有反爬機制，同時數量足夠大，多線程效果較為明顯。技術路線代理池多線程爬蟲與反爬編寫思路首先，開始分析天天基金網的一些數據。一旦使用多線程，則需要考慮到數據的讀寫順序問題。 @[TOC] 簡介提到爬蟲，大部分人都會想到使用Scrapy工具，但是僅僅停留在會使用的階段。為了增加對爬蟲機制的理解，我們可以手動實現多線程的爬蟲過程，同時，引入IP代理池進行...

jaysun 2019-07-31 10:14 評論0 收藏0