Comparing Stack and Queue Patterns
1. Comparing Stack vs Monotonic Stack
| Aspect | Stack | Monotonic Stack |
|---|---|---|
| Definition | A Last-In-First-Out (LIFO) data structure | A stack where elements are maintained in a specific order (e.g., increasing or decreasing) |
| Operations | Push, Pop, Peek | Push, Pop, Maintain monotonic property |
| Use Cases | Function call management, undo operations, expression evaluation | Next Greater Element, Histogram problems, Sliding window maximum |
| Ordering | No specific order | Strictly increasing or decreasing |
Example: Next Greater Element using Stack
const nextGreaterElement = (nums) => {
const result = new Array(nums.length).fill(-1);
const stack = [];
for (let i = nums.length - 1; i >= 0; i--) {
while (stack.length && stack[stack.length - 1] <= nums[i]) {
stack.pop();
}
if (stack.length) {
result[i] = stack[stack.length - 1];
}
stack.push(nums[i]);
}
return result;
};
// Example usage:
console.log(nextGreaterElement([1, 2, 1, 3, 4])); // [2, 3, 3, 4, -1]
Example: Next Greater Element using Monotonic Stack
const nextGreaterElementMonotonic = (nums) => {
const result = new Array(nums.length).fill(-1);
const stack = [];
for (let i = 0; i < nums.length; i++) {
while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
const index = stack.pop();
result[index] = nums[i];
}
stack.push(i);
}
return result;
};
// Example usage:
console.log(nextGreaterElementMonotonic([1, 2, 1, 3, 4])); // [-1, 3, 3, 4, -1]
Key Differences Summary
- Stack: General-purpose LIFO structure; no ordering constraint.
- Monotonic Stack: Specialized stack with ordering property; useful for specific algorithmic problems.
- Use Cases: Stack for general operations; Monotonic Stack for problems like "Next Greater Element".
2. Comparing Queue vs Monotonic Queue
| Feature | Standard Queue | Monotonic Queue |
|---|---|---|
| Structure | Linear data structure (FIFO) | Specialized deque with monotonic property |
| Operations | Enqueue, Dequeue, Peek | Push, Pop, Front, Back |
| Ordering | No specific ordering | Maintains monotonic sequence (e.g., increasing or decreasing) |
| Use Case | Task scheduling, breadth-first search | Sliding window problems, finding maximum/minimum in a window |
| Efficiency | O(1) for enqueue/dequeue | O(1) amortized for push/pop |
Example: Standard Queue Usage
// Enqueue elements
const queue = [];
queue.push(1);
queue.push(2);
queue.push(3);
// Dequeue elements
const first = queue.shift(); // 1
const second = queue.shift(); // 2Example: Monotonic Queue for Sliding Window Maximum
// Maintains indices of array elements in decreasing order
const monotonicQueue = [];
function push(index) {
while (monotonicQueue.length && arr[monotonicQueue[monotonicQueue.length - 1]] <= arr[index]) {
monotonicQueue.pop();
}
monotonicQueue.push(index);
}
function getMax() {
return arr[monotonicQueue[0]];
}3. Comparing Recursion vs Iteration
| Aspect | Recursion | Iteration |
|---|---|---|
| Definition | A function calling itself to solve a problem | Using loops (for, while) to repeat operations |
| Memory Usage | Uses call stack; can lead to stack overflow | Uses constant space (O(1)) |
| Readability | Often more intuitive for tree/graph traversals | May require more code to implement |
| Performance | Slower due to function call overhead | Faster, no function call overhead |
| Base Case | Mandatory to prevent infinite recursion | Not applicable |
Example: Factorial Calculation
// Recursive approach
function factorialRecursive(n) {
if (n === 0) return 1;
return n * factorialRecursive(n - 1);
}
// Iterative approach
function factorialIterative(n) {
let result = 1;
for (let i = 1; i <= n; i++) {
result *= i;
}
return result;
}When to Use Which?
- Recursion: Natural fit for problems with self-similar subproblems (e.g., tree traversal, divide-and-conquer)
- Iteration: Better for performance-critical code or when stack depth is a concern
4. Comparing Recursive vs Iterative DFS
| Aspect | Recursive DFS | Iterative DFS |
|---|---|---|
| Implementation | Uses function call stack | Uses explicit stack data structure |
| Memory Usage | Higher due to call stack overhead | Lower, controlled by explicit stack |
| Stack Overflow Risk | High for deep graphs | Low, limited by stack size |
| Code Readability | More intuitive and concise | More verbose, requires manual stack management |
| Control Flow | Automatic backtracking | Manual control of traversal |
Example: Recursive DFS
function dfsRecursive(node, visited = new Set()) {
if (visited.has(node)) return;
visited.add(node);
console.log(node.value);
for (let neighbor of node.neighbors) {
dfsRecursive(neighbor, visited);
}
}Example: Iterative DFS
function dfsIterative(startNode) {
const visited = new Set();
const stack = [startNode];
while (stack.length > 0) {
const node = stack.pop();
if (visited.has(node)) continue;
visited.add(node);
console.log(node.value);
for (let i = node.neighbors.length - 1; i >= 0; i--) {
stack.push(node.neighbors[i]);
}
}
}When to Use Which
- Recursive DFS: Good for small to medium graphs where stack overflow is not a concern.
- Iterative DFS: Preferred for large graphs or when stack size is a constraint.
5. Evaluating Stack-Queue Pattern Selection
Stack vs Queue: When to Choose Which
- Stack is ideal when you need LIFO (Last In, First Out) behavior — e.g., function call management, undo operations, expression evaluation.
- Queue is ideal when you need FIFO (First In, First Out) behavior — e.g., task scheduling, breadth-first search, buffering.
| Pattern | Use Case | Key Characteristics | Best For |
|---|---|---|---|
| Stack | Reverse order processing | LIFO, push/pop operations | Undo/redo, expression parsing, recursion |
| Queue | Order preservation | FIFO, enqueue/dequeue operations | Task scheduling, breadth-first search, buffering |
Decision Workflow for Pattern Selection
- Identify the order of data processing needed (FIFO vs LIFO)
- Determine if the operation requires reverse or sequential handling
- Consider performance requirements (O(1) push/pop vs O(1) enqueue/dequeue)
- Choose Stack for reverse order, Queue for order preservation