1 // Copyright Jerome Benoit. 2023. All Rights Reserved.
8 public constructor (value
: T
) {
15 * Implemented with a doubly linked list.
17 * @typeParam T - Type of deque values.
19 export class Deque
<T
> {
20 private head
?: Node
<T
>
21 private tail
?: Node
<T
>
22 /** The size of the deque. */
24 /** The maximum size of the deque. */
25 public maxSize
!: number
27 public constructor () {
32 * Appends a value to the deque.
34 * @param value - Value to append.
35 * @returns The new size of the queue.
37 public push (value
: T
): number {
38 const node
= new Node(value
)
39 if (this.tail
== null) {
40 this.head
= this.tail
= node
43 this.tail
= this.tail
.next
= node
45 return this.incrementSize()
49 * Prepends a value to the deque.
51 * @param value - Value to prepend.
52 * @returns The new size of the queue.
54 public unshift (value
: T
): number {
55 const node
= new Node(value
)
56 if (this.head
== null) {
57 this.head
= this.tail
= node
60 this.head
= this.head
.prev
= node
62 return this.incrementSize()
66 * Pops a value from the deque.
68 * @returns The popped value or `undefined` if the deque is empty.
70 public pop (): T
| undefined {
71 if (this.head
== null) {
74 const tail
= this.tail
75 this.tail
= (this.tail
as Node
<T
>).prev
76 if (this.tail
== null) {
79 this.tail
.next
= undefined
86 * Shifts a value from the deque.
88 * @returns The shifted value or `undefined` if the deque is empty.
90 public shift (): T
| undefined {
91 if (this.head
== null) {
94 const head
= this.head
95 this.head
= this.head
.next
96 if (this.head
== null) {
99 this.head
.prev
= undefined
106 * Peeks at the first value.
107 * @returns The first value or `undefined` if the deque is empty.
109 public peekFirst (): T
| undefined {
110 return this.head
?.value
114 * Peeks at the last value.
115 * @returns The last value or `undefined` if the deque is empty.
117 public peekLast (): T
| undefined {
118 return this.tail
?.value
124 public clear (): void {
125 this.head
= undefined
126 this.tail
= undefined
132 * Returns an iterator for the deque.
134 * @returns An iterator for the deque.
135 * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
137 [Symbol
.iterator
] (): Iterator
<T
> {
151 node
= node
.next
as Node
<T
>
158 * Returns an backward iterator for the deque.
160 * @returns An backward iterator for the deque.
161 * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
163 backward (): Iterable
<T
> {
165 [Symbol
.iterator
]: (): Iterator
<T
> => {
179 node
= node
.prev
as Node
<T
>
187 private incrementSize (): number {
189 if (this.size
> this.maxSize
) {
190 this.maxSize
= this.size