js实现反向队列

使用数组实现反向队列

JavaScript中可以通过数组的push()和shift()方法实现队列，反向队列则可以使用unshift()和pop()方法。

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

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

  dequeue() {
    if (this.isEmpty()) return "Underflow";
    return this.items.pop();
  }

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

  front() {
    if (this.isEmpty()) return "No elements in Queue";
    return this.items[this.items.length - 1];
  }
}

使用链表实现反向队列

链表实现反向队列需要维护头尾指针，入队操作在头部插入，出队操作从尾部移除。

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

class ReverseQueue {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  enqueue(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head = newNode;
    }
  }

  dequeue() {
    if (!this.head) return null;
    if (this.head === this.tail) {
      const value = this.head.value;
      this.head = null;
      this.tail = null;
      return value;
    }
    let current = this.head;
    while (current.next !== this.tail) {
      current = current.next;
    }
    const value = this.tail.value;
    this.tail = current;
    this.tail.next = null;
    return value;
  }
}

性能比较

数组实现的优点是代码简洁，但在频繁操作时可能遇到性能问题，因为unshift()和pop()操作的时间复杂度在最坏情况下是O(n)。

链表实现虽然代码复杂，但所有操作的时间复杂度都是O(1)，适合高频操作场景。

实际应用示例

const rq = new ReverseQueue();
rq.enqueue(10);
rq.enqueue(20);
rq.enqueue(30);
console.log(rq.dequeue()); // 输出10
console.log(rq.dequeue()); // 输出20

反向队列常用于需要后进先出但又需要队列接口的场景，如某些消息处理系统或特殊算法实现。