JavaScript 数据结构与算法 之 队列和双端队列

简介: JavaScript 数据结构与算法 之 队列和双端队列

队列和双端队列

队列是遵循先进先出(FIFO,也称为先来先服务)原则的一组有序的项。队列在尾部添加新元素,并从顶部移除元素。最新添加的元素必须排在队列的末尾。

队列数据结构

class Queue {
  constructor() {
    this.count = 0;
    this.lowestCount = 0; // 用于追踪第一元素
    this.items = {};
  }
  // 向队尾添加一个新的项
  enqueue(item) {
    this.items[this.count] = item;
    this.count++;
  }
  // 从队列移除项
  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];
  }
  // 查看是否为空
  isEmpty() {
    return this.count - this.lowestCount === 0;
  }
  // 查看队列长度
  size() {
    return this.count - this.lowestCount;
  }
  // 清空队列
  clear() {
    this.items = {};
    this.count = 0;
    this.lowestCount = 0;
  }
  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;
  }
}
const queue = new Queue();
console.log(queue.isEmpty()); // true
queue.enqueue('John');
queue.enqueue('Jack');
console.log(queue.toString()); // John,Jack
queue.enqueue('Camila');
console.log(queue.toString()); // John, Jack, Camila
console.log(queue.size()); // 输出 3
console.log(queue.isEmpty()); // 输出 false
queue.dequeue(); // 移除 John
queue.dequeue(); // 移除 Jack
console.log(queue.toString()); // Camila

双端队列数据结构

双端队列( deque,或称 double-ended queue)是一种允许同时从前端和后端添加和移除元素的特殊队列。在计算机科学中,双端队列的一个常见应用是存储一系列的撤销操作。由于双端队列同时遵守了先进先出和后进先出原则,可以说它是把队列和栈相结合的一种数据结构。
class Deque {
  constructor() {
    this.count = 0;
    this.lowestCount = 0;
    this.items = {};
  }
  // 在队列前添加新元素
  addFront(item) {
    if (this.isEmpty()) {
      this.addBack(item);
    } else if (this.lowestCount > 0) {
      this.lowestCount--;
      this.items[this.lowestCount] = item;
    } else {
      for (let i = this.count; i > 0; i--) {
        this.items[i] = this.items[i - 1];
      }
      this.count++;
      this.lowestCount = 0;
      this.items[0] = item;
    }
  }
  // 在队尾添加新元素
  addBack(item) {
    this.items[this.count] = item;
    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];
  }
  // 查看是否为空
  isEmpty() {
    return this.count - this.lowestCount === 0;
  }
  // 查看队列长度
  size() {
    return this.count - this.lowestCount;
  }
  // 清空队列
  clear() {
    this.items = {};
    this.count = 0;
    this.lowestCount = 0;
  }
  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;
  }
}
const deque = new Deque();
console.log(deque.isEmpty()); // 输出 true
deque.addBack('John');
deque.addBack('Jack');
console.log(deque.toString()); // John, Jack
deque.addBack('Camila');
console.log(deque.toString()); // John, Jack, Camila
console.log(deque.size()); // 输出 3
console.log(deque.isEmpty()); // 输出 false
deque.removeFront(); // 移除 John
console.log(deque.toString()); // Jack, Camila
deque.removeBack(); // Camila 决定离开
console.log(deque.toString()); // Jack
deque.addFront('John'); // John 回来询问一些信息
console.log(deque.toString()); // John, Jack

队列应用

  • 循环队列-击鼓传花游戏
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(),
  };
}
const names = ['John', 'Jack', 'Camila', 'Ingrid', 'Carl'];
const result = hotPotato(names, 7);
result.eliminated.forEach(name => {
console.log(`${name}在击鼓传花游戏中被淘汰。 `);
});
console.log(`胜利者: ${result.winner}`);
  • 回文检查器
回文是正反都能读通的单词、词组、数或一系列字符的序列,例如 madam 或 racecar。
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 isEqual = true;
  let firstChar, lastChar;

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

  while (deque.size() > 1 && isEqual) {
    firstChar = deque.removeFront();
    lastChar = deque.removeBack();
    if (firstChar !== lastChar) {
      isEqual = false;
    }
  }
  return isEqual;
}
  • JS任务队列
当我们在浏览器中打开新标签时,就会创建一个任务队列。这是因为每个标签都是单线程处理所有的任务,称为事件循环。浏览器要负责多个任务,如渲染 HTML、执行 JavaScript 代码、处理用户交互(用户输入、鼠标点击等)、执行和处理异步请求。
相关文章
|
6天前
|
JavaScript 前端开发
Angular.js 应用中数据模式的删除操作实现
Angular.js 应用中数据模式的删除操作实现
16 0
|
1天前
|
机器学习/深度学习 存储 算法
数据结构与算法⑨(第三章_下)队列的概念和实现(力扣:225+232+622)(下)
数据结构与算法⑨(第三章_下)队列的概念和实现(力扣:225+232+622)
4 0
|
1天前
|
算法 前端开发 C语言
数据结构与算法⑨(第三章_下)队列的概念和实现(力扣:225+232+622)(上)
数据结构与算法⑨(第三章_下)队列的概念和实现(力扣:225+232+622)
11 0
|
5天前
|
前端开发 JavaScript 算法
JavaScript 中实现常见数据结构:栈、队列与树
JavaScript 中实现常见数据结构:栈、队列与树
|
6天前
|
存储 JSON JavaScript
Node.js 上开发一个 HTTP 服务器,监听某个端口,接收 HTTP POST 请求并处理传入的数据
Node.js 上开发一个 HTTP 服务器,监听某个端口,接收 HTTP POST 请求并处理传入的数据
14 0
|
7天前
|
存储 编译器 C语言
数据结构——顺序队列与链式队列的实现-2
数据结构——顺序队列与链式队列的实现
数据结构——顺序队列与链式队列的实现-2
|
7天前
|
存储 C语言
数据结构——顺序队列与链式队列的实现-1
数据结构——顺序队列与链式队列的实现
数据结构——顺序队列与链式队列的实现-1
|
7天前
栈与队列理解
栈与队列理解
13 1
|
7天前
|
存储 算法
数据结构与算法 栈与队列
数据结构与算法 栈与队列
13 0
数据结构与算法 栈与队列
|
7天前
|
C++
数据结构(顺序队列 循环队列
数据结构(顺序队列 循环队列
11 0