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 public pop (): T
| undefined {
69 if (this.head
== null) {
72 const tail
= this.tail
73 this.tail
= (this.tail
as Node
<T
>).prev
74 if (this.tail
== null) {
77 this.tail
.next
= undefined
84 * Shifts a value from the deque.
86 * @returns The shifted value or `undefined` if the deque is empty.
88 public shift (): T
| undefined {
89 if (this.head
== null) {
92 const head
= this.head
93 this.head
= this.head
.next
94 if (this.head
== null) {
97 this.head
.prev
= undefined
104 * Peeks at the first value.
105 * @returns The first value or `undefined` if the queue is empty.
107 public peekFirst (): T
| undefined {
108 return this.head
?.value
112 * Peeks at the last value.
113 * @returns The last value or `undefined` if the queue is empty.
115 public peekLast (): T
| undefined {
116 return this.tail
?.value
122 public clear (): void {
123 this.head
= undefined
124 this.tail
= undefined
130 * Returns an iterator for the deque.
132 * @returns An iterator for the deque.
133 * @see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Iteration_protocols
135 [Symbol
.iterator
] (): Iterator
<T
> {
149 node
= node
.next
as Node
<T
>
155 private incrementSize (): number {
157 if (this.size
> this.maxSize
) {
158 this.maxSize
= this.size