Queue & Stack

Introduction

Queue<T> is FIFO (first in, first out); Stack<T> is LIFO (last in, first out). BFS uses queues; DFS and undo stacks use stacks. ConcurrentQueue and ConcurrentStack exist for threading.

System design maps message queues to Queue abstraction conceptually. Interviewers ask implement queue using stacks and vice versa.

The story

IT support software scans a company's folder hierarchy level by level to index documents — breadth-first search uses a queue. When reconstructing the path from a file back to the root drive for a "restore previous version" feature, a stack walks parent pointers from leaf to root.

Queues and stacks model real FIFO and LIFO workflows that lists simulate poorly at scale.

Understanding the topic

Key concepts

• Queue: Enqueue tail, Dequeue head, Peek.
• Stack: Push top, Pop top, Peek.
• No random access — unlike List.
• ConcurrentQueue lock-free for producers/consumers.
• PriorityQueue (.NET 6+) for heaps.
• LinkedList internal but exposed via Queue/Stack API.

Step-by-step explanation

1. Queue Enqueue adds; Dequeue removes oldest.
2. Stack Push/Pop at same end.
3. Peek observes without remove.
4. Count tracks elements; Clear empties.
5. foreach on Queue iterates without dequeue (copy order).
6. PriorityQueue Dequeue returns lowest priority element.

Practical code example

BFS file folder scan with Queue and Stack-based undo of paths:

namespace TechLearningPro.QueueStack;

public static class FolderScanner
{
    public static IEnumerable<string> BreadthFirst(IEnumerable<string> roots)
    {
        var queue = new Queue<string>(roots);
        while (queue.Count > 0)
        {
            var current = queue.Dequeue();
            yield return current;
            foreach (var child in GetChildren(current))
                queue.Enqueue(child);
        }
    }

    public static Stack<string> BuildPathStack(string leaf, Func<string, string?> getParent)
    {
        var stack = new Stack<string>();
        for (var node = leaf; node is not null; node = getParent(node))
            stack.Push(node);
        return stack;
    }

    private static IEnumerable<string> GetChildren(string path) => [];
}

Line-by-line code explanation

• Queue<string>(roots) initializes the BFS queue with starting folder paths.
• while (queue.Count > 0) continues until every reachable folder is processed.
• var current = queue.Dequeue() removes the oldest folder — FIFO order.
• yield return current emits the current path to the caller lazily.
• foreach (var child in GetChildren(current)) queue.Enqueue(child) adds subfolders for later processing.
• Stack<string>() creates an empty stack for path reconstruction.
• for (var node = leaf; node is not null; node = getParent(node)) walks upward from leaf to root.
• stack.Push(node) records each ancestor — the last push is the root.
• return stack yields root-to-leaf order when popped sequentially.

Key takeaway: Queue for BFS level-order. Stack reconstructs path from leaf to root. PriorityQueue useful for scheduled job dispatch.

Real-world use

Where you'll use this in production

• Background job processors with Queue.
• Undo/redo stacks in desktop editors.
• Breadth-first org hierarchy traversal.
• Parser expression evaluation with stacks.

Best practices

• Use ConcurrentQueue for multi-threaded producers.
• PriorityQueue for task scheduling by priority.
• Avoid Queue for random access — use List.
• Check Count before Dequeue or handle invalid operation.
• Document FIFO vs LIFO expectations in APIs.

Common mistakes

• Dequeue empty queue — InvalidOperationException.
• Using List.RemoveAt(0) as queue — O(n).
• Stack for fairness when FIFO required.
• Unbounded queue growth without backpressure.

Advanced interview questions

Summary

Queue FIFO for fair ordering; Stack LIFO for undo/DFS. Concurrent and Priority variants cover threading and scheduling. Choose correct structure — not List simulation. Classic interview problems test queue/stack fluency. Next: LINQ basics for declarative queries.