队列

队列是一种先进先出（FIFO）的数据结构，它只允许在表的前端进行删除操作，而在表的后端进行插入操作。队列中没有元素时，称为空队列。

基本操作

队列主要有以下几种基本操作：

• enqueue(element): 在队列尾部添加一个元素
• dequeue(): 移除队列头部的元素并返回
• peek(): 查看队列头部的元素但不移除
• isEmpty(): 检查队列是否为空
• size(): 获取队列中元素的数量

实现

队列可以使用栈或链表来实现。

栈实现

使用栈实现队列时，需要使用两个栈，一个栈用于存储元素，另一个栈用于辅助操作。当需要进行出队操作时，将第一个栈中的元素依次弹出并压入第二个栈中，然后弹出第二个栈的栈顶元素，即为出队元素。当需要进行入队操作时，直接将元素压入第一个栈中。

class Queue {
  constructor() {
    this.stack1 = [];
    this.stack2 = [];  
  }

  enqueue(element) {
    this.stack1.push(element);  
  }
  dequeue() {
     for (let i = this.stack1.length - 1; i >= 0; i--) {
        this.stack2.push(this.stack1.pop()!);
    }
    const item = this.stack2.pop();
    for (let i = this.stack2.length - 1; i >= 0; i--) {
        this.stack1.push(this.stack2.pop()!);
    }
    return item || null;
  }
  peek() {
    return this.stack1[0] || null;
  }

  isEmpty() {
    return this.stack1.length === 0;
  }

  size() {
    return this.stack1.length;
  }
}

链表实现

使用链表实现队列时，需要使用一个链表和两个指针，一个指针指向链表的头部，另一个指针指向链表的尾部。当需要进行出队操作时，将头部指针指向的节点移除，并返回该节点的值。当需要进行入队操作时，将新节点插入到尾部指针指向的节点之后。

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  } 
}
class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  /**
   * 入队操作
   */ 
  enqueue(element) {
    const node = new Node(element);
    // !如果队列为空，则将头部和尾部指针都指向新节点
    if (this.head === null) {
      this.head = node;
      this.tail = node;  
    } else { // !否则，将新节点插入到尾部指针指向的节点之后,并将尾部指针指向新节点。
      this.tail.next = node;
      this.tail = node; 
    }  
    this.length++;
  }
  /**
   * 出队操作
   */
  dequeue() {
    //!如果队列为空，则返回null
    if (this.head === null) {
      return null;
    }
    //!否则，将头部指针指向的节点移除，并返回该节点的值。
    const node = this.head;
    this.head = this.head.next;
    this.length--;
    return node.value; 
  }
  /**
   * 查看队列头部的元素但不移除
   */
  peek() {
    return this.head?.value || null;
  }
  /**
   * 检查队列是否为空
   */
  isEmpty() {
    return this.length === 0;
  }
  /**
   * 获取队列中元素的数量
   */
  size() {
    return this.length; 
  }
}

链表和栈的性能比较

链表和栈都可以用来实现队列，但是它们的性能有所不同。 链表实现的队列在进行入队和出队操作时，只需要修改指针的指向即可，时间复杂度为O(1)。但是链表的空间开销较大，需要为每个节点分配额外的空间。 栈实现的队列在进行入队和出队操作时，需要将元素压入或弹出栈中，时间复杂度为O(n)。但是栈的空间开销较小，只需要为栈分配足够的空间即可。