Stacks and Queues

Stacks and queues are two of the simplest data structures, but they show up everywhere. They differ only in which end you remove from — and that one decision changes the entire behavior.

Stacks: Last In, First Out (LIFO)

A stack works like a stack of plates. You add to the top, and you remove from the top. The last item pushed is the first one popped.

The two core operations are:

• push — add an item to the top
• pop — remove and return the top item

Stacks power the call stack that tracks function calls in your program, the undo button in editors, back navigation in browsers, and matching brackets in parsers.

Queues: First In, First Out (FIFO)

A queue works like a line at a coffee shop. You join at the back, and you're served from the front. The first one in is the first one out.

The two core operations are:

• enqueue — add an item to the back
• dequeue — remove and return the front item

Queues power print job scheduling, breadth-first search in graphs, task queues in servers, and any "fair" first-come-first-served system.

Why the Distinction Matters

When you choose a structure, you're really choosing a policy for the order things get processed. LIFO handles "most recent first" (good for backtracking and reverse operations). FIFO handles "oldest first" (good for fairness and level-by-level processing).

Both run their core operations in O(1) time when implemented well — adding and removing from one end is always cheap.

Try It Yourself

• Use a stack to reverse a string by pushing each character then popping them off
• Use a queue to simulate a printer processing 5 jobs in arrival order
• Write a function that uses a stack to check if parentheses in a string are balanced