- 动态大小: 链表允许队列在运行时动态增长或缩小,而无需预先指定固定大小。这使得队列更加灵活,能够适应不同场景下的变化。
- 插入和删除效率高: 在链表中插入和删除元素的效率很高,只需修改指针即可,不需要像数组那样搬移大量元素。这使得队列的入队(enqueue)和出队(dequeue)操作在链表实现中更为高效。
class ListNode<T> {
val: T | null
prev: ListNode<T> | null
next: ListNode<T> | null
constructor(val?: T, prev?: ListNode<T>, next?: ListNode<T>) {
this.val = val || null
this.prev = prev || null
this.next = next || null
}
}
class Queue<T> {
private head: ListNode<T> | null = null
private tail: ListNode<T> | null = null
private len = 0
enqueue(item: T) {
const node = new ListNode(item)
if (this.head == null || this.tail == null) {
this.head = this.tail = node
} else {
this.tail.next = node
node.prev = this.tail
this.tail = node
}
this.len++
}
dequeue() {
if (this.head == null) return null
const val = this.head.val
this.head = this.head.next
if (this.head != null) this.head.prev = null
this.len--
return val
}
isEmpty() {
return this.head == null
}
size() {
return this.len
}
front() {
if (this.head == null) return null
return this.head.val
}
clear() {
this.head = null
this.tail = null
this.len = 0
}
}