Stacks and Queues Including Priority Queues For students.

A stack is a collection where you add and remove items from the same end, called the top — like a stack of plates, where you always take the top plate. This rule is LIFO: Last In, First Out. A queue is the opposite: items enter at the rear and leave from the front — like a ticket line. This rule is FIFO: First In, First Out.

These simple ideas power much of computing. The undo button uses a stack, the print spooler uses a queue, and your browser's page search uses both. Nearly every algorithm leans on one, which is why every programmer meets them in the first year.

Key Concepts

• push / pop / peek: add to the top, remove from the top, and look at the top of a stack without removing it.
• enqueue / dequeue: add at the rear and remove from the front of a queue.
• Overflow / underflow: pushing onto a full stack (or a full queue), and popping from an empty one.
• Circular queue: an array-based queue whose rear wraps to the start, reusing freed slots.
• Priority queue: each item has a priority, and the highest-priority item leaves first regardless of arrival order — usually built on a heap.
• Deque: a double-ended queue allowing insertion and removal at both ends.

Formulas

• Array stack: with top starting at −1, push does top = top + 1 then stack[top] = x; pop does x = stack[top] then top = top − 1.
• Circular queue wrap: rear = (rear + 1) mod n and front = (front + 1) mod n, where n is the capacity.
• Full vs empty: empty when a count variable is 0; full when (rear + 1) mod n = front (one slot sacrificed, or a counter kept, so the two states never look alike).
• Time costs: push, pop, enqueue, and dequeue are all O(1); priority-queue operations on a heap cost O(log n).
• Space: O(n) for n stored items in any of these structures.

Worked Example

Start with an empty stack and run: push(10), push(20), push(30), pop(), push(40), pop(), pop(). After the three pushes the stack is [10, 20, 30] with 30 on top. The first pop() returns 30, leaving [10, 20]. push(40) gives [10, 20, 40]. The next pop() returns 40, leaving [10, 20]. The last pop() returns 20, leaving [10]. The popped values are 30, 40, 20 — the reverse of push order, which is exactly LIFO. Contrast with a min-priority queue: enqueue(30), enqueue(10), enqueue(20) dequeues 10, then 20, then 30 — smallest first, like an emergency room treating the most critical patient first even if they arrived last.

Common Misconceptions

• "Stacks and queues are basically the same." Wrong. The single rule of which end items leave from changes everything they are good for.
• "Priority queues fully sort on insert." Wrong. A heap only guarantees the top-priority item at the root; the rest stay partially ordered, which keeps operations at O(log n).
• "Recursion uses a queue." Wrong. Function calls use the call stack — LIFO — which is why deep recursion causes a stack overflow, not a queue overflow.

Real-World Applications

• Stacks: undo/redo, browser back button, expression evaluation, the function call stack.
• Queues: printer spooling, ticket systems, breadth-first search.
• Circular queues: keyboard buffers, streaming audio/video buffers.
• Priority queues: hospital triage, OS process scheduling, Dijkstra's shortest path.

Stacks remember in reverse order of arrival, queues serve in arrival order, and priority queues serve by importance. Picture plates and ticket lines, and you will recognise these patterns everywhere — from the undo button to the algorithm routing your map directions.