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