Chapter 9: Stacks and Queues: Ordered Collections

Welcome back, aspiring software engineer! In our journey through Data Structures and Algorithms, we’ve explored how to set up our TypeScript development environment, understand core programming concepts, and analyze the efficiency of our code. Now, we’re ready to dive into some of the most fundamental and widely used data structures: Stacks and Queues.

These aren’t just abstract concepts; they are the workhorses behind many everyday applications, from your browser’s back button to operating system task management. By the end of this chapter, you’ll not only understand the “what” and “why” of Stacks and Queues but also gain practical skills in implementing them efficiently in TypeScript, analyzing their performance, and recognizing their real-world utility. Get ready to add two powerful tools to your DSA toolkit!

What are Ordered Collections?

Before we jump into Stacks and Queues, let’s briefly revisit the idea of “ordered collections.” In programming, a collection is simply a group of items. An ordered collection means that the items have a specific sequence or position. Think of an array: [10, 20, 30]. The 10 is at index 0, 20 at 1, and 30 at 2. The order matters.

Stacks and Queues are special types of ordered collections that enforce strict rules about how you can add and remove items. This restriction is precisely what makes them so useful for specific problems!

Stacks: Last-In, First-Out (LIFO)

Imagine a stack of plates in a cafeteria. When you add a new plate, you place it on top. When you take a plate, you always take the one from the top. The last plate you put in is the first plate you take out. This is the core principle of a Stack: LIFO - Last-In, First-Out.

Key Stack Operations

Stacks typically support a small set of core operations:

• push(element): Adds an element to the top of the stack.
• pop(): Removes and returns the element from the top of the stack.
• peek() (or top()): Returns the element from the top of the stack without removing it.
• isEmpty(): Checks if the stack contains any elements.
• size(): Returns the number of elements in the stack.

Why Stacks Matter: Real-World Use Cases

Stacks are everywhere in computer science. Think about:

• Browser History: When you navigate to a new page, it’s pushed onto a stack. Clicking the “back” button pops the current page off, revealing the previous one.
• Undo/Redo Functionality: Each action you perform (typing, deleting) is pushed onto an “undo” stack. Clicking “undo” pops an action. A “redo” stack works similarly.
• Function Call Stack: When a program calls a function, information about that function (its local variables, where to return after it finishes) is pushed onto the call stack. When the function completes, its information is popped off. This is fundamental to how programs execute!
• Expression Evaluation: Compilers and interpreters use stacks to evaluate arithmetic expressions (e.g., converting infix to postfix notation).

Visualizing a Stack

Let’s visualize the stack operations:

Notice how 30 was the last item pushed and the first item popped.

Queues: First-In, First-Out (FIFO)

Now, let’s switch gears to Queues. Imagine a line of people waiting to buy tickets. The first person to arrive is the first person to be served. The last person to arrive is the last person to be served. This is the core principle of a Queue: FIFO - First-In, First-Out.

Key Queue Operations

Queues also have a specific set of operations:

• enqueue(element): Adds an element to the rear (back) of the queue.
• dequeue(): Removes and returns the element from the front of the queue.
• peek() (or front()): Returns the element from the front of the queue without removing it.
• isEmpty(): Checks if the queue contains any elements.
• size(): Returns the number of elements in the queue.

Why Queues Matter: Real-World Use Cases

Queues are equally prevalent in computing:

• Task Scheduling: Operating systems use queues to manage processes waiting for the CPU or other resources.
• Printer Queues: Documents sent to a printer wait in a queue and are printed in the order they were received.
• Breadth-First Search (BFS): A fundamental graph traversal algorithm uses a queue to explore nodes level by level.
• Message Queues: In distributed systems, messages between different services are often placed in a message queue to ensure reliable delivery and process them in order.
• Event Handling: User interface events (clicks, key presses) are often processed from an event queue.

Visualizing a Queue

Let’s visualize queue operations:

Notice how Alice was the first item enqueued and the first item dequeued.

Complexity Analysis: Stacks and Queues

