[数据结构与算法]3__队列和双端队列__

队列和双端队列(先进先出)

创建队列

class Queue {
  constructor() {
    // 队列的大小
    this.count = 0;
    // 队列第一个元素
    this.lowestCount = 0;
    this.items = {};
  }
  // 向队列添加元素,新的项只能添加到队列末尾
  enqueue(element) {
    this.items[this.count] = element;
    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;
    // 或者
    // return this.size() === 0
  }
  // 返回队列包含的元素个数
  size() {
    return this.count - 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];
  }
  // 检测队列是否为空
  isEmpty() {
    return this.size() === 0;
  }
  // 清空队列
  clear() {
    this.items = {};
    this.count = 0;
    this.lowestCount = 0;
  }
  // 队列大小
  size() {
    return this.count - this.lowestCount;
  }
  // 打印
  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;
  }
}

循环队列——击鼓传花游戏

// elementsList传入的数组 num为随机数
function hotPotato(elementsList, num) {
  const queue = new Queue();
  // 被淘汰的人数组
  const eliminatedList = [];
  // 写入队列
  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());
    }
    // 把倒霉蛋拿出来
    eliminatedList.push(queue.dequeue());
  }

  return {
    eliminated: eliminatedList,
    // 最后的幸运儿
    winner: queue.dequeue(),
  };
}

回文检查器