JavaScript數據結構與算法（四）隊列和雙端隊列

jindong 發布于2019-08-26 14:01 / 3080人閱讀

摘要：我們已經學習了棧，隊列和棧非常類似，但是隊列遵循的是先進先出原則的一組有序的項，并從頂部移除元素，但是最新添加的元素必須排在隊列的末尾。恩，我們的前輩就提出了雙端隊列，允許用戶在隊首進行添加和刪除元素的操作，隊尾也是一樣。

我們已經學習了棧，隊列和棧非常類似，但是隊列遵循的是先進先出（FIFO）原則的一組有序的項，并從頂部移除元素，但是最新添加的元素必須排在隊列的末尾。在生活中也有隊列的應用，比如我們在售票處排隊等票，隊頭的人先拿到票，就走了，而新來的人，就必須排在隊偉文明排隊。

隊列 創建隊列

class Queue {
  constructor() {
    this.count = 0;
    this.lowestCount = 0;//追蹤隊列的第一個元素
    this.items = {};
  }

向隊列添加元素

enqueue(element) {
    this.items[this.count] = element;
    this.count++;
  }

細節就是要注意到隊列只能在尾部添加元素

檢查隊列是否為空并獲取它的長度

size() {
    return this.count - this.lowestCount;
  };
isEmpty() {
    return this.size() === 0;
  };

從隊列移除元素

dequeue() {
    //判斷是否為空
    if (this.isEmpty()) {
      return undefined;
    }
    const result = this.items[this.lowestCount];
    delete this.items[this.lowestCount];
    this.lowestCount++;
    return result;
  }

查看隊列頭元素

 peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.lowestCount];
  }

清空隊列

clear() {
    this.items = {};
    this.count = 0;
    this.lowestCount = 0;
  }

創建toString方法

toString() {
    if (this.isEmpty()) {
      return "";
    }
    let objString = `${this.items[this.lowestCount]}`;
    for (let i = this.lowestCount + 1; i < this.count; i++) {
      objString = `${objString},${this.items[i]}`;
    }
    return objString;
  }

好的，我們的隊列到此就創建完畢了。但是，有些小伙伴就有疑問了，還是排隊情景，假如我已經離開售票廳了，但是我還想再問些簡單問題，直接到前臺詢問，這就是隊首添加元素了，還有隊尾的人突然有事離開了，這也是刪除元素操作呀，那這個用隊列怎么實現。恩，我們的前輩就提出了雙端隊列，允許用戶在隊首進行添加和刪除元素的操作，隊尾也是一樣。

雙端隊列 創建雙端隊列

class Deque {
  constructor() {
    this.count = 0;
    this.lowestCount = 0;
    this.items = {};
  }

添加操作 隊首添加元素

addFront(element) {
    if (this.isEmpty()) {//空隊列
      this.addBack(element);
    } else if (this.lowestCount > 0) {//之前被刪除，重新添加
      this.lowestCount--;
      this.items[this.lowestCount] = element;
    } else {
      for (let i = this.count; i > 0; i--) {
        this.items[i] = this.items[i - 1];
      }
      this.count++;
      this.items[0] = element;
    }
  }

隊尾添加元素

addBack(element) {
    this.items[this.count] = element;
    this.count++;
  }

刪除操作 隊首刪除元素

removeFront() {
    if (this.isEmpty()) {
      return undefined;
    }
    const result = this.items[this.lowestCount];
    delete this.items[this.lowestCount];
    this.lowestCount++;
    return result;
  }

隊尾刪除元素

removeBack() {
    if (this.isEmpty()) {
      return undefined;
    }
    this.count--;
    const result = this.items[this.count];
    delete this.items[this.count];
    return result;
  }

查詢操作 返回隊首元素

peekFront() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.lowestCount];
  }

返回隊尾元素

peekBack() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.count - 1];
  }

隊列的實踐 模擬擊鼓傳花游戲

情景：孩子們圍城一圈，把花傳遞給身邊的人，某一時刻停止，花在誰手上，誰就推出。重復這個操作，剩下的最后一個人就是勝利者。
代碼實現：