When we talk about the “efficiency” of a data structure, we’re typically referring to its time complexity (how long operations take) and space complexity (how much memory it uses). For Stacks and Queues, the goal is to have most core operations run in O(1) constant time.

• push / enqueue: O(1)
• pop / dequeue: O(1)
• peek: O(1)
• isEmpty: O(1)
• size: O(1)

This O(1) efficiency is achievable if the underlying implementation is chosen carefully. For example, using a dynamic array (like JavaScript’s native Array) where elements are added/removed from the end provides O(1) amortized time. If we were to use an array and shift() elements for queue operations, that would be O(N), which is inefficient for large queues. We’ll explore this further in the implementation.

Step-by-Step Implementation in TypeScript

Let’s get our hands dirty and implement these data structures using TypeScript. We’ll use a simple array as our underlying storage for both.

First, ensure you have a project set up from previous chapters. If not, quickly create a new directory, initialize Node.js, and install TypeScript:

# Create a new directory for this chapter
mkdir chapter9-stacks-queues
cd chapter9-stacks-queues

# Initialize Node.js project
npm init -y

# Install TypeScript
npm install typescript --save-dev

# Initialize TypeScript configuration
npx tsc --init

# Open tsconfig.json and ensure "outDir" is set to "./dist" and "rootDir" to "./src"
# You might also want to set "strict" to true for better type safety.

Now, create a src directory and inside it, a file named collections.ts.

mkdir src
touch src/collections.ts

Implementing a Stack in TypeScript

We’ll use a TypeScript class with a generic type <T> to make our stack reusable for any data type.

Open src/collections.ts and let’s start with the Stack class:

// src/collections.ts

/**
 * Represents a Last-In, First-Out (LIFO) collection of elements.
 * @template T The type of elements in the stack.
 */
export class Stack<T> {
    // 1. Declare a private array to hold the stack elements.
    // We use a regular array as the underlying data structure.
    private items: T[];

    // 2. The constructor initializes our empty stack.
    constructor() {
        this.items = [];
    }

    /**
     * Adds an element to the top of the stack.
     * Time Complexity: O(1) - Adding to the end of a JavaScript array is efficient.
     * @param element The element to be added.
     */
    push(element: T): void {
        this.items.push(element); // `Array.prototype.push` adds to the end.
    }

    /**
     * Removes and returns the element from the top of the stack.
     * Time Complexity: O(1) - Removing from the end of a JavaScript array is efficient.
     * @returns The element removed from the stack, or `undefined` if the stack is empty.
     */
    pop(): T | undefined {
        // Always check if the stack is empty before trying to pop.
        if (this.isEmpty()) {
            console.warn("Attempted to pop from an empty stack.");
            return undefined;
        }
        return this.items.pop(); // `Array.prototype.pop` removes from the end.
    }

    /**
     * Returns the element from the top of the stack without removing it.
     * Time Complexity: O(1) - Accessing the last element of an array is direct.
     * @returns The element at the top of the stack, or `undefined` if the stack is empty.
     */
    peek(): T | undefined {
        if (this.isEmpty()) {
            return undefined;
        }
        // Access the last element without removing it.
        return this.items[this.items.length - 1];
    }

    /**
     * Checks if the stack is empty.
     * Time Complexity: O(1) - Checking array length is direct.
     * @returns `true` if the stack contains no elements, `false` otherwise.
     */
    isEmpty(): boolean {
        return this.items.length === 0;
    }

    /**
     * Returns the number of elements in the stack.
     * Time Complexity: O(1) - Getting array length is direct.
     * @returns The number of elements in the stack.
     */
    size(): number {
        return this.items.length;
    }
}

Explanation:

