JavaScript 算法 1_2 先进先出队列 (链表实现)

队列, 先进先出, 和食堂排队打饭类似

目录

• JavaScript 算法 1_2 先进先出队列 (链表实现)
  • 1. 类定义
  • 2. 构造链表
  • 3. 从表头插入和删除元素
  • 4. 使用

1. 类定义

// 类定义
class Queue{
  constructor() {
    // 队头元素, 包括 next 和 ele
    this.first = null;
    // 队尾元素
    this.last = null;
    this.count = 0;
  }
  get nodeConstruct(){
    return {ele: null, next: null}
  }
  isEmpty(){
    return this.count === 0;
  }
  size(){
    return this.count;
  }

  /**
   * 队尾添加元素
   * @param item 要添加的元素
   */
  enqueue(item){
    let oldLast = this.last;
    this.last = {};
    Object.assign(this.last, this.nodeConstruct);
    this.last.ele = item;

    if( this.isEmpty() ) this.first = this.last;
    else oldLast.next = this.last;
    this.count++;
  }

  /**
   * 从队首删除元素并返回
   * @returns {*|null}
   */
  dequeue(){
    if(this.isEmpty()) {
      throw new Error('无元素可删');
    }
    let top = this.first.ele;
    this.first = this.first.next;
    this.count--;
    if(this.isEmpty()){
      this.last = null;
    }
    return top;
  }
  // 下回分解迭代器
  // [Symbol.iterator](){
  //
  // }
}

实现了队列分布先进先出的方式

2. 构造链表

get nodeConstruct(){
    return {ele: null, next: null}
  }

使用了 nodeConstruct 变量存储链表结构

3. 从表头插入和删除元素

**
   * 队尾添加元素
   * @param item 要添加的元素
   */
  enqueue(item){
    let oldLast = this.last;
    this.last = {};
    Object.assign(this.last, this.nodeConstruct);
    this.last.ele = item;

    if( this.isEmpty() ) this.first = this.last;
    else oldLast.next = this.last;
    this.count++;
  }

  /**
   * 从队首删除元素并返回
   * @returns {*|null}
   */
  dequeue(){
    if(this.isEmpty()) {
      throw new Error('无元素可删');
    }
    let top = this.first.ele;
    this.first = this.first.next;
    this.count--;
    if(this.isEmpty()){
      this.last = null;
    }
    return top;
  }

• 插入时先保存尾部节点, 后转换尾部节点, 判断是否是空节点
• 删除时移除队首元素并返回
• 注意元素数为0时

4. 使用

const queue = new Queue();
queue.enqueue(12);
queue.enqueue('apple');

let dequeue = queue.dequeue();
console.log(dequeue);

queue.enqueue([11, 13]);
queue.enqueue({age: 15});
queue.enqueue('小歪');

dequeue = queue.dequeue();
console.log(dequeue);
/*
12
Queue {
  first: { ele: 'apple', next: { ele: [Array], next: [Object] } },
  last: { ele: '小歪', next: null },
  count: 4
}
*/