Class Queue<E, R>

Array-backed queue with amortized O(1) enqueue/dequeue via an offset pointer and optional auto-compaction.

Remarks

Time O(1), Space O(1)

Example

// Sliding Window using Queue
    const nums = [2, 3, 4, 1, 5];
    const k = 2;
    const queue = new Queue<number>();

    let maxSum = 0;
    let currentSum = 0;

    nums.forEach(num => {
      queue.push(num);
      currentSum += num;

      if (queue.length > k) {
        currentSum -= queue.shift()!;
      }

      if (queue.length === k) {
        maxSum = Math.max(maxSum, currentSum);
      }
    });

    console.log(maxSum); // 7

Example

// Breadth-First Search (BFS) using Queue
    const graph: { [key in number]: number[] } = {
      1: [2, 3],
      2: [4, 5],
      3: [],
      4: [],
      5: []
    };

    const queue = new Queue<number>();
    const visited: number[] = [];

    queue.push(1);

    while (!queue.isEmpty()) {
      const node = queue.shift()!;
      if (!visited.includes(node)) {
        visited.push(node);
        graph[node].forEach(neighbor => queue.push(neighbor));
      }
    }

    console.log(visited); // [1, 2, 3, 4, 5]

Type Parameters

E = any
R = any
1. First In, First Out (FIFO): The core feature of a queue is its first in, first out nature. The element added to the queue first will be the one to be removed first.
2. Operations: The main operations include enqueue (adding an element to the end of the queue) and dequeue (removing and returning the element at the front of the queue). Typically, there is also a peek operation (looking at the front element without removing it).
3. Uses: Queues are commonly used to manage a series of tasks or elements that need to be processed in order. For example, managing task queues in a multi-threaded environment, or in algorithms for data structures like trees and graphs for breadth-first search.
4. Task Scheduling: Managing the order of task execution in operating systems or applications.
5. Data Buffering: Acting as a buffer for data packets in network communication.
6. Breadth-First Search (BFS): In traversal algorithms for graphs and trees, queues store elements that are to be visited.
7. Real-time Queuing: Like queuing systems in banks or supermarkets.

Hierarchy

LinearBase<E, R>
- Queue

Constructors

constructor

new Queue<E, R>(elements?, options?): Queue<E, R>
Create a Queue and optionally bulk-insert elements.
Type Parameters
- E = any
- R = any
Parameters
- Optionalelements: Iterable<E, any, any> | Iterable<R, any, any> = []
  Iterable of elements (or raw records if toElementFn is set).
- Optionaloptions: QueueOptions<E, R>
  Options such as toElementFn, maxLen, and autoCompactRatio.
Returns Queue<E, R>
New Queue instance.

Remarks
Time O(N), Space O(N)
Overrides LinearBase<E, R>.constructor
- Defined in data-structures/queue/queue.ts:82

Properties

`Protected` `Optional`_toElementFn

_toElementFn?: ((rawElement: R) => E)

The converter used to transform a raw element (R) into a public element (E).

Remarks

Time O(1), Space O(1).

Accessors

autoCompactRatio

get autoCompactRatio(): number
Get the compaction threshold (offset/size).

Returns number
Auto-compaction ratio in (0,1].

Remarks
Time O(1), Space O(1)
- Defined in data-structures/queue/queue.ts:123
set autoCompactRatio(value): void
Set the compaction threshold.
Parameters
- value: number
  New ratio; compacts when offset/size exceeds this value.
Returns void
void

Remarks
Time O(1), Space O(1)
- Defined in data-structures/queue/queue.ts:134

elements

get elements(): E[]
Get the underlying array buffer.

Returns E[]
Backing array of elements.

Remarks
Time O(1), Space O(1)
- Defined in data-structures/queue/queue.ts:99

first

get first(): undefined | E
Get the first element (front) without removing it.

Returns undefined | E
Front element or undefined.

Remarks
Time O(1), Space O(1)
- Defined in data-structures/queue/queue.ts:154

