JavaScript数据结构与算法（四）队列和双端队列

jindong 发布于2019-08-26 14:01 / 3018人阅读

摘要：我们已经学习了栈，队列和栈非常类似，但是队列遵循的是先进先出原则的一组有序的项，并从顶部移除元素，但是最新添加的元素必须排在队列的末尾。恩，我们的前辈就提出了双端队列，允许用户在队首进行添加和删除元素的操作，队尾也是一样。

我们已经学习了栈，队列和栈非常类似，但是队列遵循的是先进先出（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队列处理数据

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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