Stacks and Queues
A stack and a queue are linear data structures that control how elements are added and removed. Unlike arrays or linked lists, which allow flexible access, stacks and queues enforce strict access rules, making them ideal for managing ordered workflows and execution sequences.
Stacks and queues are widely used in areas such as function calls, expression evaluation, scheduling systems, buffering, and graph algorithms.
What Are Stacks and Queues?
Both stacks and queues store elements in a linear sequence, but they differ in how elements are accessed and removed.
Stack
A stack follows the Last In, First Out (LIFO) principle.
Push → [1] → [2] → [3]
↑
Top
Pop ← [1] → [2]
The last element pushed onto the stack is the first one removed.
Stack Operations
A stack typically supports:
- Push - add an element to the top
- Pop - remove the top element
- Peek / Top - view the top element without removing it
- IsEmpty - check if the stack is empty
Real-World Examples of Stacks
- Function call stack
- Undo / redo operations
- Expression evaluation
- Backtracking algorithms (DFS)
Queue
A queue follows the First In, First Out (FIFO) principle.
Enqueue → [1] → [2] → [3] → Dequeue
↑ ↑
Front Rear
The first element added is the first one removed.
Queue Operations
A queue typically supports:
- Enqueue - add an element to the rear
- Dequeue - remove an element from the front
- Front / Peek - view the front element
- IsEmpty - check if the queue is empty
Real-World Examples of Queues
- Task scheduling
- Print queues
- Breadth-First Search (BFS)
- Message buffering
Stack vs Queue
| Aspect | Stack | Queue |
|---|---|---|
| Access rule | LIFO | FIFO |
| Insert | Push (top) | Enqueue (rear) |
| Remove | Pop (top) | Dequeue (front) |
| Typical use | Backtracking | Scheduling |
Implementation Options
Stacks and queues can be implemented using:
| Structure | Stack | Queue |
|---|---|---|
| Array / Vec | ✅ | ✅ |
| Linked List | ✅ | ✅ |
| Deque | ❌ | ✅ (efficient) |
Rust’s standard library provides efficient building blocks, but implementing them manually helps understand the underlying mechanics.
Why Stacks & Queues Matter
Stacks and queues are foundational because:
- They model real execution flows
- They simplify complex algorithms
- They are building blocks for trees, graphs, and parsers
- Many algorithms are naturally expressed using them
Understanding these structures makes later topics like DFS, BFS, and recursion much clearer.