last

get last(): undefined | E
Get the last element (back) without removing it.

Returns undefined | E
Back element or undefined.

Remarks
Time O(1), Space O(1)
- Defined in data-structures/queue/queue.ts:164

length

get length(): number
Get the number of elements currently in the queue.

Returns number
Current length.

Remarks
Time O(1), Space O(1)
Overrides LinearBase.length
- Defined in data-structures/queue/queue.ts:144

maxLen

get maxLen(): number
Upper bound for length (if positive), or -1 when unbounded.

Returns number
Maximum allowed length.

Remarks
Time O(1), Space O(1)
Inherited from LinearBase.maxLen
- Defined in data-structures/base/linear-base.ts:100

offset

get offset(): number
Get the current start offset into the array.

Returns number
Zero-based offset.

Remarks
Time O(1), Space O(1)
- Defined in data-structures/queue/queue.ts:111

toElementFn

get toElementFn(): undefined | ((rawElement: R) => E)
Exposes the current toElementFn, if configured.

Returns undefined | ((rawElement: R) => E)
The converter function or undefined when not set.

Remarks
Time O(1), Space O(1).
Inherited from LinearBase.toElementFn
- Defined in data-structures/base/iterable-element-base.ts:47

Methods

`Protected`_createInstance

_createInstance(options?): this
(Protected) Create an empty instance of the same concrete class.
Parameters
- Optionaloptions: LinearBaseOptions<E, R>
  Options forwarded to the constructor.
Returns this
An empty like-kind queue instance.

Remarks
Time O(1), Space O(1)
Overrides LinearBase._createInstance
- Defined in data-structures/queue/queue.ts:490

`Protected`_createLike

_createLike<EM, RM>(elements?, options?): Queue<EM, RM>
(Protected) Create a like-kind queue and seed it from an iterable.
Type Parameters
- EM = E
- RM = R
Parameters
- Optionalelements: Iterable<EM, any, any> | Iterable<RM, any, any> = []
  Iterable used to seed the new queue.
- Optionaloptions: QueueOptions<EM, RM>
  Options forwarded to the constructor.
Returns Queue<EM, RM>
A like-kind Queue instance.

Remarks
Time O(N), Space O(N)
- Defined in data-structures/queue/queue.ts:505

`Protected`_getIterator

_getIterator(): IterableIterator<E, any, any>
(Protected) Iterate elements from front to back.

Returns IterableIterator<E, any, any>
Iterator of E.

Remarks
Time O(N), Space O(1)
Overrides LinearBase._getIterator
- Defined in data-structures/queue/queue.ts:466

`Protected`_getReverseIterator

_getReverseIterator(): IterableIterator<E, any, any>
(Protected) Iterate elements from back to front.

Returns IterableIterator<E, any, any>
Iterator of E.

Remarks
Time O(N), Space O(1)
Overrides LinearBase._getReverseIterator
- Defined in data-structures/queue/queue.ts:476

`Protected`_setAutoCompactRatio

_setAutoCompactRatio(value): void
(Protected) Set the internal auto-compaction ratio.
Parameters
- value: number
  New ratio to assign.
Returns void
void

Remarks
Time O(1), Space O(1)
- Defined in data-structures/queue/queue.ts:456

[iterator]

[iterator](...args): IterableIterator<E, any, any>
Returns an iterator over the structure's elements.
Parameters
- Rest...args: unknown[]
  Optional iterator arguments forwarded to the internal iterator.
Returns IterableIterator<E, any, any>
An IterableIterator<E> that yields the elements in traversal order.

Remarks
Producing the iterator is O(1); consuming the entire iterator is Time O(n) with O(1) extra space.
Inherited from LinearBase.[iterator]
- Defined in data-structures/base/iterable-element-base.ts:60

addAt

addAt(index, newElement): boolean
Insert a new element at a given index.
Parameters
- index: number
  Zero-based index from the front.
