Linear Data Structures

/**
 * FIFO queue for ordered processing
 */
function Queue<T>(): Queue<T>;

interface Queue<T> {
  readonly size: number;
  
  /** Add item to back of queue */
  enqueue(item: T): number;
  
  /** Remove and return item from front of queue */
  dequeue(): T | undefined;
  
  /** View item at front without removing */
  peek(): T | undefined;
  
  /** Remove all items */
  clear(): void;
  
  values(): IterableIterator<T>;
  [Symbol.iterator](): IterableIterator<T>;
  forEach(callback: (item: T, index: number, queue: this) => void): void;
  
  inspect(): any;
}

/**
 * LIFO stack for recursive operations
 */
function Stack<T>(): Stack<T>;

interface Stack<T> {
  readonly size: number;
  
  /** Add item to top of stack */
  push(item: T): number;
  
  /** Remove and return item from top of stack */
  pop(): T | undefined;
  
  /** View item at top without removing */
  peek(): T | undefined;
  
  /** Remove all items */
  clear(): void;
  
  values(): IterableIterator<T>;
  [Symbol.iterator](): IterableIterator<T>;
  forEach(callback: (item: T, index: number, stack: this) => void): void;
  
  inspect(): any;
}

/**
 * Fixed-capacity stack with typed backing storage
 * @param ArrayClass Constructor for backing array type
 * @param capacity Maximum number of items
 */
function FixedStack<T>(ArrayClass: ArrayConstructor, capacity: number): FixedStack<T>;

interface FixedStack<T> {
  readonly capacity: number;
  readonly size: number;
  
  /** Add item to top (throws if at capacity) */
  push(item: T): number;
  
  /** Remove and return item from top */
  pop(): T | undefined;
  
  /** View item at top without removing */
  peek(): T | undefined;
  
  /** Remove all items */
  clear(): void;
  
  values(): IterableIterator<T>;
  [Symbol.iterator](): IterableIterator<T>;
  
  inspect(): any;
}

/**
 * Doubly-linked list implementation
 */
function LinkedList<T>(): LinkedList<T>;

interface LinkedList<T> {
  readonly size: number;
  
  /** Add item to end of list */
  append(value: T): number;
  
  /** Add item to beginning of list */
  prepend(value: T): number;
  
  /** Remove and return first item */
  shift(): T | undefined;
  
  /** Remove and return last item */
  pop(): T | undefined;
  
  /** Insert item at specific index */
  insert(index: number, value: T): number;
  
  /** Remove item at specific index */
  remove(index: number): T | undefined;
  
  /** Get item at index without removing */
  get(index: number): T | undefined;
  
  /** Set item at index */
  set(index: number, value: T): void;
  
  /** Find index of first occurrence of value */
  indexOf(value: T): number;
  
  /** Find index of last occurrence of value */
  lastIndexOf(value: T): number;
  
  /** Check if value exists in list */
  contains(value: T): boolean;
  
  /** Convert to array */
  toArray(): Array<T>;
  
  /** Remove all items */
  clear(): void;
  
  values(): IterableIterator<T>;
  [Symbol.iterator](): IterableIterator<T>;
  forEach(callback: (item: T, index: number, list: this) => void): void;
  
  inspect(): any;
}

/**
 * Fixed-size circular buffer
 * @param ArrayClass Constructor for backing array type
 * @param capacity Fixed buffer size
 */
function CircularBuffer<T>(ArrayClass: ArrayConstructor, capacity: number): CircularBuffer<T>;

interface CircularBuffer<T> {
  readonly capacity: number;
  readonly size: number;
  
  /** Add item (overwrites oldest if full) */
  push(item: T): number;
  
  /** Remove and return oldest item */
  shift(): T | undefined;
  
  /** Get item at logical index */
  get(index: number): T | undefined;
  
  /** Set item at logical index */
  set(index: number, value: T): void;
  
  /** Remove all items */
  clear(): void;
  
