LIFO and FIFO structures, their array-based implementations in .NET, the call stack, undo, BFS and work queues, plus ConcurrentStack, ConcurrentQueue and Channels.
Push, Pop, Peek, all O(1). Used for the call stack, undo, expression parsing, DFS and backtracking.Enqueue, Dequeue, Peek, all O(1). Used for work queues, BFS, buffering and rate limiting.In .NET, Stack<T> is an array that grows at the end. Queue<T> is a circular buffer: head and tail indexes wrap around the array, so dequeuing does not shift elements.
Neither is thread-safe. For concurrency use ConcurrentQueue<T>/ConcurrentStack<T>, or better for producer/consumer pipelines, a bounded Channel<T> which adds async waiting and back-pressure.
Stack (LIFO) Queue (FIFO)
Push C ──► ┌───┐ Enqueue ──► [D][C][B][A] ──► Dequeue (A first)
│ C │ ◄── Pop tail head
│ B │
│ A │
└───┘
| Type | Order | Implementation | Thread-safe | Typical use |
|---|---|---|---|---|
Stack<T> |
LIFO | Growable array | No | Undo, DFS, parsing |
Queue<T> |
FIFO | Circular array | No | BFS, buffers |
PriorityQueue<TElement,TPriority> |
By priority | Binary heap | No | Scheduling, Dijkstra |
ConcurrentStack<T> |
LIFO | Lock-free linked nodes | Yes | Object pools |
ConcurrentQueue<T> |
FIFO | Lock-free linked array segments | Yes | Multi-threaded handoff |
Channel<T> |
FIFO | Bounded or unbounded, async | Yes | Producer/consumer with back-pressure |
A background service pulled jobs from an API and processed them in parallel using a List<Job> guarded by lock and a while (true) { Thread.Sleep(100); } polling loop. It wasted CPU, had race bugs and no back-pressure. Replacing it with a bounded Channel<Job> (capacity 500, FullMode = Wait) and 8 consumers using await foreach (var job in reader.ReadAllAsync(ct)) removed the polling, fixed the races, and stopped the producer from outrunning consumers during spikes.
Checks basic data structure knowledge and whether the candidate connects it to real system patterns.
Green flags
Queue<T> is a circular buffer and Stack<T> a growable array.Red flags
List<T>.RemoveAt(0) as a queue.Queue<T> as a circular buffercapacity 8, after some enqueues and dequeues:
index: 0 1 2 3 4 5 6 7
[G] [H] [ ] [ ] [ ] [D] [E] [F]
▲ ▲
tail head
Dequeue → D (head moves to 6). Enqueue I → goes to index 2 (tail moves to 3).
When full, allocate an array twice as large and copy the items in order,
so head starts at 0 again.
No shifting on dequeue, so both ends are O(1), and Enqueue is amortised O(1) because of the occasional resize. Stack<T> is simpler: one array and a count, push and pop at the end, doubling when full. Both offer TrimExcess, EnsureCapacity, TryPeek and TryPop/TryDequeue.
Each thread has a fixed-size stack. On Windows the default is 1 MB; on Linux the main thread uses the ulimit -s value (often 8 MB) while threads .NET creates, including thread-pool threads, default to about 1.5 MB. Deep recursion (for example walking a 100,000-level deep tree recursively) causes StackOverflowException, which cannot be caught and kills the process. Convert deep recursion to an explicit Stack<T> loop.
| Problem | Structure | Idea |
|---|---|---|
| Balanced brackets | Stack | Push openers, pop and match on closers |
| Evaluate Reverse Polish notation | Stack | Push numbers, pop two on an operator |
| Next greater element | Monotonic stack | Each item pushed and popped once: O(n) |
| Queue using two stacks | Two stacks | Move items only when the out-stack is empty: amortised O(1) |
| Sliding window maximum | Deque of indices | Drop smaller values from the back: O(n) |
| Shortest path in an unweighted graph | Queue (BFS) | Level by level from the source |
| Need | Choose |
|---|---|
| Many threads hand off items, no waiting | ConcurrentQueue<T> |
| LIFO reuse of objects across threads | ConcurrentStack<T> or ObjectPool<T> |
Consumers should await items; producers should slow down when full |
Channel.CreateBounded<T> |
| Cross-process, durable, retries and dead-lettering | Service Bus, RabbitMQ, SQS, Kafka |
| Legacy blocking API | BlockingCollection<T> (prefer Channels in new code) |
Stack<char>.Queue<T> behaviour by enqueuing 1–10, dequeuing 5, enqueuing 11–15 and listing contents.Stack<Node>; test on a degenerate 200,000-deep tree.Channel<int> and observe the producer waiting when capacity is reached.// Stack: balanced brackets
static bool IsBalanced(string s)
{
var stack = new Stack<char>();
foreach (var c in s)
{
switch (c)
{
case '(' or '[' or '{': stack.Push(c); break;
case ')' when stack.Count == 0 || stack.Pop() != '(': return false;
case ']' when stack.Count == 0 || stack.Pop() != '[': return false;
case '}' when stack.Count == 0 || stack.Pop() != '{': return false;
}
}
return stack.Count == 0;
}
// Iterative DFS with an explicit stack (no StackOverflowException on deep trees)
static IEnumerable<TreeNode> DepthFirst(TreeNode root)
{
var stack = new Stack<TreeNode>();
stack.Push(root);
while (stack.TryPop(out var node))
{
yield return node;
for (int i = node.Children.Count - 1; i >= 0; i--)
stack.Push(node.Children[i]);
}
}
// Producer/consumer with back-pressure
var channel = Channel.CreateBounded<Job>(new BoundedChannelOptions(500)
{
FullMode = BoundedChannelFullMode.Wait
});
var consumers = Enumerable.Range(0, 8).Select(_ => Task.Run(async () =>
{
await foreach (var job in channel.Reader.ReadAllAsync(ct))
await ProcessAsync(job, ct);
}, ct)).ToArray();
await foreach (var job in source.FetchJobsAsync(ct))
await channel.Writer.WriteAsync(job, ct); // waits when 500 are pending
channel.Writer.Complete();
await Task.WhenAll(consumers);
Mistake: Using List<T>.RemoveAt(0) as a queue.
Why it is wrong: Every removal shifts all remaining elements, so draining n items is O(n²).
Instead: Use Queue<T>, a circular buffer with O(1) dequeue.
Mistake: Sharing Stack<T> or Queue<T> across threads without locks.
Why it is wrong: Concurrent writes race on the index fields and internal array, so items are lost, duplicated or the collection throws.
Instead: Use ConcurrentQueue<T> or ConcurrentStack<T>, a Channel<T>, or one lock around every access.
Mistake: Polling a queue with Thread.Sleep or Task.Delay loops.
Why it is wrong: It wastes CPU while idle and adds up to one polling interval of latency to every item.
Instead: Use Channel<T> so consumers await new items with no polling.
Mistake: Using unbounded queues between fast producers and slow consumers. Why it is wrong: The backlog grows until memory runs out, and latency grows with it. Instead: Use bounded channels with a deliberate full mode (wait, drop oldest, drop newest) and alert on queue length.
Mistake: Writing deep recursion on unbounded input.
Why it is wrong: StackOverflowException cannot be caught and kills the whole process.
Instead: Use an explicit Stack<T> for deep or user-controlled depth.
Mistake: Using Count > 0 then Dequeue on a concurrent queue.
Why it is wrong: Another thread can take the item between the check and the call.
Instead: Use the atomic TryDequeue / TryPop methods.
Stacks and queues are simple, but they model ordering and flow control everywhere: call stacks, schedulers, message brokers and back-pressure. The senior angle is choosing the right flavour and deciding what happens when the queue is full.
| Decision | Options | How I choose |
|---|---|---|
| Scope | In-process (Channel<T>) or distributed (broker) |
Distributed when work must survive restarts or cross services |
| Capacity | Bounded or unbounded | Bounded by default, sized from throughput × acceptable delay |
| Full behaviour | Wait, drop oldest, drop newest, reject | Wait for must-process work; drop for telemetry or live updates |
| Waiting | Blocking or async | Async (ReadAllAsync) in ASP.NET Core and worker services |
| Ordering | FIFO, LIFO or priority | Priority when some work must jump the line; watch for starvation |
The .NET thread pool itself is a good example: a global FIFO queue plus per-thread local queues that the owner uses LIFO (warm cache) and other threads steal from FIFO. In .NET, Channel<T> is my default for in-process producer/consumer; for cross-service work, a durable broker with retries and dead-letter queues. And I keep the call stack in mind: recursion is a hidden stack with a small, fixed size.
A heap is a complete tree stored in an array that keeps the heap property: in a min-heap every parent ≤ its children, so the smallest item is always at the root.
.NET's PriorityQueue<TElement,TPriority> (.NET 6+) is an array-backed min-heap (4-ary internally). Enqueue, Dequeue, TryPeek, EnqueueDequeue; not stable for equal priorities; no decrease-key (Remove was added in .NET 9). For a max-heap, pass a reversed comparer.
Top K from a stream: keep a min-heap of size K; for each item, if it beats the heap's minimum, replace it. That is O(n log K) time and O(K) memory.
(Not to be confused with the managed heap, which is memory.)
Each thread has a fixed-size stack (about 1 MB on Windows), and every method call pushes a frame. Unbounded or very deep recursion exhausts it. Since .NET 2.0 the runtime terminates the process on a stack overflow instead of throwing a catchable exception, because with no stack left it can't safely run handlers or finally blocks. To diagnose it, I read the crash output (recent .NET versions print the repeating frames to standard error), check container logs or the Windows Event Log, and capture a crash dump with DOTNET_DbgEnableMiniDump=1 to inspect the stack. Typical causes are a missing base case, a property or ToString that calls itself, cycles in object graphs (serialisation, Equals), and deeply nested input. Fixes: correct the recursion, switch to iteration with an explicit stack, and add depth limits and tests.
An array is a fixed-size block of contiguous elements of one type. Element i lives at start + i × elementSize, so indexing is O(1) and iteration is very cache-friendly. Its size cannot change.
List<T> wraps an internal array plus a Count. When the array is full, Add allocates a new array about twice as large and copies the elements, so Add is amortised O(1) but occasionally O(n). Inserting or removing in the middle is O(n) because elements shift.
Use an array for fixed-size data and hot paths, List<T> when the size changes, set Capacity when you know the size, and Span<T>/Memory<T> to work on slices without copying.
Last updated 23 Oct 2026.