- newElement: E
  Element to insert.
Returns boolean
True if inserted.

Remarks
Time O(N), Space O(1)
Overrides LinearBase.addAt
- Defined in data-structures/queue/queue.ts:284

at

at(index): undefined | E
Get the element at a given logical index.
Parameters
- index: number
  Zero-based index from the front.
Returns undefined | E
Element or undefined.

Remarks
Time O(1), Space O(1)
Overrides LinearBase.at
- Defined in data-structures/queue/queue.ts:257

clear

clear(): void
Remove all elements and reset offset.

Returns void
void

Remarks
Time O(1), Space O(1)
Overrides LinearBase.clear
- Defined in data-structures/queue/queue.ts:322

clone

clone(): this
Deep clone this queue and its parameters.

Returns this
A new queue with the same content and options.

Remarks
Time O(N), Space O(N)
Overrides LinearBase.clone
- Defined in data-structures/queue/queue.ts:370

compact

compact(): boolean
Compact storage by discarding consumed head elements.

Returns boolean
True when compaction performed.

Remarks
Time O(N), Space O(N)
- Defined in data-structures/queue/queue.ts:333

concat

concat(...items): this
Concatenate multiple containers of the same species.
Parameters
- Rest...items: Queue<E, R>[]
  Other lists to append.
Returns this
New container with combined elements (this type).

Remarks
Time O(sum(length)), Space O(sum(length))
Inherited from LinearBase.concat
- Defined in data-structures/base/linear-base.ts:165

delete

delete(element): boolean
Delete the first occurrence of a specific element.
Parameters
- element: E
  Element to remove (strict equality via Object.is).
Returns boolean
True if an element was removed.

Remarks
Time O(N), Space O(1)
Overrides LinearBase.delete
- Defined in data-structures/queue/queue.ts:240

deleteAt

deleteAt(index): undefined | E
Delete the element at a given index.
Parameters
- index: number
  Zero-based index from the front.
Returns undefined | E
Removed element or undefined.

Remarks
Time O(N), Space O(1)
Overrides LinearBase.deleteAt
- Defined in data-structures/queue/queue.ts:269

every

every(predicate, thisArg?): boolean
Tests whether all elements satisfy the predicate.
Parameters
- predicate: ElementCallback<E, R, boolean>
  Function invoked for each element with signature (value, index, self).
- OptionalthisArg: unknown
  Optional this binding for the predicate.
Returns boolean
true if every element passes; otherwise false.

Remarks
Time O(n) in the worst case; may exit early when the first failure is found. Space O(1).
Inherited from LinearBase.every
- Defined in data-structures/base/iterable-element-base.ts:86

fill

fill(value, start?, end?): this
Fill a range with a value.
Parameters
- value: E
  Value to set.
- start: number = 0
  Inclusive start.
- end: number = ...
  Exclusive end.
Returns this
This list.

Remarks
Time O(n), Space O(1)
Inherited from LinearBase.fill
- Defined in data-structures/base/linear-base.ts:300

filter

filter(predicate, thisArg?): this
Filter elements into a new queue of the same class.
Parameters
- predicate: ElementCallback<E, R, boolean>
  Predicate (element, index, queue) → boolean to keep element.
- OptionalthisArg: unknown
  Value for this inside the predicate.
Returns this
A new queue with kept elements.

Remarks
Time O(N), Space O(N)
Overrides LinearBase.filter
- Defined in data-structures/queue/queue.ts:385

find

find<S>(predicate, thisArg?): undefined | S
Finds the first element that satisfies the predicate and returns it.

Finds the first element of type S (a subtype of E) that satisfies the predicate and returns it.
Type Parameters
- S
Parameters
- predicate: ElementCallback<E, R, S>
  Type-guard predicate: (value, index, self) => value is S.
- OptionalthisArg: unknown
  Optional this binding for the predicate.
Returns undefined | S
The matched element typed as S, or undefined if not found.

