js实现queue

实现队列的基本方法

队列是一种先进先出（FIFO）的数据结构，可以通过数组或链表实现。以下是使用JavaScript实现队列的几种方法。

使用数组实现队列

JavaScript数组原生支持队列操作，通过push和shift方法可以实现队列的基本功能。

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

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    return this.items.shift();
  }

  front() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    return this.items[0];
  }

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

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

  print() {
    console.log(this.items.toString());
  }
}

使用链表实现队列

链表实现队列可以避免数组shift操作的高时间复杂度（O(n)），链表实现的时间复杂度为O(1)。

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedListQueue {
  constructor() {
    this.front = null;
    this.rear = null;
    this.size = 0;
  }

  enqueue(value) {
    const newNode = new Node(value);
    if (this.rear === null) {
      this.front = newNode;
      this.rear = newNode;
    } else {
      this.rear.next = newNode;
      this.rear = newNode;
    }
    this.size++;
  }

  dequeue() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    const removedNode = this.front;
    this.front = this.front.next;
    if (this.front === null) {
      this.rear = null;
    }
    this.size--;
    return removedNode.value;
  }

  peek() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    return this.front.value;
  }

  isEmpty() {
    return this.size === 0;
  }

  getSize() {
    return this.size;
  }

  print() {
    let current = this.front;
    const values = [];
    while (current) {
      values.push(current.value);
      current = current.next;
    }
    console.log(values.join(' -> '));
  }
}

使用两个栈实现队列

通过两个栈可以模拟队列的行为，其中一个栈用于入队操作，另一个栈用于出队操作。

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

  enqueue(element) {
    this.stack1.push(element);
  }

  dequeue() {
    if (this.stack2.length === 0) {
      while (this.stack1.length > 0) {
        this.stack2.push(this.stack1.pop());
      }
    }
    if (this.stack2.length === 0) {
      return "Queue is empty";
    }
    return this.stack2.pop();
  }

  peek() {
    if (this.stack2.length === 0) {
      while (this.stack1.length > 0) {
        this.stack2.push(this.stack1.pop());
      }
    }
    if (this.stack2.length === 0) {
      return "Queue is empty";
    }
    return this.stack2[this.stack2.length - 1];
  }

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

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

性能比较

• 数组实现：简单易用，但shift操作的时间复杂度为O(n)，不适合频繁出队操作。
• 链表实现：入队和出队操作均为O(1)，适合频繁操作。
• 双栈实现：虽然可以模拟队列，但某些操作的时间复杂度可能达到O(n)，不如链表高效。

根据实际需求选择合适的实现方式。链表实现通常是最优选择，尤其在高性能场景下。