How do Queue<T> and Stack<T> work in C#? Explain their internal storage, Enqueue/Dequeue and Push/Pop, the Try methods, the enumeration order, and when you would use PriorityQueue<TElement,TPriority> or a concurrent queue instead.

1. The circular buffer in Queue<T>

capacity 8, after enqueuing A..F and dequeuing A, B:
index:  0   1   2   3   4   5   6   7
       [ ] [ ] [C] [D] [E] [F] [ ] [ ]
                ^head           ^tail

enqueue G, H, I (I wraps to index 0):
       [I] [ ] [C] [D] [E] [F] [G] [H]
            ^tail ^head

• Enqueue: _array[_tail] = item; MoveNext(ref _tail); _size++, where MoveNext wraps to 0 at the end (implemented with a compare rather than % for speed).
• Dequeue: read _array[_head], clear the slot if T contains references (so the GC can collect the object), advance _head.
• Growth: when _size == _array.Length, allocate a larger array (2×, minimum +4) and copy the two segments (_head..end and 0.._tail) so the new array starts at index 0.

Without the ring buffer, dequeuing from the front of an array would require shifting (O(n)) as List<T>.RemoveAt(0) does.

2. Why Stack<T> and Queue<T> clear slots

When T is a reference type (or a struct containing references), popped/dequeued slots are set to default. Otherwise the backing array would keep removed objects reachable and prevent garbage collection — a subtle memory leak in long-lived queues. For unmanaged T, the runtime skips clearing for speed (RuntimeHelpers.IsReferenceOrContainsReferences<T>()).

3. Binary and d-ary heaps

PriorityQueue stores a complete tree in an array. For a 4-ary heap, the children of node i are at 4i + 1 .. 4i + 4, and the parent at (i − 1) / 4.

• Enqueue: append at the end, then sift up (swap with parent while smaller) — O(log₄ n).
• Dequeue: take the root, move the last element to the root, then sift down (swap with the smallest child) — O(log₄ n) levels, each comparing up to 4 children.

A 4-ary heap is shallower than a binary heap (fewer levels, fewer cache misses) at the cost of more comparisons per level; .NET chose arity 4 after benchmarking. EnqueueRange and the constructor from a collection use heapify (Floyd's algorithm), O(n), which is faster than n enqueues.

EnqueueDequeue and DequeueEnqueue combine operations efficiently — useful for maintaining a bounded top-N heap.

4. Top-N with a bounded heap

// Keep the 10 largest orders seen in a stream
var heap = new PriorityQueue<Order, decimal>();      // min-heap by total
foreach (var o in orders)
{
    if (heap.Count < 10) heap.Enqueue(o, o.Total);
    else if (heap.TryPeek(out _, out var smallest) && o.Total > smallest) heap.DequeueEnqueue(o, o.Total);
}

O(n log 10) time and O(10) memory, versus sorting everything (O(n log n), O(n) memory).

5. Iterative DFS/BFS

static IEnumerable<Node> Bfs(Node root)
{
    var queue = new Queue<Node>([root]);
    var seen = new HashSet<Node>([root]);
    while (queue.TryDequeue(out var node))
    {
        yield return node;
        foreach (var child in node.Children)
            if (seen.Add(child)) queue.Enqueue(child);
    }
}

Replacing the Queue with a Stack turns it into depth-first traversal. Using an explicit stack avoids recursion depth limits — important because StackOverflowException cannot be caught and terminates the process.

6. Concurrent queues and channels internally

• ConcurrentQueue<T> uses linked segments (arrays) with lock-free head/tail indexes using Interlocked operations; it scales well under contention and never blocks.
• Channel<T> builds on similar structures plus async waiters: ReadAsync completes immediately if data is available, otherwise returns a pending ValueTask completed by the next writer. Bounded channels make writers wait (or drop items, depending on BoundedChannelFullMode), giving backpressure so a fast producer can't exhaust memory.

Try it yourself

1. Implement BFS and DFS over a tree with Queue<T> and Stack<T> and compare visit order.
2. Copy a stack with new Stack<T>(stack) and compare the enumeration order.
3. Enqueue items with equal priority into a PriorityQueue and observe the dequeue order; fix it with a (priority, sequence) tuple.
4. Build a bounded Channel<int> with a slow consumer and watch the producer wait.

// FIFO work list
var work = new Queue<string>();
work.Enqueue("a.csv");
work.Enqueue("b.csv");
while (work.TryDequeue(out var file))
    Console.WriteLine($"Processing {file}");   // a.csv, then b.csv

// LIFO: iterative depth-first walk, no recursion
var pending = new Stack<string>();
pending.Push(rootFolder);
while (pending.TryPop(out var dir))
{
    foreach (var sub in Directory.EnumerateDirectories(dir))
        pending.Push(sub);
}

// Constructor order surprise
var s = new Stack<int>([1, 2, 3]);
Console.WriteLine(s.Pop());                    // 3
Console.WriteLine(string.Join(",", s));       // 2,1

// Priority: lowest value comes out first
var jobs = new PriorityQueue<string, int>();
jobs.Enqueue("email", 3);
jobs.Enqueue("payment", 1);
jobs.Enqueue("report", 2);
while (jobs.TryDequeue(out var job, out var priority))
    Console.WriteLine($"{priority}: {job}");  // payment, report, email