Remarks
Time O(n) in the worst case; may exit early on the first match. Space O(1).
Inherited from LinearBase.find
- Defined in data-structures/base/iterable-element-base.ts:162

findIndex

findIndex(predicate, thisArg?): number
Find the first index matching a predicate.
Parameters
- predicate: ElementCallback<E, R, boolean>
  (element, index, self) => boolean.
- OptionalthisArg: any
  Optional this for callback.
Returns number
Index or -1.

Remarks
Time O(n), Space O(1)
Inherited from LinearBase.findIndex
- Defined in data-structures/base/linear-base.ts:151

forEach

forEach(callbackfn, thisArg?): void
Invokes a callback for each element in iteration order.
Parameters
- callbackfn: ElementCallback<E, R, void>
  Function invoked per element with signature (value, index, self).
- OptionalthisArg: unknown
  Optional this binding for the callback.
Returns void
void.

Remarks
Time O(n), Space O(1).
Inherited from LinearBase.forEach
- Defined in data-structures/base/iterable-element-base.ts:132

has

has(element): boolean
Checks whether a strictly-equal element exists in the structure.
Parameters
- element: E
  The element to test with === equality.
Returns boolean
true if an equal element is found; otherwise false.

Remarks
Time O(n) in the worst case. Space O(1).
Inherited from LinearBase.has
- Defined in data-structures/base/iterable-element-base.ts:188

indexOf

indexOf(searchElement, fromIndex?): number
First index of a value from the left.
Parameters
- searchElement: E
  Value to match.
- fromIndex: number = 0
  Start position (supports negative index).
Returns number
Index or -1 if not found.

Remarks
Time O(n), Space O(1)
Inherited from LinearBase.indexOf
- Defined in data-structures/base/linear-base.ts:111

isEmpty

isEmpty(): boolean
Check whether the queue is empty.

Returns boolean
True if length is 0.

Remarks
Time O(1), Space O(1)
Overrides LinearBase.isEmpty
- Defined in data-structures/queue/queue.ts:186

join

join(separator?): string
Join all elements into a string.
Parameters
- separator: string = ','
  Separator string.
Returns string
Concatenated string.

Remarks
Time O(n), Space O(n)
Inherited from LinearBase.join
- Defined in data-structures/base/linear-base.ts:236

lastIndexOf

lastIndexOf(searchElement, fromIndex?): number
Last index of a value from the right.
Parameters
- searchElement: E
  Value to match.
- fromIndex: number = ...
  Start position (supports negative index).
Returns number
Index or -1 if not found.

Remarks
Time O(n), Space O(1)
Inherited from LinearBase.lastIndexOf
- Defined in data-structures/base/linear-base.ts:131

map

map<EM, RM>(callback, options?, thisArg?): Queue<EM, RM>
Map each element to a new element in a possibly different-typed queue.
Type Parameters
- EM
- RM
Parameters
- callback: ElementCallback<E, R, EM>
  Mapping function (element, index, queue) → newElement.
- Optionaloptions: QueueOptions<EM, RM>
  Options for the output queue (e.g., toElementFn, maxLen, autoCompactRatio).
- OptionalthisArg: unknown
  Value for this inside the callback.
Returns Queue<EM, RM>
A new Queue with mapped elements.

Remarks
Time O(N), Space O(N)
Overrides LinearBase.map
- Defined in data-structures/queue/queue.ts:407

mapSame

mapSame(callback, thisArg?): this
Map each element to a new value of the same type.
Parameters
- callback: ElementCallback<E, R, E>
  Mapping function (element, index, queue) → element.
- OptionalthisArg: unknown
  Value for this inside the callback.
Returns this
A new queue with mapped elements (same element type).

Remarks
Time O(N), Space O(N)
Overrides LinearBase.mapSame
- Defined in data-structures/queue/queue.ts:430

print

print(): void
Prints toVisual() to the console. Intended for quick debugging.

Returns void
void.

