Stacks and Queues

Stacks and queues are the two simplest data structures after arrays, and they appear everywhere: undo history, browser back buttons, function calls, print jobs, breadth-first search. Both restrict where you may add and remove elements, and that restriction is exactly what makes them useful. In this lesson you will build both in Python and use them to solve a classic interview problem.

What You'll Learn

• LIFO vs FIFO: what stacks and queues guarantee
• How to implement a stack with a plain Python list
• Why queues need collections.deque instead of a list
• A classic stack interview problem: balanced brackets

Stacks: Last In, First Out

A stack is like a pile of plates: you add to the top and take from the top. The last item pushed is the first item popped (LIFO). A Python list is a perfect stack because append and pop both work on the end in O(1):

Stack operations and their costs:

• push (append): O(1)
• pop: O(1)
• peek (stack[-1]): O(1)
• is_empty (not stack): O(1)

Queues: First In, First Out

A queue is a line at a coffee shop: first come, first served (FIFO). You add at the back and remove from the front. Here a plain list fails you, because pop(0) shifts every element (O(n), as you saw last lesson). Python's answer is collections.deque, a double-ended queue with O(1) operations at both ends:

Rule of thumb: list for stacks, deque for queues. A deque also works as a stack, but a list is simpler when you only touch one end.

Classic Problem: Balanced Brackets

Given a string of brackets, is every opener closed in the right order? "([]{})" is balanced; "([)]" is not. This is the canonical stack problem: push every opener, and on each closer check that the most recent opener matches. Try it, then open the editor fullscreen and test your own inputs:

Walk through "([)]" by hand: push (, push [, then ) arrives but the top of the stack is [. Mismatch, not balanced. The stack remembers order, which is exactly what nested structures need.

Where You Will Meet Them

• Stacks: function call stacks (next lesson on recursion), undo/redo, depth-first search, expression evaluation
• Queues: breadth-first search (graphs lesson), task schedulers, rate limiters, print spoolers
• Deques: sliding-window problems, both of the above

Exercises

Key Takeaways

• Stacks are LIFO: push and pop at the same end, both O(1) with a Python list
• Queues are FIFO: use collections.deque so both ends are O(1)
• Never use list.pop(0) in a loop; that is an O(n^2) queue
• The balanced-brackets pattern (push openers, match on closers) solves a whole family of nesting problems
• Stacks power recursion and DFS; queues power BFS