You use stacks and queues every single day, you just don't think about it. Every time you hit the **back button** in your browser, that's a stack. Every time you send a document to the printer and it waits in line behind two other jobs, that's a queue. Every time you press **Ctrl+Z** to undo a mistake, that's a stack. Every time a web server processes requests in the order they arrived, that's a queue. These two data structures are among the simplest you'll ever learn, but they are absolutely **foundational**. They show up everywhere: in algorithms like BFS and DFS, in system design for message brokers and task schedulers, in compilers for parsing expressions, and in virtually every coding interview you'll ever take. The beautiful thing about stacks and queues is that they're really just **restricted lists**. An array lets you add and remove from anywhere. A stack says, “you can only touch the top.” A queue says, “you can only add to the back and remove from the front.” These constraints aren't limitations, they're **superpowers**. By restricting how data flows, you model real-world problems more clearly and write code that's easier to reason about. > If arrays are the Swiss army knife of data structures, stacks and queues are the scalpel and tweezers: specialized, precise, and perfect for the right job. By the end of this guide, you'll: - Understand the **LIFO** and **FIFO** principles at a deep level - Build your own stacks and queues from scratch in TypeScript (array-based and linked-list-based) - Know the **Big O** complexity of every operation - Recognize real-world applications of each - Understand deques, priority queues, and circular queues - Be ready to tackle stack and queue problems in interviews Let's get started. --- ## What Is a Stack? A **stack** is a linear data structure that follows the **LIFO** principle: **Last In, First Out**. The last element you add to the stack is the first one you remove. Think about a **stack of plates** at a buffet. You place plates on top of the pile, one by one. When someone needs a plate, they take it from the **top**, not the bottom. The most recently placed plate is always the first one removed. Or think about a **Pringles can**. You can only reach the chip on top. To get to the one at the bottom, you have to eat through every chip above it first. That's LIFO in action. ### How It Works Visually Imagine a stack growing upward. New items go on top. Removal happens from the top: ``` ┌─────────┐ │ 30 │ ← top (most recently added) ├─────────┤ │ 20 │ ├─────────┤ │ 10 │ ← bottom (first item added) └─────────┘ push(40): pop(): ┌─────────┐ ┌─────────┐ │ 40 │ ← new │ 20 │ ← new top ├─────────┤ ├─────────┤ │ 30 │ │ 10 │ ├─────────┤ └─────────┘ │ 20 │ (30 was removed) ├─────────┤ │ 10 │ └─────────┘ ``` ### Core Operations Every stack supports these fundamental operations: | Operation | Description | Big O | |-------------|------------------------------------------|-------| | `push(item)` | Add an item to the top of the stack | O(1) | | `pop()` | Remove and return the top item | O(1) | | `peek()` | View the top item without removing it | O(1) | | `isEmpty()` | Check if the stack is empty | O(1) | | `size()` | Return the number of items in the stack | O(1) | Notice something important: **every single operation is O(1)**. That's constant time. No matter how many items are in the stack, these operations take the same amount of time. That's part of what makes stacks so efficient. > **Key insight**: A stack only ever cares about one element, the one on top. You never need to search through a stack or access an item in the middle. If you find yourself needing random access, you probably want a different data structure. --- ## Building a Stack in TypeScript (Array-Based) The simplest way to implement a stack is with an array. JavaScript and TypeScript arrays already have `push()` and `pop()` methods that operate on the end of the array, which is exactly what a stack needs. Let's build a fully typed, generic stack class: ```typescript class Stack { private items: T[]; constructor() { this.items = []; } push(item: T): void { this.items.push(item); } pop(): T | undefined { if (this.isEmpty()) { return undefined; } return this.items.pop(); } peek(): T | undefined { if (this.isEmpty()) { return undefined; } return this.items[this.items.length - 1]; } isEmpty(): boolean { return this.items.length === 0; } size(): number { return this.items.length; } clear(): void { this.items = []; } toArray(): T[] { return [...this.items]; } toString(): string { return this.items.toString(); } } ``` Let's break down what's happening: - **Generics (``)**: The class is generic, meaning it works with any type: numbers, strings, objects, whatever you need. TypeScript will enforce type safety for you. - **`push(item)`**: Delegates to the native array `push()`, which appends to the end in O(1) amortized time. - **`pop()`**: Delegates to the native array `pop()`, which removes from the end in O(1). Returns `undefined` if the stack is empty rather than throwing an error. - **`peek()`**: Reads the last element without modifying the array. - **`isEmpty()` and `size()`**: Simple state checks. - **`clear()`**: Resets the stack by replacing the internal array. - **`toArray()`**: Returns a shallow copy so the internal state isn't accidentally mutated. ### Usage Examples ```typescript const stack = new Stack(); stack.push(10); stack.push(20); stack.push(30); console.log(stack.peek()); // 30 console.log(stack.size()); // 3 console.log(stack.pop()); // 30 console.log(stack.pop()); // 20 console.log(stack.peek()); // 10 console.log(stack.size()); // 1 console.log(stack.isEmpty()); // false stack.pop(); console.log(stack.isEmpty()); // true console.log(stack.pop()); // undefined (stack is empty) ``` Works with other types just as easily: ```typescript const nameStack = new Stack(); nameStack.push("Alice"); nameStack.push("Bob"); nameStack.push("Charlie"); console.log(nameStack.pop()); // "Charlie" console.log(nameStack.peek()); // "Bob" ``` ### Big O Analysis (Array-Based Stack) | Operation | Time Complexity | Space Complexity | |------------|--------------------|------------------| | `push` | O(1) amortized* | O(1) | | `pop` | O(1) | O(1) | | `peek` | O(1) | O(1) | | `isEmpty` | O(1) | O(1) | | `size` | O(1) | O(1) | *\*Amortized O(1) because JavaScript arrays occasionally need to resize their internal storage when capacity is exceeded. On average, though, it's constant time.* > **Tip**: For the vast majority of use cases, an array-based stack is perfectly fine. The array resizing overhead is negligible in practice. Only reach for a linked-list-based stack if you have specific requirements around guaranteed O(1) push in all cases or need to avoid array reallocation. --- ## Linked-List-Based Stack Sometimes you want a stack where **every single push and pop is guaranteed O(1)**, not just amortized. Or maybe you want to avoid the memory overhead of array resizing. In these cases, a **linked-list-based stack** is the way to go. The idea is simple: each item in the stack is a **node** that points to the node below it. The `top` pointer always references the most recently added node. ### How It Looks Visually ``` top │ ▼ ┌─────┬───┐ ┌─────┬───┐ ┌─────┬───┐ │ 30 │ ──┼───▶│ 20 │ ──┼───▶│ 10 │ / │ └─────┴───┘ └─────┴───┘ └─────┴───┘ (newest) (oldest) ``` Each node stores a `value` and a `next` pointer. The top of the stack is the head of the linked list. ### Implementation ```typescript class StackNode { value: T; next: StackNode | null; constructor(value: T) { this.value = value; this.next = null; } } class LinkedStack { private top: StackNode | null; private count: number; constructor() { this.top = null; this.count = 0; } push(item: T): void { const newNode = new StackNode(item); newNode.next = this.top; this.top = newNode; this.count++; } pop(): T | undefined { if (!this.top) { return undefined; } const value = this.top.value; this.top = this.top.next; this.count--; return value; } peek(): T | undefined { return this.top?.value; } isEmpty(): boolean { return this.top === null; } size(): number { return this.count; } clear(): void { this.top = null; this.count = 0; } } ``` Let's trace through what happens: 1. **`push(10)`**: Create a node with value 10, point its `next` to `null` (current top), make it the new top. Stack: `[10]` 2. **`push(20)`**: Create a node with value 20, point its `next` to the node with 10, make it the new top. Stack: `[20 → 10]` 3. **`push(30)`**: Create a node with value 30, point its `next` to the node with 20, make it the new top. Stack: `[30 → 20 → 10]` 4. **`pop()`**: Save the value 30, move `top` to point to the node with 20, return 30. Stack: `[20 → 10]` ### Usage ```typescript const stack = new LinkedStack(); stack.push(100); stack.push(200); stack.push(300); console.log(stack.peek()); // 300 console.log(stack.pop()); // 300 console.log(stack.size()); // 2 console.log(stack.pop()); // 200 console.log(stack.pop()); // 100 console.log(stack.isEmpty()); // true ``` ### Big O Analysis (Linked-List Stack) | Operation | Time Complexity | Space Complexity | |------------|-----------------|------------------| | `push` | O(1) always | O(1) | | `pop` | O(1) always | O(1) | | `peek` | O(1) | O(1) | | `isEmpty` | O(1) | O(1) | | `size` | O(1) | O(1) | > **Trade-off**: A linked-list stack gives you strict O(1) for push and pop with no resizing. However, each node carries extra memory overhead for the `next` pointer, and linked lists have worse **cache locality** than arrays (nodes aren't stored contiguously in memory). For most web development use cases, the array-based version is the better default. --- ## Real-World Stack Applications Stacks aren't just an academic concept. They power some of the most common features you use every day. Let's look at the big ones. ### 1. Browser Back/Forward Navigation Your browser maintains two stacks: a **back stack** and a **forward stack**. - Every time you visit a new page, the current page gets pushed onto the **back stack**. - When you click **Back**, the current page is pushed onto the **forward stack**, and the top of the back stack becomes the current page. - When you click **Forward**, the reverse happens. - If you visit a **new** page (not via forward), the forward stack is cleared. ```typescript class BrowserHistory { private backStack: Stack; private forwardStack: Stack; private currentPage: string; constructor(homepage: string) { this.backStack = new Stack(); this.forwardStack = new Stack(); this.currentPage = homepage; } visit(url: string): void { this.backStack.push(this.currentPage); this.currentPage = url; this.forwardStack.clear(); } back(): string { if (this.backStack.isEmpty()) { return this.currentPage; } this.forwardStack.push(this.currentPage); this.currentPage = this.backStack.pop()!; return this.currentPage; } forward(): string { if (this.forwardStack.isEmpty()) { return this.currentPage; } this.backStack.push(this.currentPage); this.currentPage = this.forwardStack.pop()!; return this.currentPage; } getCurrent(): string { return this.currentPage; } } ``` ```typescript const browser = new BrowserHistory("google.com"); browser.visit("github.com"); browser.visit("stackoverflow.com"); console.log(browser.getCurrent()); // "stackoverflow.com" browser.back(); console.log(browser.getCurrent()); // "github.com" browser.back(); console.log(browser.getCurrent()); // "google.com" browser.forward(); console.log(browser.getCurrent()); // "github.com" browser.visit("twitter.com"); console.log(browser.getCurrent()); // "twitter.com" browser.forward(); console.log(browser.getCurrent()); // "twitter.com" (forward stack cleared) ``` ### 2. Undo/Redo in Text Editors Every text editor, from VS Code to Google Docs, uses stacks for undo and redo. The pattern is nearly identical to browser history: - Every action gets pushed onto the **undo stack**. - When you undo, the action moves to the **redo stack**. - A new action clears the redo stack. ```typescript interface EditorAction { type: "insert" | "delete"; text: string; position: number; } class TextEditorHistory { private undoStack: Stack; private redoStack: Stack; constructor() { this.undoStack = new Stack(); this.redoStack = new Stack(); } performAction(action: EditorAction): void { this.undoStack.push(action); this.redoStack.clear(); } undo(): EditorAction | undefined { const action = this.undoStack.pop(); if (action) { this.redoStack.push(action); } return action; } redo(): EditorAction | undefined { const action = this.redoStack.pop(); if (action) { this.undoStack.push(action); } return action; } } ``` ### 3. The Function Call Stack When your program calls a function, the runtime pushes a **stack frame** onto the **call stack**. That frame holds local variables, the return address, and other context. When the function returns, its frame is popped off the stack. This is why **recursion** works: each recursive call adds a new frame to the call stack. And it's why infinite recursion causes a **stack overflow**, the stack runs out of space. ```typescript function factorial(n: number): number { if (n <= 1) return 1; return n * factorial(n - 1); } // Call stack during factorial(4): // // factorial(1) → returns 1 ← top // factorial(2) → returns 2 * 1 // factorial(3) → returns 3 * 2 // factorial(4) → returns 4 * 6 ← bottom // // Each call is "stacked" on top of the previous one. // They resolve in LIFO order: 1 → 2 → 6 → 24 ``` ### 4. Expression Evaluation and Parsing Compilers and interpreters use stacks to evaluate mathematical expressions and parse syntax. The classic algorithm is the **Shunting Yard algorithm** (by Dijkstra), which converts infix notation (`3 + 4 * 2`) to postfix notation (`3 4 2 * +`) using a stack. Here's a simple postfix evaluator: ```typescript function evaluatePostfix(expression: string): number { const stack = new Stack(); const tokens = expression.split(" "); for (const token of tokens) { if (!isNaN(Number(token))) { stack.push(Number(token)); } else { const b = stack.pop()!; const a = stack.pop()!; switch (token) { case "+": stack.push(a + b); break; case "-": stack.push(a - b); break; case "*": stack.push(a * b); break; case "/": stack.push(Math.trunc(a / b)); break; } } } return stack.pop()!; } console.log(evaluatePostfix("3 4 2 * +")); // 11 (3 + (4 * 2)) console.log(evaluatePostfix("5 1 2 + 4 * + 3 -")); // 14 ``` ### 5. Parentheses / Bracket Matching One of the most classic stack problems. Given a string of brackets, determine if every open bracket has a corresponding close bracket in the right order: ```typescript function isValidBrackets(s: string): boolean { const stack = new Stack(); const pairs: Record = { ")": "(", "]": "[", "}": "{", }; for (const char of s) { if (char === "(" || char === "[" || char === "{") { stack.push(char); } else if (char in pairs) { if (stack.isEmpty() || stack.pop() !== pairs[char]) { return false; } } } return stack.isEmpty(); } console.log(isValidBrackets("({[]})")); // true console.log(isValidBrackets("({[})")); // false console.log(isValidBrackets("((")); // false console.log(isValidBrackets("")); // true ``` > **Interview tip**: Bracket matching is one of the most common stack interview questions (LeetCode #20). If you can implement it from memory, you're in great shape. --- ## What Is a Queue? A **queue** is a linear data structure that follows the **FIFO** principle: **First In, First Out**. The first element you add is the first one you remove. Think about a **line at a coffee shop**. The person who arrives first gets served first. New customers join at the **back** of the line, and the barista serves from the **front**. Nobody cuts in line (in a well-behaved queue, anyway). Or think about a **drive-through**. Cars enter from one end and exit from the other. The car that entered first leaves first. You can't skip ahead, and you can't go backward. ### How It Works Visually ``` dequeue ← ┌────┬────┬────┬────┐ ← enqueue (front) │ 10 │ 20 │ 30 │ 40 │ (back) └────┴────┴────┴────┘ enqueue(50): ┌────┬────┬────┬────┬────┐ │ 10 │ 20 │ 30 │ 40 │ 50 │ └────┴────┴────┴────┴────┘ dequeue() → returns 10: ┌────┬────┬────┬────┐ │ 20 │ 30 │ 40 │ 50 │ └────┴────┴────┴────┘ ``` Items enter from the right (back) and leave from the left (front). ### Core Operations | Operation | Description | Big O | |------------------|---------------------------------------------|---------| | `enqueue(item)` | Add an item to the back of the queue | O(1) | | `dequeue()` | Remove and return the front item | O(1)* | | `front()` / `peek()` | View the front item without removing it | O(1) | | `isEmpty()` | Check if the queue is empty | O(1) | | `size()` | Return the number of items in the queue | O(1) | *\*O(1) with the right implementation. We'll discuss this in detail shortly.* > **Key insight**: A queue is the natural data structure for anything that requires **fairness** or **ordering**. If things should be processed in the order they arrive, you want a queue. --- ## Building a Queue in TypeScript ### The Naive Array Approach (and Why It's Problematic) Your first instinct might be to use an array, with `push()` to enqueue and `shift()` to dequeue: ```typescript class NaiveQueue { private items: T[]; constructor() { this.items = []; } enqueue(item: T): void { this.items.push(item); // O(1) amortized } dequeue(): T | undefined { return this.items.shift(); // ⚠️ O(n)! } front(): T | undefined { return this.items[0]; } isEmpty(): boolean { return this.items.length === 0; } size(): number { return this.items.length; } } ``` This works, but there's a serious problem: **`Array.shift()` is O(n)**. When you remove the first element, every remaining element has to shift one position to the left. With 10 items, that's barely noticeable. With 10 million items, that's a performance disaster. ``` Before shift(): [A, B, C, D, E] indices: 0, 1, 2, 3, 4 After shift(): [B, C, D, E] indices: 0, 1, 2, 3 ↑ ↑ ↑ ↑ All elements shifted left by 1 → O(n) ``` > **Warning**: Using `Array.shift()` for a queue is one of the most common performance pitfalls in JavaScript. For small queues, it's fine. For anything at scale, avoid it. ### The Object-Based Queue (O(1) Everything) A much better approach is to use an **object (hash map)** with two pointers: one tracking the front index and one tracking the back index. This gives us O(1) enqueue and O(1) dequeue without any shifting: ```typescript class Queue { private items: Record; private headIndex: number; private tailIndex: number; constructor() { this.items = {}; this.headIndex = 0; this.tailIndex = 0; } enqueue(item: T): void { this.items[this.tailIndex] = item; this.tailIndex++; } dequeue(): T | undefined { if (this.isEmpty()) { return undefined; } const item = this.items[this.headIndex]; delete this.items[this.headIndex]; this.headIndex++; return item; } front(): T | undefined { if (this.isEmpty()) { return undefined; } return this.items[this.headIndex]; } rear(): T | undefined { if (this.isEmpty()) { return undefined; } return this.items[this.tailIndex - 1]; } isEmpty(): boolean { return this.tailIndex - this.headIndex === 0; } size(): number { return this.tailIndex - this.headIndex; } clear(): void { this.items = {}; this.headIndex = 0; this.tailIndex = 0; } toArray(): T[] { const result: T[] = []; for (let i = this.headIndex; i < this.tailIndex; i++) { result.push(this.items[i]); } return result; } toString(): string { return this.toArray().toString(); } } ``` Let's trace through what happens: 1. **`enqueue("A")`**: Store `"A"` at index 0, tailIndex becomes 1. Items: `{0: "A"}` 2. **`enqueue("B")`**: Store `"B"` at index 1, tailIndex becomes 2. Items: `{0: "A", 1: "B"}` 3. **`enqueue("C")`**: Store `"C"` at index 2, tailIndex becomes 3. Items: `{0: "A", 1: "B", 2: "C"}` 4. **`dequeue()`**: Return `"A"` from index 0, delete it, headIndex becomes 1. Items: `{1: "B", 2: "C"}` 5. **`dequeue()`**: Return `"B"` from index 1, delete it, headIndex becomes 2. Items: `{2: "C"}` No shifting. No reindexing. Just pointer arithmetic. Every operation is truly O(1). ### Usage Examples ```typescript const queue = new Queue(); queue.enqueue("first"); queue.enqueue("second"); queue.enqueue("third"); console.log(queue.front()); // "first" console.log(queue.rear()); // "third" console.log(queue.size()); // 3 console.log(queue.dequeue()); // "first" console.log(queue.dequeue()); // "second" console.log(queue.front()); // "third" console.log(queue.size()); // 1 console.log(queue.isEmpty()); // false queue.dequeue(); console.log(queue.isEmpty()); // true console.log(queue.dequeue()); // undefined ``` ### Big O Analysis (Object-Based Queue) | Operation | Time Complexity | Space Complexity | |------------|-----------------|------------------| | `enqueue` | O(1) | O(1) | | `dequeue` | O(1) | O(1) | | `front` | O(1) | O(1) | | `rear` | O(1) | O(1) | | `isEmpty` | O(1) | O(1) | | `size` | O(1) | O(1) | > **Tip**: The object-based queue is the recommended general-purpose implementation for TypeScript/JavaScript. It's simple, fast, and avoids the `shift()` trap. --- ## Linked-List-Based Queue For a true O(1) implementation with proper memory management and no growing index counters, a **linked list** is the classic choice. By maintaining both a **head** (front) and **tail** (back) pointer, we get constant-time enqueue and dequeue. ### How It Looks Visually ``` head tail │ │ ▼ ▼ ┌─────┬───┐ ┌─────┬───┐ ┌─────┬───┐ │ 10 │ ──┼───▶│ 20 │ ──┼───▶│ 30 │ / │ └─────┴───┘ └─────┴───┘ └─────┴───┘ (front) (back) dequeue from head ← → enqueue at tail ``` New items are added at the tail. Items are removed from the head. Both operations are O(1) because we have direct pointers to both ends. ### Implementation ```typescript class QueueNode { value: T; next: QueueNode | null; constructor(value: T) { this.value = value; this.next = null; } } class LinkedQueue { private head: QueueNode | null; private tail: QueueNode | null; private count: number; constructor() { this.head = null; this.tail = null; this.count = 0; } enqueue(item: T): void { const newNode = new QueueNode(item); if (this.tail) { this.tail.next = newNode; } this.tail = newNode; if (!this.head) { this.head = newNode; } this.count++; } dequeue(): T | undefined { if (!this.head) { return undefined; } const value = this.head.value; this.head = this.head.next; if (!this.head) { this.tail = null; } this.count--; return value; } front(): T | undefined { return this.head?.value; } rear(): T | undefined { return this.tail?.value; } isEmpty(): boolean { return this.head === null; } size(): number { return this.count; } clear(): void { this.head = null; this.tail = null; this.count = 0; } } ``` Let's trace through the operations: 1. **`enqueue(10)`**: Create node(10). Both `head` and `tail` point to it. `[10]` 2. **`enqueue(20)`**: Create node(20). `tail.next` = node(20), move `tail` to node(20). `[10 → 20]` 3. **`enqueue(30)`**: Create node(30). `tail.next` = node(30), move `tail` to node(30). `[10 → 20 → 30]` 4. **`dequeue()`**: Save 10, move `head` to node(20), return 10. `[20 → 30]` 5. **`dequeue()`**: Save 20, move `head` to node(30), return 20. `[30]` 6. **`dequeue()`**: Save 30, move `head` to `null`, set `tail` to `null`, return 30. `[]` ### Usage ```typescript const queue = new LinkedQueue(); queue.enqueue(1); queue.enqueue(2); queue.enqueue(3); console.log(queue.front()); // 1 console.log(queue.rear()); // 3 console.log(queue.dequeue()); // 1 console.log(queue.dequeue()); // 2 console.log(queue.size()); // 1 console.log(queue.dequeue()); // 3 console.log(queue.isEmpty()); // true ``` ### Big O Analysis (Linked-List Queue) | Operation | Time Complexity | Space Complexity | |------------|-----------------|------------------| | `enqueue` | O(1) | O(1) | | `dequeue` | O(1) | O(1) | | `front` | O(1) | O(1) | | `rear` | O(1) | O(1) | | `isEmpty` | O(1) | O(1) | | `size` | O(1) | O(1) | > **When to choose linked-list over object-based**: If memory cleanup matters (the object-based approach leaves incrementing indices that never reset), or if you're in a memory-constrained environment and want nodes to be garbage collected immediately on dequeue, a linked-list queue is cleaner. --- ## Real-World Queue Applications Queues are everywhere in computing. Let's walk through the most important ones. ### 1. Print Job Scheduling When multiple users send documents to a shared printer, those jobs enter a **print queue**. The printer processes them in the order received, first come, first served. ```typescript interface PrintJob { id: number; document: string; pages: number; submittedBy: string; } class PrinterQueue { private queue: Queue; private jobCounter: number; constructor() { this.queue = new Queue(); this.jobCounter = 0; } submitJob(document: string, pages: number, user: string): number { const jobId = ++this.jobCounter; this.queue.enqueue({ id: jobId, document, pages, submittedBy: user, }); console.log(`Job #${jobId} queued: "${document}" (${pages} pages) by ${user}`); return jobId; } processNext(): PrintJob | undefined { const job = this.queue.dequeue(); if (job) { console.log(`Printing: "${job.document}" (${job.pages} pages) for ${job.submittedBy}`); } else { console.log("No jobs in queue."); } return job; } pendingJobs(): number { return this.queue.size(); } } ``` ```typescript const printer = new PrinterQueue(); printer.submitJob("Report Q4", 12, "Alice"); printer.submitJob("Invoice #1001", 2, "Bob"); printer.submitJob("Presentation.pdf", 30, "Charlie"); console.log(`Pending: ${printer.pendingJobs()}`); // 3 printer.processNext(); // Printing: "Report Q4" (Alice first in line) printer.processNext(); // Printing: "Invoice #1001" (Bob second) printer.processNext(); // Printing: "Presentation.pdf" (Charlie third) printer.processNext(); // No jobs in queue. ``` ### 2. Task Queues and the Node.js Event Loop Node.js uses queues extensively in its **event loop**. When asynchronous operations complete (file reads, HTTP responses, timers), their callbacks are placed in a queue and processed in order. The event loop has multiple queues: - **Microtask queue** (Promises, `queueMicrotask`) - **Macrotask queue** (setTimeout, setInterval, I/O callbacks) - **Check queue** (`setImmediate`) Each tick of the event loop drains the microtask queue first, then processes one macrotask, then checks again for microtasks, and so on. It's queues all the way down. ```typescript class TaskQueue { private queue: Queue<() => Promise>; private isProcessing: boolean; constructor() { this.queue = new Queue<() => Promise>(); this.isProcessing = false; } addTask(task: () => Promise): void { this.queue.enqueue(task); this.processQueue(); } private async processQueue(): Promise { if (this.isProcessing) return; this.isProcessing = true; while (!this.queue.isEmpty()) { const task = this.queue.dequeue(); if (task) { try { await task(); } catch (error) { console.error("Task failed:", error); } } } this.isProcessing = false; } } ``` ### 3. Breadth-First Search (BFS) BFS is one of the most important graph/tree traversal algorithms, and it relies entirely on a queue. The idea is to visit all neighbors at the current depth before moving to the next level. ```typescript function bfs(graph: Map, start: string): string[] { const visited = new Set(); const queue = new Queue(); const result: string[] = []; queue.enqueue(start); visited.add(start); while (!queue.isEmpty()) { const node = queue.dequeue()!; result.push(node); const neighbors = graph.get(node) || []; for (const neighbor of neighbors) { if (!visited.has(neighbor)) { visited.add(neighbor); queue.enqueue(neighbor); } } } return result; } const socialGraph = new Map([ ["Alice", ["Bob", "Charlie"]], ["Bob", ["Alice", "Diana"]], ["Charlie", ["Alice", "Eve"]], ["Diana", ["Bob"]], ["Eve", ["Charlie"]], ]); console.log(bfs(socialGraph, "Alice")); // ["Alice", "Bob", "Charlie", "Diana", "Eve"] ``` BFS visits nodes level by level, which is perfect for finding the **shortest path** in an unweighted graph. ### 4. Rate Limiting / Throttling APIs often use queues to implement rate limiting. Incoming requests enter a queue, and only a certain number are processed per time window. This prevents overwhelming the server. ```typescript class RateLimiter { private timestamps: Queue; private maxRequests: number; private windowMs: number; constructor(maxRequests: number, windowMs: number) { this.timestamps = new Queue(); this.maxRequests = maxRequests; this.windowMs = windowMs; } allowRequest(): boolean { const now = Date.now(); const windowStart = now - this.windowMs; while (!this.timestamps.isEmpty() && this.timestamps.front()! <= windowStart) { this.timestamps.dequeue(); } if (this.timestamps.size() < this.maxRequests) { this.timestamps.enqueue(now); return true; } return false; } } const limiter = new RateLimiter(5, 60_000); console.log(limiter.allowRequest()); // true (1/5) console.log(limiter.allowRequest()); // true (2/5) console.log(limiter.allowRequest()); // true (3/5) console.log(limiter.allowRequest()); // true (4/5) console.log(limiter.allowRequest()); // true (5/5) console.log(limiter.allowRequest()); // false (rate limit exceeded) ``` ### 5. Message Queues in Distributed Systems At a larger scale, **message queues** like RabbitMQ, Apache Kafka, Amazon SQS, and BullMQ are queues that sit between services. One service produces messages, another consumes them. The queue ensures reliable, ordered delivery even if the consumer is temporarily down. Common use cases: - **Email services**: A web app enqueues “send email” jobs, and a worker process dequeues and sends them. - **Order processing**: An e-commerce checkout enqueues orders, and a fulfillment service processes them one by one. - **Log aggregation**: Application instances push logs to a queue, and a centralized service consumes and stores them. The concept is the same as our simple `Queue` class, just distributed across networks with persistence, retries, and dead-letter queues. --- ## The Deque (Double-Ended Queue) A **deque** (pronounced “deck”) is a generalization of both stacks and queues. It allows insertion and removal from **both ends**, the front and the back. Think of it like a **two-way line** where people can join or leave from either end. ### When Would You Use a Deque? - **Sliding window algorithms**: You often need to add to the back and remove from the front AND back. - **Palindrome checking**: Compare characters from both ends. - **Undo/redo with branching**: Navigate history from either direction. - **Work-stealing algorithms**: Threads steal tasks from each other's deques. - **Browser history with both back AND forward**: Remove from either end when limits are reached. ### Core Operations | Operation | Description | Big O | |-----------------------|---------------------------------------|-------| | `addFront(item)` | Add an item to the front | O(1) | | `addBack(item)` | Add an item to the back | O(1) | | `removeFront()` | Remove and return the front item | O(1) | | `removeBack()` | Remove and return the back item | O(1) | | `peekFront()` | View the front item | O(1) | | `peekBack()` | View the back item | O(1) | | `isEmpty()` | Check if the deque is empty | O(1) | | `size()` | Return the number of items | O(1) | ### TypeScript Implementation We'll use a doubly linked list so every operation is guaranteed O(1): ```typescript class DequeNode { value: T; prev: DequeNode | null; next: DequeNode | null; constructor(value: T) { this.value = value; this.prev = null; this.next = null; } } class Deque { private head: DequeNode | null; private tail: DequeNode | null; private count: number; constructor() { this.head = null; this.tail = null; this.count = 0; } addFront(item: T): void { const newNode = new DequeNode(item); if (!this.head) { this.head = newNode; this.tail = newNode; } else { newNode.next = this.head; this.head.prev = newNode; this.head = newNode; } this.count++; } addBack(item: T): void { const newNode = new DequeNode(item); if (!this.tail) { this.head = newNode; this.tail = newNode; } else { newNode.prev = this.tail; this.tail.next = newNode; this.tail = newNode; } this.count++; } removeFront(): T | undefined { if (!this.head) return undefined; const value = this.head.value; this.head = this.head.next; if (this.head) { this.head.prev = null; } else { this.tail = null; } this.count--; return value; } removeBack(): T | undefined { if (!this.tail) return undefined; const value = this.tail.value; this.tail = this.tail.prev; if (this.tail) { this.tail.next = null; } else { this.head = null; } this.count--; return value; } peekFront(): T | undefined { return this.head?.value; } peekBack(): T | undefined { return this.tail?.value; } isEmpty(): boolean { return this.count === 0; } size(): number { return this.count; } clear(): void { this.head = null; this.tail = null; this.count = 0; } } ``` ### Usage Examples ```typescript const deque = new Deque(); deque.addBack(1); deque.addBack(2); deque.addBack(3); deque.addFront(0); deque.addFront(-1); // Deque is now: [-1, 0, 1, 2, 3] console.log(deque.peekFront()); // -1 console.log(deque.peekBack()); // 3 console.log(deque.removeFront()); // -1 console.log(deque.removeBack()); // 3 // Deque is now: [0, 1, 2] console.log(deque.size()); // 3 ``` A deque can act as a **stack** (add/remove from the same end) or a **queue** (add to one end, remove from the other). It's the most flexible linear structure. > **Tip**: If you ever find yourself needing both stack-like and queue-like behavior in the same problem (especially in sliding window patterns), reach for a deque. --- ## Priority Queue A **priority queue** is like a regular queue, but with a twist: instead of processing items in the order they arrived, it processes the item with the **highest (or lowest) priority** first. Think of a **hospital emergency room**. Patients don't get treated in the order they arrive. Someone having a heart attack gets seen before someone with a paper cut, regardless of who arrived first. That's a priority queue. ### How It Differs from a Regular Queue | Feature | Regular Queue | Priority Queue | |----------------|----------------------|----------------------------| | Order | FIFO | By priority | | Enqueue | Add to back | Add with a priority value | | Dequeue | Remove from front | Remove highest priority | | Implementation | Array/Linked List | Typically a Binary Heap | ### Simple TypeScript Implementation For a production priority queue, you'd use a **binary heap** (which we'll cover in a future Trees article). Here's a simplified version to understand the concept: ```typescript interface PriorityItem { value: T; priority: number; } class SimplePriorityQueue { private items: PriorityItem[]; constructor() { this.items = []; } enqueue(value: T, priority: number): void { const newItem: PriorityItem = { value, priority }; let inserted = false; for (let i = 0; i < this.items.length; i++) { if (newItem.priority < this.items[i].priority) { this.items.splice(i, 0, newItem); inserted = true; break; } } if (!inserted) { this.items.push(newItem); } } dequeue(): T | undefined { return this.items.shift()?.value; } peek(): T | undefined { return this.items[0]?.value; } isEmpty(): boolean { return this.items.length === 0; } size(): number { return this.items.length; } } ``` ```typescript const er = new SimplePriorityQueue(); er.enqueue("Paper cut", 5); er.enqueue("Heart attack", 1); er.enqueue("Broken arm", 3); er.enqueue("Headache", 4); er.enqueue("Allergic reaction", 2); console.log(er.dequeue()); // "Heart attack" (priority 1) console.log(er.dequeue()); // "Allergic reaction" (priority 2) console.log(er.dequeue()); // "Broken arm" (priority 3) console.log(er.dequeue()); // "Headache" (priority 4) console.log(er.dequeue()); // "Paper cut" (priority 5) ``` ### Big O Comparison | Operation | Simple (sorted array) | Heap-Based | |-----------|-----------------------|-------------| | `enqueue` | O(n) | O(log n) | | `dequeue` | O(1)* | O(log n) | | `peek` | O(1) | O(1) | *\*O(1) only because we keep the array sorted during insertion. The O(n) cost is paid during enqueue.* > **Coming soon**: The heap-based priority queue delivers O(log n) for both enqueue and dequeue, making it far superior for large datasets. We'll build one from scratch in the **Trees and Heaps** article. --- ## Circular Queue (Ring Buffer) A **circular queue** (also called a **ring buffer**) is a fixed-size queue where the last position wraps around to the first position. When the queue is full, it reuses slots that were previously freed by dequeue operations. Think of it like a **revolving sushi conveyor belt**. There are a fixed number of plates on the belt. When a plate is taken (dequeued), that slot becomes empty and can be filled with a new plate the next time the belt comes around. ### Why Use a Circular Queue? - **Fixed memory**: Great for memory-constrained environments (embedded systems, audio buffers). - **No wasted space**: Unlike the object-based queue where old indices are never reused, a circular queue recycles positions. - **Predictable performance**: No resizing, no garbage collection pressure. - **Common in**: Audio/video streaming buffers, OS schedulers, network packet buffers. ### How It Works Visually ``` Capacity: 5 Initial state (empty): ┌───┬───┬───┬───┬───┐ │ │ │ │ │ │ └───┴───┴───┴───┴───┘ ↑ head/tail After enqueue(A), enqueue(B), enqueue(C): ┌───┬───┬───┬───┬───┐ │ A │ B │ C │ │ │ └───┴───┴───┴───┴───┘ ↑ ↑ head tail After dequeue() → A, dequeue() → B: ┌───┬───┬───┬───┬───┐ │ │ │ C │ │ │ └───┴───┴───┴───┴───┘ ↑ ↑ head tail After enqueue(D), enqueue(E), enqueue(F): ┌───┬───┬───┬───┬───┐ │ │ │ C │ D │ E │ └───┴───┴───┴───┴───┘ ↑ ↑ (wraps to index 0) head tail After enqueue(F) — tail wraps around: ┌───┬───┬───┬───┬───┐ │ F │ │ C │ D │ E │ └───┴───┴───┴───┴───┘ ↑ ↑ tail head → wrapping! ``` ### TypeScript Implementation ```typescript class CircularQueue { private items: (T | undefined)[]; private head: number; private tail: number; private count: number; private capacity: number; constructor(capacity: number) { this.capacity = capacity; this.items = new Array(capacity).fill(undefined); this.head = 0; this.tail = 0; this.count = 0; } enqueue(item: T): boolean { if (this.isFull()) { return false; } this.items[this.tail] = item; this.tail = (this.tail + 1) % this.capacity; this.count++; return true; } dequeue(): T | undefined { if (this.isEmpty()) { return undefined; } const item = this.items[this.head]; this.items[this.head] = undefined; this.head = (this.head + 1) % this.capacity; this.count--; return item; } front(): T | undefined { if (this.isEmpty()) return undefined; return this.items[this.head]; } rear(): T | undefined { if (this.isEmpty()) return undefined; const index = (this.tail - 1 + this.capacity) % this.capacity; return this.items[index]; } isEmpty(): boolean { return this.count === 0; } isFull(): boolean { return this.count === this.capacity; } size(): number { return this.count; } } ``` The key trick is the **modulo operator** (`%`). It makes the indices wrap around: - `(this.tail + 1) % this.capacity` wraps the tail back to 0 when it reaches the end. - `(this.head + 1) % this.capacity` wraps the head back to 0 when it reaches the end. ### Usage Examples ```typescript const buffer = new CircularQueue(3); console.log(buffer.enqueue("A")); // true console.log(buffer.enqueue("B")); // true console.log(buffer.enqueue("C")); // true console.log(buffer.enqueue("D")); // false (full!) console.log(buffer.isFull()); // true console.log(buffer.dequeue()); // "A" console.log(buffer.enqueue("D")); // true (slot freed up) console.log(buffer.front()); // "B" console.log(buffer.rear()); // "D" console.log(buffer.size()); // 3 console.log(buffer.dequeue()); // "B" console.log(buffer.dequeue()); // "C" console.log(buffer.dequeue()); // "D" console.log(buffer.isEmpty()); // true ``` ### Big O Analysis (Circular Queue) | Operation | Time Complexity | Space Complexity | |------------|-----------------|------------------| | `enqueue` | O(1) | O(1) | | `dequeue` | O(1) | O(1) | | `front` | O(1) | O(1) | | `rear` | O(1) | O(1) | | `isEmpty` | O(1) | O(1) | | `isFull` | O(1) | O(1) | > **Tip**: Circular queues are particularly useful when you know the maximum size upfront. They're used in audio processing (fixed-size sample buffers), networking (packet ring buffers), and operating system schedulers (round-robin scheduling with a fixed process pool). --- ## Stack vs Queue: A Side-by-Side Comparison Let's put everything together in a clear comparison: | Feature | Stack | Queue | |---------------------|------------------------------|-------------------------------| | **Principle** | LIFO (Last In, First Out) | FIFO (First In, First Out) | | **Add operation** | `push` (to top) | `enqueue` (to back) | | **Remove operation**| `pop` (from top) | `dequeue` (from front) | | **Peek** | Top element | Front element | | **Real-world analogy** | Stack of plates, Pringles can | Line at a store, drive-through | | **Primary use cases** | Undo/redo, DFS, call stack, parsing | BFS, scheduling, buffering, message passing | | **Access pattern** | One end only | Two ends (add back, remove front) | | **Traversal algo** | DFS (Depth-First Search) | BFS (Breadth-First Search) | ### When to Use a Stack - You need to **reverse** things (reverse a string, reverse a list) - You need to **backtrack** (maze solving, DFS, undo operations) - You need to **match pairs** (parentheses, HTML tags) - You need to **evaluate expressions** (postfix, infix conversion) - You need to track **nested** structures (function calls, recursive descent) ### When to Use a Queue - You need **fairness** (first come, first served) - You need **level-by-level processing** (BFS, tree level order traversal) - You need **buffering** (I/O buffers, streaming data) - You need **scheduling** (print jobs, task queues, CPU scheduling) - You need **rate limiting** (throttling API requests) > **Rule of thumb**: If the problem involves **depth** or **nesting**, think stack. If it involves **breadth** or **ordering**, think queue. If you need both directions, think deque. --- ## Common Pitfalls Even experienced developers make these mistakes. Let's make sure you don't. ### 1. Using `Array.shift()` for Queue Dequeue This is the number one performance pitfall with queues in JavaScript: ```typescript // ❌ Don't do this for large queues const queue: number[] = []; queue.push(1); // enqueue queue.shift(); // dequeue — O(n)! // ✅ Do this instead const betterQueue = new Queue(); // our object-based implementation betterQueue.enqueue(1); betterQueue.dequeue(); // O(1) ``` Why it matters: If you're processing 100,000 items through a queue, `shift()` makes it O(n²) overall instead of O(n). That's the difference between milliseconds and minutes. ### 2. Stack Overflow from Unbounded Recursion Every recursive function call pushes a frame onto the **call stack**. If there's no base case (or the input is too large), you'll blow the stack: ```typescript // ❌ This will crash with a stack overflow for large n function sum(n: number): number { if (n <= 0) return 0; return n + sum(n - 1); } sum(100_000); // RangeError: Maximum call stack size exceeded // ✅ Use iteration instead function sumIterative(n: number): number { let total = 0; for (let i = 1; i <= n; i++) { total += i; } return total; } ``` When recursion depth might be large, consider converting to an **iterative approach using an explicit stack**: ```typescript // Convert recursive DFS to iterative DFS with a stack function iterativeDFS(graph: Map, start: string): string[] { const visited = new Set(); const stack = new Stack(); const result: string[] = []; stack.push(start); while (!stack.isEmpty()) { const node = stack.pop()!; if (visited.has(node)) continue; visited.add(node); result.push(node); const neighbors = graph.get(node) || []; for (const neighbor of neighbors.reverse()) { if (!visited.has(neighbor)) { stack.push(neighbor); } } } return result; } ``` ### 3. Forgetting Edge Cases (Empty Stack/Queue) Always handle the case where the stack or queue is empty: ```typescript // ❌ Will crash if stack is empty const stack = new Stack(); const top = stack.pop()!; // undefined, then using ! lies to TypeScript // ✅ Check before accessing const stack2 = new Stack(); if (!stack2.isEmpty()) { const top = stack2.pop()!; // safe to use top } else { console.log("Stack is empty, nothing to pop."); } // ✅ Or handle undefined gracefully const value = stack2.pop(); if (value !== undefined) { // process value } ``` ### 4. Confusing Stack and Queue in BFS/DFS Using a **stack** when you meant to use a **queue** (or vice versa) is a subtle bug that produces incorrect traversal orders: ```typescript // BFS uses a QUEUE function bfs(start: string): string[] { /* use Queue */ } // DFS uses a STACK (or recursion, which implicitly uses the call stack) function dfs(start: string): string[] { /* use Stack */ } ``` > **Memory aid**: **B**FS = **B**readth = **B**ack of the line (Queue). **D**FS = **D**epth = **D**ig deeper (Stack). ### 5. Not Considering Thread Safety In multi-threaded or concurrent environments, standard stacks and queues are not thread-safe. If multiple threads or async operations modify the same structure simultaneously, you'll get race conditions. In those cases, use libraries that provide thread-safe or concurrent data structures, or protect access with mutexes/locks. --- ## Quick Reference / Cheat Sheet Here's everything you need at a glance. ### Stack Operations ``` ┌──────────────────────────────────────────┐ │ STACK (LIFO) │ ├──────────────┬─────────┬─────────────────┤ │ Operation │ Big O │ Description │ ├──────────────┼─────────┼─────────────────┤ │ push(item) │ O(1) │ Add to top │ │ pop() │ O(1) │ Remove top │ │ peek() │ O(1) │ View top │ │ isEmpty() │ O(1) │ Check empty │ │ size() │ O(1) │ Count items │ └──────────────┴─────────┴─────────────────┘ ``` ### Queue Operations ``` ┌──────────────────────────────────────────┐ │ QUEUE (FIFO) │ ├──────────────┬─────────┬─────────────────┤ │ Operation │ Big O │ Description │ ├──────────────┼─────────┼─────────────────┤ │ enqueue() │ O(1) │ Add to back │ │ dequeue() │ O(1)* │ Remove front │ │ front() │ O(1) │ View front │ │ isEmpty() │ O(1) │ Check empty │ │ size() │ O(1) │ Count items │ └──────────────┴─────────┴─────────────────┘ * O(1) with object-based or linked-list implementation. O(n) with Array.shift()! ``` ### Deque Operations ``` ┌──────────────────────────────────────────────┐ │ DEQUE (Double-Ended) │ ├──────────────────┬─────────┬─────────────────┤ │ Operation │ Big O │ Description │ ├──────────────────┼─────────┼─────────────────┤ │ addFront() │ O(1) │ Add to front │ │ addBack() │ O(1) │ Add to back │ │ removeFront() │ O(1) │ Remove front │ │ removeBack() │ O(1) │ Remove back │ │ peekFront() │ O(1) │ View front │ │ peekBack() │ O(1) │ View back │ └──────────────────┴─────────┴─────────────────┘ ``` ### Implementation Comparison | Approach | Push/Enqueue | Pop/Dequeue | Pros | Cons | |------------------|-------------|-------------|------------------------|---------------------------| | Array stack | O(1)* | O(1) | Simple, cache-friendly | Occasional resize | | Linked stack | O(1) | O(1) | No resize ever | More memory per node | | Array queue (shift) | O(1)* | O(n) | Simple | Slow dequeue! | | Object queue | O(1) | O(1) | Fast, simple | Growing indices | | Linked queue | O(1) | O(1) | True O(1), clean memory| More memory per node | | Circular queue | O(1) | O(1) | Fixed memory, no waste | Fixed capacity | *\*Amortized* ### Decision Tree: Which Should I Use? ``` Do you need LIFO (last in, first out)? └─ YES → Use a Stack └─ Need guaranteed O(1)? → Linked-List Stack └─ General use? → Array-based Stack Do you need FIFO (first in, first out)? └─ YES → Use a Queue └─ Fixed size buffer? → Circular Queue └─ General use? → Object-based Queue └─ Need clean GC? → Linked-List Queue Do you need both LIFO and FIFO? └─ YES → Use a Deque Do you need priority ordering? └─ YES → Use a Priority Queue (heap-based) ``` --- ## Summary Stacks and queues are deceptively simple. They're just restricted lists, but those restrictions are what give them their power. By limiting how data enters and exits, they model real-world scenarios cleanly and efficiently. Here's what we covered: - **Stacks** follow LIFO. Think plates, Pringles, or the back button. Push and pop from the top. All operations are O(1). - **Queues** follow FIFO. Think coffee shop lines or print jobs. Enqueue at the back, dequeue from the front. Avoid `Array.shift()` for performance. - We built **four implementations**: array-based stack, linked-list stack, object-based queue, and linked-list queue, all with proper TypeScript generics. - **Deques** give you the flexibility of both stacks and queues with O(1) operations at both ends. - **Priority queues** process by priority instead of arrival order, typically backed by a heap. - **Circular queues** are fixed-size and memory-efficient, perfect for buffers and schedulers. - Real-world applications are everywhere: browser navigation, undo/redo, BFS/DFS, rate limiting, message brokers, and more. The key takeaway: **know when to use which**. If you need depth or backtracking, reach for a stack. If you need fairness or level-order processing, reach for a queue. If you need both, reach for a deque. --- ## What's Next? Now that you understand how stacks and queues work under the hood, it's time to put them to work on real problems. In the next article, **“Stacks and Queues Made Simple”**, we'll tackle the most common interview patterns that use these data structures: - Monotonic stacks for “next greater element” problems - Using stacks to simplify file paths and decode strings - BFS patterns with queues for shortest-path problems - Sliding window maximums with deques - And more classic LeetCode patterns broken down step by step You've built the foundation. Now let's sharpen the blade. Happy coding.

Stacks and Queues 101: The Ultimate Beginner's Guide