Remarks
Time O(n) due to materialization, Space O(n) for the intermediate representation.
Inherited from LinearBase.print
- Defined in data-structures/base/iterable-element-base.ts:268

push

push(element): boolean
Enqueue one element at the back.
Parameters
- element: E
  Element to enqueue.
Returns boolean
True on success.

Remarks
Time O(1), Space O(1)
Overrides LinearBase.push
- Defined in data-structures/queue/queue.ts:197

pushMany

pushMany(elements): boolean[]
Enqueue many elements from an iterable.
Parameters
- elements: Iterable<E, any, any> | Iterable<R, any, any>
  Iterable of elements (or raw records if toElementFn is set).
Returns boolean[]
Array of per-element success flags.

Remarks
Time O(N), Space O(1)
Overrides LinearBase.pushMany
- Defined in data-structures/queue/queue.ts:210

reduce

reduce(callbackfn): E
Parameters
- callbackfn: ReduceElementCallback<E, R>
Returns E
Inherited from LinearBase.reduce
- Defined in data-structures/base/iterable-element-base.ts:193
reduce(callbackfn, initialValue): E
Parameters
- callbackfn: ReduceElementCallback<E, R>
- initialValue: E
Returns E
Inherited from LinearBase.reduce
- Defined in data-structures/base/iterable-element-base.ts:194
reduce<U>(callbackfn, initialValue): U
Type Parameters
- U
Parameters
- callbackfn: ReduceElementCallback<E, R, U>
- initialValue: U
Returns U
Inherited from LinearBase.reduce
- Defined in data-structures/base/iterable-element-base.ts:195

reduceRight

reduceRight<U>(callbackfn, initialValue): U
Right-to-left reduction over elements.
Type Parameters
- U
Parameters
- callbackfn: ReduceLinearCallback<E, U>
  (acc, element, index, self) => acc.
- initialValue: U
  Initial accumulator (optional generic overloads supported).
Returns U
Final accumulator.

Remarks
Time O(n), Space O(1)
Inherited from LinearBase.reduceRight
- Defined in data-structures/base/linear-base.ts:264

reverse

reverse(): this
Reverse the queue in-place by compacting then reversing.

Returns this
This queue.

Remarks
Time O(N), Space O(N)
Overrides LinearBase.reverse
- Defined in data-structures/queue/queue.ts:310

setAt

setAt(index, newElement): boolean
Replace the element at a given index.
Parameters
- index: number
  Zero-based index from the front.
- newElement: E
  New element to set.
Returns boolean
True if updated.

Remarks
Time O(1), Space O(1)
Overrides LinearBase.setAt
- Defined in data-structures/queue/queue.ts:298

shift

shift(): undefined | E
Dequeue one element from the front (amortized via offset).

Returns undefined | E
Removed element or undefined.

Remarks
Time O(1) amortized, Space O(1)
- Defined in data-structures/queue/queue.ts:225

slice

slice(start?, end?): this
Create a shallow copy of a subrange.
Parameters
- start: number = 0
  Inclusive start (supports negative index).
- end: number = ...
  Exclusive end (supports negative index).
Returns this
New list with the range (this type).

Remarks
Time O(n), Space O(n)
Inherited from LinearBase.slice
- Defined in data-structures/base/linear-base.ts:281

some

some(predicate, thisArg?): boolean
Tests whether at least one element satisfies the predicate.
Parameters
- predicate: ElementCallback<E, R, boolean>
  Function invoked for each element with signature (value, index, self).
- OptionalthisArg: unknown
  Optional this binding for the predicate.
Returns boolean
true if any element passes; otherwise false.

Remarks
Time O(n) in the worst case; may exit early on first success. Space O(1).
Inherited from LinearBase.some
- Defined in data-structures/base/iterable-element-base.ts:109

sort

sort(compareFn?): this
In-place stable order via array sort semantics.
Parameters
- OptionalcompareFn: ((a: E, b: E) => number)
  Comparator (a, b) => number.
  - - (a, b): number
    - Parameters
      a: E
      b: E
      Returns number