• export class Stack<T>: We define a class Stack that is generic (<T>). This means T can be replaced by any type (e.g., Stack<number>, Stack<string>, Stack<{ name: string }>) making our stack versatile.
• private items: T[]: This is the core of our stack: a private array that will store all the elements. It’s private to ensure users interact with the stack only through its defined methods, maintaining its LIFO integrity.
• constructor(): Initializes the items array as empty when a new Stack instance is created.
• push(element: T): Uses Array.prototype.push(). This method adds an element to the end of the array. In a stack, the “end” of the array acts as the “top” of the stack. This operation is O(1).
• pop(): T | undefined: Uses Array.prototype.pop(). This method removes and returns the last element from the array. This corresponds to removing from the “top” of the stack. It’s crucial to check isEmpty() first to prevent errors if the stack is empty. This operation is also O(1).
• peek(): T | undefined: Directly accesses the last element of the array (this.items[this.items.length - 1]) without modifying the array. This is the “top” element. O(1).
• isEmpty() and size(): These simply leverage the underlying array’s length property, making them O(1) operations.

Let’s test our Stack! Create a file src/app.ts:

// src/app.ts
import { Stack } from './collections';

console.log("--- Testing Stack ---");

const numberStack = new Stack<number>();
console.log(`Is stack empty? ${numberStack.isEmpty()}`); // true

numberStack.push(10);
numberStack.push(20);
numberStack.push(30);

console.log(`Stack size: ${numberStack.size()}`); // 3
console.log(`Top element: ${numberStack.peek()}`); // 30

const popped1 = numberStack.pop();
console.log(`Popped: ${popped1}`); // 30
console.log(`Stack size after pop: ${numberStack.size()}`); // 2
console.log(`New top element: ${numberStack.peek()}`); // 20

numberStack.pop(); // Popping 20
numberStack.pop(); // Popping 10
const poppedEmpty = numberStack.pop(); // Attempt to pop from empty stack
console.log(`Popped from empty: ${poppedEmpty}`); // undefined (and a warning)
console.log(`Is stack empty? ${numberStack.isEmpty()}`); // true

Compile and run:

npx tsc # Compiles src/collections.ts and src/app.ts into the dist folder
node dist/app.js

You should see output reflecting the LIFO behavior. Great job!

Implementing a Queue in TypeScript (Optimized Array-Based)

For implementing a Queue using an array, we need to be careful. If we simply use Array.prototype.push() for enqueue (adding to the end) and Array.prototype.shift() for dequeue (removing from the beginning), dequeue would be an O(N) operation. Why? Because shift() requires re-indexing all subsequent elements in the array, which becomes very slow for large queues.

To achieve O(1) for both enqueue and dequeue (amortized), we can optimize our array-based implementation by using two pointers: a head pointer for the front of the queue and a tail pointer for the rear. Elements will be added at tail and removed from head. When the queue is logically empty, we can reset the pointers and clear the array.

Let’s add the Queue class to src/collections.ts below your Stack class:

// src/collections.ts (continued)

/**
 * Represents a First-In, First-Out (FIFO) collection of elements.
 * @template T The type of elements in the queue.
 */
export class Queue<T> {
    private items: T[];
    private head: number; // Index of the front element
    private tail: number; // Index where the next element will be added

    constructor() {
        this.items = [];
        this.head = 0;
        this.tail = 0;
    }

    /**
     * Adds an element to the rear of the queue.
     * Time Complexity: O(1) - Adding to the end of an array by index is direct.
     * @param element The element to be added.
     */
    enqueue(element: T): void {
        this.items[this.tail] = element; // Place element at the current tail index
        this.tail++; // Move tail pointer to the next available slot
    }

    /**
     * Removes and returns the element from the front of the queue.
     * Time Complexity: O(1) - Accessing and incrementing head pointer is direct.
     * @returns The element removed from the queue, or `undefined` if the queue is empty.
     */
    dequeue(): T | undefined {
        if (this.isEmpty()) {
            console.warn("Attempted to dequeue from an empty queue.");
            return undefined;
        }

        const item = this.items[this.head]; // Get the element at the head
        delete this.items[this.head]; // Optional: Clear the reference to aid garbage collection
        this.head++; // Move head pointer forward

        // Optimization: If the queue becomes empty after dequeue,
        // reset head and tail to 0 and clear the array to reclaim memory.
        // This keeps the array from growing indefinitely with 'undefined' holes
        // and ensures `head` and `tail` don't overflow for extremely long-running queues.
        if (this.isEmpty()) {
            this.head = 0;
            this.tail = 0;
            this.items = []; // Re-initialize the array
        }
        return item;
    }

