0
# Linear Data Structures
1

2
Classic linear data structures including queues, stacks, linked lists, and circular buffers.
3

4
## Capabilities
5

6
### Queue
7

8
FIFO (First In, First Out) queue implementation.
9

10
```typescript { .api }
11
/**
12
 * FIFO queue for ordered processing
13
 */
14
function Queue<T>(): Queue<T>;
15

16
interface Queue<T> {
17
  readonly size: number;
18
  
19
  /** Add item to back of queue */
20
  enqueue(item: T): number;
21
  
22
  /** Remove and return item from front of queue */
23
  dequeue(): T | undefined;
24
  
25
  /** View item at front without removing */
26
  peek(): T | undefined;
27
  
28
  /** Remove all items */
29
  clear(): void;
30
  
31
  values(): IterableIterator<T>;
32
  [Symbol.iterator](): IterableIterator<T>;
33
  forEach(callback: (item: T, index: number, queue: this) => void): void;
34
  
35
  inspect(): any;
36
}
37
```
38

39
### Stack
40

41
LIFO (Last In, First Out) stack implementation.
42

43
```typescript { .api }
44
/**
45
 * LIFO stack for recursive operations
46
 */
47
function Stack<T>(): Stack<T>;
48

49
interface Stack<T> {
50
  readonly size: number;
51
  
52
  /** Add item to top of stack */
53
  push(item: T): number;
54
  
55
  /** Remove and return item from top of stack */
56
  pop(): T | undefined;
57
  
58
  /** View item at top without removing */
59
  peek(): T | undefined;
60
  
61
  /** Remove all items */
62
  clear(): void;
63
  
64
  values(): IterableIterator<T>;
65
  [Symbol.iterator](): IterableIterator<T>;
66
  forEach(callback: (item: T, index: number, stack: this) => void): void;
67
  
68
  inspect(): any;
69
}
70
```
71

72
### FixedStack
73

74
Fixed-capacity stack with typed array backing storage.
75

76
```typescript { .api }
77
/**
78
 * Fixed-capacity stack with typed backing storage
79
 * @param ArrayClass Constructor for backing array type
80
 * @param capacity Maximum number of items
81
 */
82
function FixedStack<T>(ArrayClass: ArrayConstructor, capacity: number): FixedStack<T>;
83

84
interface FixedStack<T> {
85
  readonly capacity: number;
86
  readonly size: number;
87
  
88
  /** Add item to top (throws if at capacity) */
89
  push(item: T): number;
90
  
91
  /** Remove and return item from top */
92
  pop(): T | undefined;
93
  
94
  /** View item at top without removing */
95
  peek(): T | undefined;
96
  
97
  /** Remove all items */
98
  clear(): void;
99
  
100
  values(): IterableIterator<T>;
101
  [Symbol.iterator](): IterableIterator<T>;
102
  
103
  inspect(): any;
104
}
105
```
106

107
### LinkedList
108

109
Doubly-linked list with efficient insertion and deletion.
110

111
```typescript { .api }
112
/**
113
 * Doubly-linked list implementation
114
 */
115
function LinkedList<T>(): LinkedList<T>;
116

117
interface LinkedList<T> {
118
  readonly size: number;
119
  
120
  /** Add item to end of list */
121
  append(value: T): number;
122
  
123
  /** Add item to beginning of list */
124
  prepend(value: T): number;
125
  
126
  /** Remove and return first item */
127
  shift(): T | undefined;
128
  
129
  /** Remove and return last item */
130
  pop(): T | undefined;
131
  
132
  /** Insert item at specific index */
133
  insert(index: number, value: T): number;
134
  
135
  /** Remove item at specific index */
136
  remove(index: number): T | undefined;
137
  
138
  /** Get item at index without removing */
139
  get(index: number): T | undefined;
140
  
141
  /** Set item at index */
142
  set(index: number, value: T): void;
143
  
144
  /** Find index of first occurrence of value */
145
  indexOf(value: T): number;
146
  
147
  /** Find index of last occurrence of value */
148
  lastIndexOf(value: T): number;
149
  
150
  /** Check if value exists in list */
151
  contains(value: T): boolean;
152
  
153
  /** Convert to array */
154
  toArray(): Array<T>;
155
  
156
  /** Remove all items */
157
  clear(): void;
158
  
159
  values(): IterableIterator<T>;
160
  [Symbol.iterator](): IterableIterator<T>;
161
  forEach(callback: (item: T, index: number, list: this) => void): void;
162
  
163
  inspect(): any;
164
}
165
```
166

167
### CircularBuffer
168

169
Fixed-size circular buffer with efficient wrap-around operations.
170

171
```typescript { .api }
172
/**
173
 * Fixed-size circular buffer
174
 * @param ArrayClass Constructor for backing array type
175
 * @param capacity Fixed buffer size
176
 */
177
function CircularBuffer<T>(ArrayClass: ArrayConstructor, capacity: number): CircularBuffer<T>;
178

179
interface CircularBuffer<T> {
180
  readonly capacity: number;
181
  readonly size: number;
182
  
183
  /** Add item (overwrites oldest if full) */
184
  push(item: T): number;
185
  
186
  /** Remove and return oldest item */
187
  shift(): T | undefined;
188
  
189
  /** Get item at logical index */
190
  get(index: number): T | undefined;
191
  
192
  /** Set item at logical index */
193
  set(index: number, value: T): void;
194
  
195
  /** Remove all items */
196
  clear(): void;
197
  
198
  values(): IterableIterator<T>;
199
  [Symbol.iterator](): IterableIterator<T>;
200
  
201
  inspect(): any;
202
}
203
```
204

