A stack follows Last In, First Out. Think of a stack of plates — you add and remove from the top.
| Operation | Stack |
|---|---|
| Push | O(1) |
| Pop | O(1) |
| Peek | O(1) |
Uses: Undo/redo, backtracking, expression evaluation, DFS (implicitly via recursion).
var stack = new Stack<int>();
stack.Push(1); // [1]
stack.Push(2); // [1, 2]
stack.Push(3); // [1, 2, 3]
int top = stack.Peek(); // 3 (no removal)
int popped = stack.Pop(); // 3, stack is now [1, 2]
// Monotonic stack pattern — maintain increasing/decreasing order
int[] NextGreaterElement(int[] arr) {
var result = new int[arr.Length];
Array.Fill(result, -1);
var monoStack = new Stack<int>(); // stores indices
for (int i = 0; i < arr.Length; i++) {
while (monoStack.Count > 0 && arr[i] > arr[monoStack.Peek()]) {
int idx = monoStack.Pop();
result[idx] = arr[i];
}
monoStack.Push(i);
}
return result;
}
// For [2, 1, 3], returns [3, 3, -1]A queue follows First In, First Out. Think of a line at a store.
| Operation | Queue |
|---|---|
| Enqueue | O(1) |
| Dequeue | O(1) |
| Peek | O(1) |
Uses: BFS, task scheduling, buffering, sliding window.
var queue = new Queue<int>();
queue.Enqueue(1); // [1]
queue.Enqueue(2); // [1, 2]
queue.Enqueue(3); // [1, 2, 3]
int front = queue.Peek(); // 1 (no removal)
int dequeued = queue.Dequeue(); // 1, queue is now [2, 3]
// BFS template using Queue
void Bfs(TreeNode root) {
var q = new Queue<TreeNode>();
q.Enqueue(root);
while (q.Count > 0) {
int levelSize = q.Count;
for (int i = 0; i < levelSize; i++) {
var node = q.Dequeue();
Console.Write(node.val + " ");
if (node.left != null) q.Enqueue(node.left);
if (node.right != null) q.Enqueue(node.right);
}
Console.WriteLine(); // new level
}
}A priority queue dequeues elements by priority, not insertion order.
| Operation | Priority Queue |
|---|---|
| Enqueue | O(log n) |
| Dequeue | O(log n) |
| Peek | O(1) |
Uses: Dijkstra's algorithm, Huffman coding, K smallest/largest elements.
// Min-heap by default (lower priority = dequeued first)
var pq = new PriorityQueue<string, int>();
pq.Enqueue("low", 3);
pq.Enqueue("high", 1);
pq.Enqueue("medium", 2);
string next = pq.Dequeue(); // "high" (priority 1)
// For max-heap, negate priorities or use a custom comparer
var maxHeap = new PriorityQueue<int, int>(
Comparer<int>.Create((a, b) => b.CompareTo(a))
);
// Top K frequent elements pattern
int[] TopKFrequent(int[] nums, int k) {
var counts = new Dictionary<int, int>();
foreach (var n in nums) counts[n] = counts.GetValueOrDefault(n) + 1;
var heap = new PriorityQueue<int, int>();
foreach (var kvp in counts) {
heap.Enqueue(kvp.Key, kvp.Value);
if (heap.Count > k) heap.Dequeue(); // keep only top K
}
var result = new int[k];
for (int i = 0; i < k; i++) result[i] = heap.Dequeue();
return result;
}