  values(): IterableIterator<T>;
  [Symbol.iterator](): IterableIterator<T>;
  
  inspect(): any;
}

/**
 * Fixed-capacity double-ended queue
 * @param ArrayClass Constructor for backing array type
 * @param capacity Maximum number of items
 */
function FixedDeque<T>(ArrayClass: ArrayConstructor, capacity: number): FixedDeque<T>;

interface FixedDeque<T> {
  readonly capacity: number;
  readonly size: number;
  
  /** Add item to back */
  push(item: T): number;
  
  /** Add item to front */
  unshift(item: T): number;
  
  /** Remove and return item from back */
  pop(): T | undefined;
  
  /** Remove and return item from front */
  shift(): T | undefined;
  
  /** View item at back without removing */
  peekLast(): T | undefined;
  
  /** View item at front without removing */
  peekFirst(): T | undefined;
  
  /** Remove all items */
  clear(): void;
  
  values(): IterableIterator<T>;
  [Symbol.iterator](): IterableIterator<T>;
  
  inspect(): any;
}

import {Queue} from "mnemonist";

// Task processing queue
const taskQueue = new Queue<Task>();

// Add tasks
taskQueue.enqueue({id: 1, name: "Process order"});
taskQueue.enqueue({id: 2, name: "Send email"});
taskQueue.enqueue({id: 3, name: "Update database"});

console.log(taskQueue.size); // 3

// Process tasks in order
while (taskQueue.size > 0) {
  const task = taskQueue.dequeue();
  console.log(`Processing: ${task?.name}`);
}

// Peek without removing
taskQueue.enqueue({id: 4, name: "Cleanup"});
console.log(taskQueue.peek()?.name); // "Cleanup"
console.log(taskQueue.size); // Still 1

import {Stack} from "mnemonist";

// Expression evaluation stack
const operatorStack = new Stack<string>();

// Push operators
operatorStack.push("(");
operatorStack.push("+");
operatorStack.push("*");

console.log(operatorStack.peek()); // "*"
console.log(operatorStack.pop());  // "*"
console.log(operatorStack.size);   // 2

// Iterate from top to bottom
for (const op of operatorStack) {
  console.log(op); // "+", "("
}

import {LinkedList} from "mnemonist";

const list = new LinkedList<number>();

// Add items
list.append(1);
list.append(2);
list.prepend(0); // [0, 1, 2]

// Insert at specific position
list.insert(1, 0.5); // [0, 0.5, 1, 2]

// Access items
console.log(list.get(0)); // 0
console.log(list.indexOf(1)); // 2

// Remove items
list.remove(1); // Remove at index 1
list.pop();     // Remove last
list.shift();   // Remove first

// Convert to array
const array = list.toArray();

import {CircularBuffer} from "mnemonist";

// Sliding window buffer
const window = new CircularBuffer(Array, 5); // Capacity of 5

// Fill buffer
for (let i = 1; i <= 7; i++) {
  window.push(i);
}

console.log(window.size); // 5 (capacity reached)

// Buffer contains [3, 4, 5, 6, 7] (oldest items overwritten)
for (const value of window) {
  console.log(value); // 3, 4, 5, 6, 7
}

// Access by index
console.log(window.get(0)); // 3 (oldest)
console.log(window.get(4)); // 7 (newest)

import {FixedDeque} from "mnemonist";

// Job scheduler with priority
const scheduler = new FixedDeque(Array, 100);

// Add high priority job to front
scheduler.unshift({priority: "high", task: "urgent"});

// Add normal priority job to back
scheduler.push({priority: "normal", task: "routine"});

// Process high priority first
const urgent = scheduler.shift(); // Gets high priority job
const routine = scheduler.pop();  // Gets normal priority job

// Peek without removing
scheduler.push({priority: "low", task: "cleanup"});
console.log(scheduler.peekLast()); // Latest added job
console.log(scheduler.peekFirst()); // Next job to process