Stacks and Queues
Stacks and Queues are linear data structures that differ primarily in how elements are added and removed. They are often implemented using Arrays or Linked Lists.
1. Stack (LIFO)
A Stack follows the Last In, First Out (LIFO) principle. The last element added is the first one to be removed.
- Analogy: A stack of plates. You put a new plate on top, and you take the top plate off first. You can't take a plate from the middle or bottom easily.
Operations
- Push: Add an element to the top.
- Pop: Remove the top element.
- Peek (Top): View the top element without removing it.
Use Cases
- Function Call Stack: Tracking function calls and local variables (recursion).
- Undo/Redo: Storing history of actions.
- Browser History: Back button functionality.
- Syntax Parsing: Checking for balanced parentheses
(( )).
2. Queue (FIFO)
A Queue follows the First In, First Out (FIFO) principle. The first element added is the first one to be removed.
- Analogy: A line of people waiting for a bus. The person who arrived first gets on the bus first.
Operations
- Enqueue: Add an element to the back (rear).
- Dequeue: Remove the element from the front.
- Peek (Front): View the front element without removing it.
Use Cases
- Task Scheduling: Printer queues, CPU task scheduling.
- Breadth-First Search (BFS): Exploring graph nodes layer by layer.
- Message Queues: Handling asynchronous data between services (RabbitMQ).
3. Implementation (Python)
Python lists can be used as stacks. For queues, collections.deque is more efficient.
# Stack Implementation
stack = []
stack.append(1) # Push
stack.append(2)
print(stack.pop()) # Pop -> 2
# Queue Implementation
from collections import deque
queue = deque()
queue.append(1) # Enqueue
queue.append(2)
print(queue.popleft()) # Dequeue -> 1programming/arrays-and-lists programming/arrays-vs-linked-lists programming/algorithms