205
### FixedDeque
206

207
Fixed-capacity double-ended queue (deque) with efficient operations at both ends.
208

209
```typescript { .api }
210
/**
211
 * Fixed-capacity double-ended queue
212
 * @param ArrayClass Constructor for backing array type
213
 * @param capacity Maximum number of items
214
 */
215
function FixedDeque<T>(ArrayClass: ArrayConstructor, capacity: number): FixedDeque<T>;
216

217
interface FixedDeque<T> {
218
  readonly capacity: number;
219
  readonly size: number;
220
  
221
  /** Add item to back */
222
  push(item: T): number;
223
  
224
  /** Add item to front */
225
  unshift(item: T): number;
226
  
227
  /** Remove and return item from back */
228
  pop(): T | undefined;
229
  
230
  /** Remove and return item from front */
231
  shift(): T | undefined;
232
  
233
  /** View item at back without removing */
234
  peekLast(): T | undefined;
235
  
236
  /** View item at front without removing */
237
  peekFirst(): T | undefined;
238
  
239
  /** Remove all items */
240
  clear(): void;
241
  
242
  values(): IterableIterator<T>;
243
  [Symbol.iterator](): IterableIterator<T>;
244
  
245
  inspect(): any;
246
}
247
```
248

249
## Usage Examples
250

251
### Queue Example
252

253
```typescript
254
import {Queue} from "mnemonist";
255

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

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

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

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

272
// Peek without removing
273
taskQueue.enqueue({id: 4, name: "Cleanup"});
274
console.log(taskQueue.peek()?.name); // "Cleanup"
275
console.log(taskQueue.size); // Still 1
276
```
277

278
### Stack Example
279

280
```typescript
281
import {Stack} from "mnemonist";
282

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

286
// Push operators
287
operatorStack.push("(");
288
operatorStack.push("+");
289
operatorStack.push("*");
290

291
console.log(operatorStack.peek()); // "*"
292
console.log(operatorStack.pop());  // "*"
293
console.log(operatorStack.size);   // 2
294

295
// Iterate from top to bottom
296
for (const op of operatorStack) {
297
  console.log(op); // "+", "("
298
}
299
```
300

301
### LinkedList Example
302

303
```typescript
304
import {LinkedList} from "mnemonist";
305

306
const list = new LinkedList<number>();
307

308
// Add items
309
list.append(1);
310
list.append(2);
311
list.prepend(0); // [0, 1, 2]
312

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

316
// Access items
317
console.log(list.get(0)); // 0
318
console.log(list.indexOf(1)); // 2
319

320
// Remove items
321
list.remove(1); // Remove at index 1
322
list.pop();     // Remove last
323
list.shift();   // Remove first
324

325
// Convert to array
326
const array = list.toArray();
327
```
328

329
### CircularBuffer Example
330

331
```typescript
332
import {CircularBuffer} from "mnemonist";
333

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

337
// Fill buffer
338
for (let i = 1; i <= 7; i++) {
339
  window.push(i);
340
}
341

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

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

349
// Access by index
350
console.log(window.get(0)); // 3 (oldest)
351
console.log(window.get(4)); // 7 (newest)
352
```
353

354
### FixedDeque Example
355

356
```typescript
357
import {FixedDeque} from "mnemonist";
358

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

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

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

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

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

378
## Performance Characteristics
379

380
| Operation | Queue | Stack | LinkedList | CircularBuffer | FixedDeque |
381
|-----------|-------|-------|------------|----------------|------------|
382
| Push/Enqueue | O(1) | O(1) | O(1) | O(1) | O(1) |
383
| Pop/Dequeue | O(1) | O(1) | O(1) | O(1) | O(1) |
384
| Peek | O(1) | O(1) | O(1) | O(1) | O(1) |
385
| Insert | N/A | N/A | O(n) | N/A | N/A |
386
| Remove | N/A | N/A | O(n) | N/A | N/A |
387
| Random Access | N/A | N/A | O(n) | O(1) | N/A |
388
| Space | O(n) | O(n) | O(n) | O(capacity) | O(capacity) |
389
390
## Memory Characteristics
391

392
- **Queue/Stack**: Dynamic sizing, no memory limit
393
- **FixedStack**: Uses typed arrays, fixed capacity
394
- **LinkedList**: Node-based, efficient insertion/deletion anywhere
395
- **CircularBuffer**: Fixed memory footprint, overwrites old data
396
- **FixedDeque**: Fixed capacity with efficient operations at both ends
397

398
## Choosing the Right Linear Structure
399

400
- **Queue**: For FIFO processing, task queues, breadth-first algorithms
401
- **Stack**: For LIFO processing, recursion simulation, expression parsing
402
- **FixedStack**: When memory usage must be bounded and you need typed storage
403
- **LinkedList**: When you need frequent insertion/deletion at arbitrary positions
404
- **CircularBuffer**: For sliding windows, streaming data with fixed memory
405
- **FixedDeque**: When you need efficient operations at both ends with bounded memory