Returns this
This container.

Remarks
Time O(n log n), Space O(n) (materializes to array temporarily)
Inherited from LinearBase.sort
- Defined in data-structures/base/linear-base.ts:193

splice

splice(start, deleteCount?, ...items?): this
Remove and/or insert elements at a position (array-like).
Parameters
- start: number
  Start index (clamped to [0, length]).
- OptionaldeleteCount: number = 0
  Number of elements to remove (default 0).
- Optional Rest...items: E[]
  Elements to insert after start.
Returns this
A new queue containing the removed elements (typed as this).

Remarks
Time O(N + M), Space O(M)
Overrides LinearBase.splice
- Defined in data-structures/queue/queue.ts:348

toArray

toArray(): E[]
Materializes the elements into a new array.

Returns E[]
A shallow array copy of the iteration order.

Remarks
Time O(n), Space O(n).
Inherited from LinearBase.toArray
- Defined in data-structures/base/iterable-element-base.ts:245

toReversedArray

toReversedArray(): E[]
Snapshot elements into a reversed array.

Returns E[]
New reversed array.

Remarks
Time O(n), Space O(n)
Inherited from LinearBase.toReversedArray
- Defined in data-structures/base/linear-base.ts:245

toVisual

toVisual(): E[]
Returns a representation of the structure suitable for quick visualization. Defaults to an array of elements; subclasses may override to provide richer visuals.

Returns E[]
A visual representation (array by default).

Remarks
Time O(n), Space O(n).
Inherited from LinearBase.toVisual
- Defined in data-structures/base/iterable-element-base.ts:257

values

values(): IterableIterator<E, any, any>
Returns an iterator over the values (alias of the default iterator).

Returns IterableIterator<E, any, any>
An IterableIterator<E> over all elements.

Remarks
Creating the iterator is O(1); full iteration is Time O(n), Space O(1).
Inherited from LinearBase.values
- Defined in data-structures/base/iterable-element-base.ts:71

`Static`fromArray

fromArray<E>(elements): Queue<E, any>
Create a queue from an array of elements.
Type Parameters
- E
Parameters
- elements: E[]
  Array of elements to enqueue in order.
Returns Queue<E, any>
A new queue populated from the array.

Remarks
Time O(N), Space O(N)
- Defined in data-structures/queue/queue.ts:176

Class Queue<E, R>

Remarks

Example

Example

Type Parameters

Hierarchy

Index

Constructors

Properties

Accessors

Methods

Constructors

constructor

Type Parameters

Parameters

Returns Queue<E, R>

Remarks

Properties

Protected Optional_toElementFn

Remarks

Accessors

autoCompactRatio

Returns number

Remarks

Parameters

Returns void

Remarks

elements

Returns E[]

Remarks

first

Returns undefined | E

Remarks

last

Returns undefined | E

Remarks

length

Returns number

Remarks

maxLen

Returns number

Remarks

offset

Returns number

Remarks

toElementFn

Returns undefined | ((rawElement: R) => E)

Remarks

Methods

Protected_createInstance

Parameters

Returns this

Remarks

Protected_createLike

Type Parameters

Parameters

Returns Queue<EM, RM>

Remarks

Protected_getIterator

Returns IterableIterator<E, any, any>

Remarks

Protected_getReverseIterator

Returns IterableIterator<E, any, any>

Remarks

Protected_setAutoCompactRatio

Parameters

Returns void

Remarks

[iterator]

Parameters

Returns IterableIterator<E, any, any>

Remarks

addAt

Parameters

Returns boolean

Remarks

at

Parameters

Returns undefined | E

Remarks

`Protected` `Optional`_toElementFn

`Protected`_createInstance

`Protected`_createLike

`Protected`_getIterator

`Protected`_getReverseIterator

`Protected`_setAutoCompactRatio