Queue
June 24, 2025
04:33 AM
No headings found
Loading content...
Related Posts
Theory Data Structure And Algorithms
No headings found
Related Posts
Theory Data Structure And Algorithms
dequeue() (xoá phần tử đầu) sẽ có độ phức tạp O(n) do phải dồn lại các phần tử phía sau. Điều này không đáp ứng yêu cầu O(1)Để đảm bảo mọi thao tác đều O(1), nên dùng doubly linked list (danh sách liên kết đôi) với hai node giả (dummy head/tail).
Solution - Linked List
1class Node<T> {
2 value: T;
3 next: Node<T> | null;
4 prev: Node<T> | null;
5 constructor(value: T) {
6 this.value = value;
7 this.next = null;
8 this.prev = null;
9 }
10}
11
12export default class Queue<T> {
13 head: Node<T> | null;
14 tail: Node<T> | null;
15 _size: number;
16 constructor() {
17 this.head = null;
18 this.tail = null;
19 this._size = 0;
20 }
21
22 /**
23 * Adds an item to the back of the queue.
24 * @param {T} item The item to be pushed onto the queue.
25 * @return {number} The new length of the queue.
26 */
27 enqueue(item: T): number {
28 const node = new Node(item);
29 if (!this.tail) {
30 this.head = node;
31 this.tail = node;
32 } else {
33 this.tail.next = node;
34 node.prev = this.tail;
35 this.tail = node;
36 }
37 this._size++;
38 return this._size;
39 }
40
41 /**
42 * Removes an item from the front of the queue.
43 * @return {T | undefined} The item at the front of the queue if it is not empty, `undefined` otherwise.
44 */
45 dequeue(): T | undefined {
46 if (!this.head) return undefined;
47 const value = this.head!.value;
48 this.head = this.head.next;
49 if (this.head) {
50 this.head.prev = null;
51 } else {
52 this.tail = null;
53 }
54 this._size--;
55 return value;
56 }
57
58 /**
59 * Determines if the queue is empty.
60 * @return {boolean} `true` if the queue has no items, `false` otherwise.
61 */
62 isEmpty(): boolean {
63 return this._size === 0;
64 }
65
66 /**
67 * Returns the item at the front of the queue without removing it from the queue.
68 * @return {T | undefined} The item at the front of the queue if it is not empty, `undefined` otherwise.
69 */
70 front(): T | undefined {
71 return this.head?.value;
72 }
73
74 /**
75 * Returns the item at the back of the queue without removing it from the queue.
76 * @return {T | undefined} The item at the back of the queue if it is not empty, `undefined` otherwise.
77 */
78 back(): T | undefined {
79 return this.tail?.value;
80 }
81
82 /**
83 * Returns the number of items in the queue.
84 * @return {number} The number of items in the queue.
85 */
86 length(): number {
87 return this._size;
88 }
89}
90