55a97169f757beb0f53c51843d6a8a87f6392612
4 interface PriorityQueueNode
<T
> {
12 * @typeParam T - Type of priority queue data.
15 export class PriorityQueue
<T
> {
16 private nodeArray
!: Array<PriorityQueueNode
<T
>>
17 /** The size of the priority queue. */
19 /** The maximum size of the priority queue. */
20 public maxSize
!: number
22 public constructor () {
27 * Enqueue data into the priority queue.
29 * @param data - Data to enqueue.
30 * @param priority - Priority of the data. Lower values have higher priority.
31 * @returns The new size of the priority queue.
33 public enqueue (data
: T
, priority
?: number): number {
34 priority
= priority
?? 0
36 for (const [index
, node
] of this.nodeArray
.entries()) {
37 if (node
.priority
> priority
) {
38 this.nodeArray
.splice(index
, 0, { data
, priority
})
44 this.nodeArray
.push({ data
, priority
})
46 return this.incrementSize()
50 * Dequeue data from the priority queue.
52 * @returns The dequeued data or `undefined` if the priority queue is empty.
54 public dequeue (): T
| undefined {
58 return this.nodeArray
.shift()?.data
62 * Peeks at the first data.
63 * @returns The first data or `undefined` if the priority queue is empty.
65 public peekFirst (): T
| undefined {
66 return this.nodeArray
[0]?.data
70 * Peeks at the last data.
71 * @returns The last data or `undefined` if the priority queue is empty.
73 public peekLast (): T
| undefined {
74 return this.nodeArray
[this.nodeArray
.length
- 1]?.data
78 * Clears the priority queue.
80 public clear (): void {
87 * Increments the size of the deque.
89 * @returns The new size of the deque.
91 private incrementSize (): number {
93 if (this.size
> this.maxSize
) {
94 this.maxSize
= this.size