    /**
     * Returns the element from the front of the queue without removing it.
     * Time Complexity: O(1) - Accessing element at head index is direct.
     * @returns The element at the front of the queue, or `undefined` if the queue is empty.
     */
    peek(): T | undefined {
        if (this.isEmpty()) {
            return undefined;
        }
        return this.items[this.head];
    }

    /**
     * Checks if the queue is empty.
     * Time Complexity: O(1) - Comparing head and tail pointers is direct.
     * @returns `true` if the queue contains no elements, `false` otherwise.
     */
    isEmpty(): boolean {
        // The queue is empty when head and tail pointers are at the same position.
        return this.head === this.tail;
    }

    /**
     * Returns the number of elements currently in the queue.
     * Time Complexity: O(1) - Simple subtraction.
     * @returns The number of elements in the queue.
     */
    size(): number {
        return this.tail - this.head;
    }
}

Explanation of the Optimized Queue:

• private head: number; private tail: number;: We introduce two pointers. head points to the first actual element in the queue. tail points to the position where the next element will be inserted.
• enqueue(element: T): We place the element directly at this.items[this.tail] and then increment this.tail. This is an O(1) operation.
• dequeue(): T | undefined: We retrieve the element at this.items[this.head], then increment this.head. This is also an O(1) operation because we are not re-indexing the entire array.
  • delete this.items[this.head]: This line is important. While head moves forward, the old items[head] spot still holds a reference to the element. Using delete removes that reference, allowing the garbage collector to reclaim memory if the element is no longer referenced anywhere else. It leaves an undefined “hole” in the array, but since we only care about elements between head and tail, this is fine.
  • Resetting on Empty: When head catches up to tail, it means the queue is logically empty. At this point, we reset head and tail to 0 and clear the items array. This prevents the array from becoming excessively large with undefined holes over time and ensures our pointers don’t grow indefinitely. This reset operation is O(N) in the worst case (when a very large queue becomes empty), but it happens infrequently, making the average (amortized) time complexity O(1).
• peek(): Simply returns this.items[this.head]. O(1).
• isEmpty(): The queue is empty when head equals tail. O(1).
• size(): The number of elements is simply the difference between tail and head. O(1).

Let’s add tests for our Queue in src/app.ts:

// src/app.ts (continued)
import { Stack, Queue } from './collections'; // Make sure to import Queue as well

// ... (Stack testing code from before) ...

console.log("\n--- Testing Queue ---");

const stringQueue = new Queue<string>();
console.log(`Is queue empty? ${stringQueue.isEmpty()}`); // true

stringQueue.enqueue("Alice");
stringQueue.enqueue("Bob");
stringQueue.enqueue("Charlie");

console.log(`Queue size: ${stringQueue.size()}`); // 3
console.log(`Front element: ${stringQueue.peek()}`); // Alice

const dequeued1 = stringQueue.dequeue();
console.log(`Dequeued: ${dequeued1}`); // Alice
console.log(`Queue size after dequeue: ${stringQueue.size()}`); // 2
console.log(`New front element: ${stringQueue.peek()}`); // Bob

stringQueue.enqueue("David"); // Add David to the rear
console.log(`Queue after enqueuing David: Size=${stringQueue.size()}, Front=${stringQueue.peek()}`); // Size=3, Front=Bob

stringQueue.dequeue(); // Dequeuing Bob
stringQueue.dequeue(); // Dequeuing Charlie
stringQueue.dequeue(); // Dequeuing David

const dequeuedEmpty = stringQueue.dequeue(); // Attempt to dequeue from empty queue
console.log(`Dequeued from empty: ${dequeuedEmpty}`); // undefined (and a warning)
console.log(`Is queue empty? ${stringQueue.isEmpty()}`); // true

