So far, every data structure you've seen lets you access elements freely - you can read, insert, or delete from anywhere.
But sometimes, restricting how you access data actually makes problems easier to solve.
Think of a text editor's undo feature. You press Ctrl+Z, and the most recent action is undone. It doesn't matter what you did 10 steps ago - you only care about the last thing. That's a stack.
Or think of a printer queue. Documents are printed in the order they were sent - first come, first served. That's a queue.
These restrictions aren't weaknesses. They're contracts that make the behavior predictable. When you see a problem that involves "most recent first" or "first come, first served," you know exactly which tool to reach for.
A stack is like a stack of plates. You add a plate to the top (push), and you take a plate from the top (pop). The plate at the bottom might stay there for a long time - you can't touch it without removing everything above it.
Three operations, all O(1):
Classic uses: undo/redo, parsing expressions, checking balanced brackets, backtracking in algorithms (we'll see this in the Recursion module).
push = new element added to the top; stack grows upward
pop = top element removed; stack shrinks from the top
cyan arrow = top pointer, green = push, red = pop
LIFO: the last element pushed is the first one popped
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]
// Check balanced parentheses - O(n), O(n) space
bool IsValid(string s) {
var stack = new Stack<char>();
var map = new Dictionary<char, char> {
[')'] = '(', [']'] = '[', ['}'] = '{'
};
foreach (char c in s) {
if (map.ContainsKey(c)) {
if (stack.Count == 0 || stack.Pop() != map[c]) return false;
} else {
stack.Push(c);
}
}
return stack.Count == 0;
}
// "()[]{}" → true, "(]" → falseA queue is like a line at a grocery store. The first person in line is the first person served. New people join at the back.
Three operations, all O(1):
Classic uses: task scheduling, buffering data streams, Breadth-First Search (we'll use this extensively in the Trees and Graphs modules).
enqueue = new element added at the rear; queue extends
dequeue = front element removed; queue shifts forward
green arrow = front pointer, cyan arrow = rear pointer
green = enqueue, red = dequeue
FIFO: the first element enqueued is the first one dequeued
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]
// Processing items in FIFO order
var q = new Queue<int>();
q.Enqueue(1);
q.Enqueue(2);
q.Enqueue(3);
while (q.Count > 0) {
int item = q.Dequeue();
Console.Write(item + " ");
}
// Output: 1 2 3A priority queue is like a queue, but instead of "first come, first served," it serves the highest priority item first - regardless of when it arrived.
This is implemented with a heap — a binary tree where the parent always has higher priority than its children. A heap supports:
Classic uses: "Top K" problems, task scheduling, merging K sorted lists, Dijkstra's algorithm for shortest paths.
// 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)
// Process tasks by priority
var tasks = new PriorityQueue<string, int>();
tasks.Enqueue("Write report", 3);
tasks.Enqueue("Fix critical bug", 1);
tasks.Enqueue("Review PR", 2);
while (tasks.Count > 0) {
string task = tasks.Dequeue();
Console.WriteLine($"Processing: {task}");
}
// Output: Fix critical bug, Review PR, Write report
// For max-heap, negate priorities or use a custom comparer
var maxHeap = new PriorityQueue<int, int>(
Comparer<int>.Create((a, b) => b.CompareTo(a))
);Stack (LIFO) - "most recent first"
Queue (FIFO) - "first come, first served"
Priority Queue (Heap) - "most important first"
Popping from an empty stack Always check that the stack isn't empty before popping. An empty pop is a runtime error in most languages.
Using a queue when you need a stack (or vice versa) LIFO vs FIFO: if you need "most recent first", it's a stack. If you need "first come, first served", it's a queue. Getting this wrong means your algorithm processes data in the wrong order.
TypeScript: shift() is O(n)
Using arr.shift() in JavaScript re-indexes the entire array. For large queues, use an index pointer, a proper queue implementation, or a deque.
Priority queue comparator confusion In a min-heap, the smallest element comes out first. In a max-heap, the largest. Double-check which default your language uses before writing logic around it.
Stack overflow with recursion Every recursive call uses stack space. For deep recursion (thousands of calls), consider an iterative approach with an explicit stack. We'll cover this trade-off more in the Recursion module.
Stacks and queues are your first encounter with restricted-access data structures. You're starting to see a theme: different structures make different trade-offs.
Now we get to one of the most mind-bending topics in computer science: Recursion & Backtracking.
Recursion is when a function calls itself. It sounds circular and useless at first, but it's actually the key to solving problems that have a naturally self-similar structure - like navigating nested folders, exploring game trees, or generating all possible combinations.
And yes - recursion uses a stack under the hood (the call stack). So you already know more about how it works than you think.
Next up: Recursion & Backtracking