Stacks vs Queues: When to Use Which

With both structures now built from scratch, this short chapter exists purely to crystallize the distinction between them before moving on. No new code beyond one quick reference to Python's standard library.

In a cafe's plate stack, you take the plate on top, which is the one that was put there last. In the queue for the till, the person served first is the one who arrived first. Same kind of collection, opposite rule about who comes out next. That one question is the whole chapter: of everything waiting, which do I want to handle next, the newest or the oldest?

• -The plate stack is a stack: last in, first out (LIFO).
• -The queue at the till is a queue: first in, first out (FIFO).

Add a, b and c in that order, then remove all three. A stack gives them back newest first, and a queue gives them back oldest first:

• -A browser-style back button, undo history, and matching parentheses all want a stack. The most recent action matters first.
• -A printer job queue, a customer support ticket line, and processing requests fairly in arrival order all want a queue.
• -Tracking in-progress function calls during recursion is a stack, whether or not it is managed by hand. This connects directly to the recursion module later in this tier.
• -Task scheduling and breadth-first search, covered in later tiers, both want a queue for the same fairness reason.

Sometimes neither newest nor oldest is the right rule. An emergency room does not treat patients in arrival order, and a task scheduler runs urgent jobs first. That is a priority queue, usually built on a heap: it always hands over the item with the highest priority. You will meet it again in Dijkstra's algorithm, which always expands the cheapest known node next.

Python's standard library already ships a structure that behaves correctly as either one: collections.deque, a doubly-linked list under the hood offering O(1) append and pop from both ends. Building a Stack and a Queue from scratch in this module was not busywork. Understanding why list.pop(0) is slow, and how a circular buffer avoids that cost, is exactly the reasoning that lets you evaluate any structure's complexity, including ones a language or library hands you ready-made, or the constrained sandbox environment in the Forge Algorithm Lab where a full standard library is not always available.

The trap to avoid is using a plain list as a queue. list.pop(0) removes the first item, and every other item then has to shift one place left, so popping from the front of a list of 100,000 items moves 99,999 of them. deque.popleft() removes from the front in O(1).