Compile and run again:

npx tsc
node dist/app.js

You should now see the FIFO behavior for the queue. Fantastic!

Mini-Challenge: Applying Stacks and Queues

Time to put your new knowledge to the test!

Challenge 1: Reverse a String Using a Stack

Challenge: Write a TypeScript function reverseString(input: string): string that takes a string as input and returns its reversed version using your Stack class.

Hint: Think about how the LIFO principle helps with reversing order.

Challenge 2: Hot Potato Game Simulation Using a Queue

Challenge: Implement a function hotPotato(nameList: string[], num: number): { winner: string, eliminated: string[] } that simulates the “Hot Potato” game. In this game, children stand in a circle and pass a potato. After a certain number of passes, the child holding the potato is eliminated. The game continues until only one child remains.

Your function should:

1. Take an array of names (nameList) and a number (num) representing how many passes before elimination.
2. Use your Queue class to simulate the game.
3. Return an object containing the winner and an array of eliminated players in order.

Hint: For num passes, dequeue and enqueue num - 1 times. The num-th dequeue is the eliminated player.

Take your time with these challenges. Try to solve them independently first!

Common Pitfalls & Troubleshooting

1. Off-by-One Errors with Indices: Especially in array-based implementations, it’s easy to mix up length, length - 1, head, and tail indices. Always double-check your logic when accessing array elements.
2. Forgetting isEmpty() Checks: Attempting to pop() or dequeue() from an empty collection will lead to undefined or runtime errors if not handled gracefully. Always check isEmpty() before performing removal or peek operations.
3. Performance of Array.prototype.shift(): As discussed, using shift() for dequeue in a large queue will result in O(N) performance, which is a major bottleneck. Always prefer pointer-based or linked-list-based queue implementations for O(1) efficiency.
4. Memory Leaks (for non-primitive types): In our optimized array-based queue, we used delete this.items[this.head];. If you omit this for objects, even though head moves forward, the reference to the object at the old head index might still exist in the items array, preventing it from being garbage collected. This is less of an issue for primitives (numbers, strings) but crucial for complex objects. The delete keyword helps, or the full items = [] reset when empty.
5. Not Using Generics: Initially, you might implement a stack or queue for a specific type (e.g., number[]). Using generics (<T>) makes your data structures reusable and type-safe across your entire application.

Summary

Congratulations! You’ve successfully navigated the world of Stacks and Queues. Here are the key takeaways from this chapter:

• Stacks are LIFO (Last-In, First-Out) data structures, analogous to a stack of plates.
• Queues are FIFO (First-In, First-Out) data structures, analogous to a waiting line.
• Both provide a restricted interface for adding (push/enqueue) and removing (pop/dequeue) elements, which makes them ideal for specific problem domains.
• Core operations (push, pop, peek, enqueue, dequeue, isEmpty, size) should ideally have O(1) time complexity.
• We learned how to implement both Stack and Queue using TypeScript classes with generic types and an underlying array, ensuring O(1) amortized performance for all core operations in our optimized queue.
• You now understand the importance of choosing the right underlying implementation to maintain performance (e.g., avoiding Array.prototype.shift() for queues).
• Stacks and Queues are fundamental and appear in many real-world applications, from browser history to operating system scheduling.

In the next chapter, we’ll build upon these concepts and explore Linked Lists, another linear data structure that offers distinct advantages for certain operations, particularly for efficient insertions and deletions anywhere in the list. This will give us another powerful tool to implement our Stacks and Queues, offering truly O(1) performance without the amortized complexity of array resizing.

References

• Node.js v25.6.1 (Current) Documentation
• TypeScript Handbook - Classes
• TypeScript Handbook - Generics
• MDN Web Docs - Array.prototype.push()
• MDN Web Docs - Array.prototype.pop()
• MDN Web Docs - delete operator

This page is AI-assisted and reviewed. It references official documentation and recognized resources where relevant.