function hotPotato(elementsList, num) {
  const queue = new Queue();
  const elimitatedList = [];

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

  while (queue.size() > 1) {
    for (let i = 0; i < num; i++) {
      queue.enqueue(queue.dequeue());
    }
    elimitatedList.push(queue.dequeue());
  }

  return {
    eliminated: elimitatedList,
    winner: queue.dequeue()
  };
}

回文檢查器

檢查一個詞組揮著字符串是否為回文。
代碼實現：

function palindromeChecker(aString) {
  if (
    aString === undefined
    || aString === null
    || (aString !== null && aString.length === 0)
  ) {
    return false;
  }
  const deque = new Deque();
  const lowerString = aString.toLocaleLowerCase().split(" ").join("");
  let firstChar;
  let lastChar;

  for (let i = 0; i < lowerString.length; i++) {
    deque.addBack(lowerString.charAt(i));
  }

  while (deque.size() > 1) {
    firstChar = deque.removeFront();
    lastChar = deque.removeBack();
    if (firstChar !== lastChar) {
      return false;
    }
  }

  return true;
};

GPU云服務器云服務器 javascript實現隊列走迷宮算法隊列c語言鏈表數據結構隊列 java隊列處理數據

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

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

Java中的Queue與Deque

摘要：最小初始化容量。它作為堆棧隊列雙端隊列的操作和的操作是一致的，只是內部的實現不同。根據元素內容查找和刪除的效率比較低，為。但是接口有對應的并發實現類類。 Queue接口的實現類 Queue接口作為隊列數據結構，java在實現的時候，直接定義了Deque接口（雙端隊列）來繼承Queue接口，并且只實現Deque接口。這樣java中的雙端隊列就囊括了隊列、雙端隊列、堆棧（Deque接口又定...

zhangrxiang 2019-08-19 11:14 評論0 收藏0
重讀《學習JavaScript數據結構與算法-第三版》- 第5章隊列

摘要：定場詩馬瘦毛長蹄子肥，兒子偷爹不算賊，瞎大爺娶個瞎大奶奶，老兩口過了多半輩，誰也沒看見誰前言本章為重讀學習數據結構與算法第三版的系列文章，主要講述隊列數據結構雙端隊列數據結構以及隊列相關應用。定場詩馬瘦毛長蹄子肥，兒子偷爹不算賊，瞎大爺娶個瞎大奶奶，老兩口過了多半輩，誰也沒看見誰！前言本章為重讀《學習JavaScript數據結構與算法-第三版》的系列文章，主要講述隊列數據結構、...

charles_paul 2019-08-26 14:05 評論0 收藏0
Java 中的線程安全容器

摘要：一同步容器常用的一些容器例如都不是線程安全的，最簡單的將這些容器變為線程安全的方式，是給這些容器所有的方法都加上關鍵字。為了降低哈希沖突的成本，在鏈表長度超過時，將鏈表轉換為紅黑樹。一、同步容器常用的一些容器例如 ArrayList、HashMap、都不是線程安全的，最簡單的將這些容器變為線程安全的方式，是給這些容器所有的方法都加上 synchronized 關鍵字。 Java 的...

Seay 2019-08-16 17:38 評論0 收藏0
LeetCode 之 JavaScript 解答第641題 —— 設計雙端隊列（Design Cir

摘要：小鹿題目設計實現雙端隊列。你的實現需要支持以下操作構造函數雙端隊列的大小為。獲得雙端隊列的最后一個元素。檢查雙端隊列是否為空。數組頭部刪除第一個數據。以上數組提供的使得更方便的對數組進行操作和模擬其他數據結構的操作，棧隊列等。 Time：2019/4/15Title: Design Circular DequeDifficulty: MediumAuthor: 小鹿題目：Desi...

Freeman 2019-08-23 16:58 評論0 收藏0
Fork/Join框架簡介

摘要：第二步執行任務并合并結果。使用兩個類來完成以上兩件事情我們要使用框架，必須首先創建一個任務。用于有返回結果的任務。如果任務順利執行完成了，則設置任務狀態為，如果出現異常，則紀錄異常，并將任務狀態設置為。 1. 什么是Fork/Join框架 Fork/Join框架是Java7提供了的一個用于并行執行任務的框架，是一個把大任務分割成若干個小任務，最終匯總每個小任務結果后得到大任務結果的...

W_BinaryTree 2019-08-14 11:38 評論0 收藏0