1 // Copyright Jerome Benoit. 2023. All Rights Reserved.
4 * Linked list node interface.
6 * @typeParam T - Type of linked list node data.
9 export interface ILinkedListNode
<T
> {
11 next
?: ILinkedListNode
<T
>
12 prev
?: ILinkedListNode
<T
>
17 * Implemented with a doubly linked list.
19 * @typeParam T - Type of deque data.
22 export class Deque
<T
> {
23 private head
?: ILinkedListNode
<T
>
24 private tail
?: ILinkedListNode
<T
>
25 /** The size of the deque. */
27 /** The maximum size of the deque. */
28 public maxSize
!: number
30 public constructor () {
35 * Appends data to the deque.
37 * @param data - Data to append.
38 * @returns The new size of the queue.
40 public push (data
: T
): number {
41 const node
= { data
, prev
: this.tail
}
42 if (this.tail
== null) {
43 this.head
= this.tail
= node
45 this.tail
= this.tail
.next
= node
47 return this.incrementSize()
51 * Prepends data to the deque.
53 * @param data - Data to prepend.
54 * @returns The new size of the queue.
56 public unshift (data
: T
): number {
57 const node
= { data
, next
: this.head
}
58 if (this.head
== null) {
59 this.head
= this.tail
= node
61 this.head
= this.head
.prev
= node
63 return this.incrementSize()
67 * Pops data from the deque.
69 * @returns The popped data or `undefined` if the deque is empty.
71 public pop (): T
| undefined {
72 if (this.head
== null) {
75 const tail
= this.tail
76 this.tail
= this.tail
?.prev
77 if (this.tail
== null) {
87 * Shifts data from the deque.
89 * @returns The shifted data or `undefined` if the deque is empty.
91 public shift (): T
| undefined {
92 if (this.head
== null) {
95 const head
= this.head
96 this.head
= this.head
.next
97 if (this.head
== null) {
100 delete this.head
.prev
107 * Peeks at the first data.
108 * @returns The first data or `undefined` if the deque is empty.
110 public peekFirst (): T
| undefined {
111 return this.head
?.data
115 * Peeks at the last data.
116 * @returns The last data or `undefined` if the deque is empty.
118 public peekLast (): T
| undefined {
119 return this.tail
?.data
125 public clear (): void {
133 * Returns an iterator for the deque.
135 * @returns An iterator for the deque.
136 * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
138 [Symbol
.iterator
] (): Iterator
<T
> {
159 * Returns an backward iterator for the deque.
161 * @returns An backward iterator for the deque.
162 * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
164 backward (): Iterable
<T
> {
166 [Symbol
.iterator
]: (): Iterator
<T
> => {
188 private incrementSize (): number {
190 if (this.size
> this.maxSize
) {
191 this.maxSize
= this.size