Core Order Structures
Some of the most useful data structures are deliberately restricted, allowing additions and removals only at specific ends. This exact restriction is what makes them powerful.
A stack is a last-in, first-out (LIFO) structure. You push elements onto the top, pop the top element off, and peek to view it without removal. The last item added is always the first one popped, acting just like a physical stack of plates.
A queue is a first-in, first-out (FIFO) structure. You enqueue at the back and dequeue from the front. The first element added is the first one removed, modeling any standard service line.
| Structure | Order | Add Operation | Remove Operation |
|---|---|---|---|
| Stack | LIFO | push (top) | pop (top) |
| Queue | FIFO | enqueue (back) | dequeue (front) |
Both are Abstract Data Types implemented via arrays or linked lists. When well-implemented, all core operations run in time.
Variants and Pitfalls
A common variant is the deque (double-ended queue), which allows adding and removing elements at both ends. This effectively generalizes both stacks and queues into a single flexible structure.
Applications are distinct and widespread:
- Stack uses: call stack for function tracking, undo/redo histories, bracket matching, and expression evaluation.
- Queue uses: print jobs, task scheduling, and breadth-first graph traversal.
Common pitfall: Mixing up LIFO and FIFO. A stack always returns the most recently added element, while a queue always returns the oldest. Never expect a queue to act like a stack.