EN_CS_Stack_Queue - somaz94/DevOps-Engineer GitHub Wiki

Q6: Stack and Queue

Question: Explain how stacks and queues work from a LIFO/FIFO perspective. Cover time complexity and practical use cases.


Key Terms

Term Description
Stack LIFO (Last In First Out) data structure
Queue FIFO (First In First Out) data structure
Push / Pop Stack insert / delete operations
Enqueue / Dequeue Queue insert / delete operations
Call Stack Stack tracking function call frames
Priority Queue Queue ordered by priority (implemented with a Heap)

Stack — LIFO

┌─────────┐
│   TOP   │  ← Push / Pop
├─────────┤
│    5    │  (last inserted, first removed)
├─────────┤
│    3    │
├─────────┤
│    2    │  (first inserted, last removed)
└─────────┘
  BOTTOM

Operations & Time Complexity

Operation Description Time
push(item) Add to top O(1)
pop() Remove and return top O(1)
peek() View top without removing O(1)
isEmpty() Check if empty O(1)

Use Cases

Use Case Description
Call Stack Manages function frames during recursion
DFS Stores nodes to visit; explores deepest path first
Bracket Validation Push open brackets, pop and match on close
Undo / Redo History managed as a stack

Queue — FIFO

Front                                Rear
  ↓                                    ↓
┌─────┐ → ┌─────┐ → ┌─────┐ → ┌─────┐
│  2  │   │  7  │   │  3  │   │  5  │
└─────┘   └─────┘   └─────┘   └─────┘
Dequeue                           Enqueue

Operations & Time Complexity

Operation Description Time
enqueue(item) Add to rear O(1)
dequeue() Remove and return front O(1)
peek() View front without removing O(1)
isEmpty() Check if empty O(1)

Use Cases

Use Case Description
BFS Stores nodes to visit; explores level by level
Task Scheduling OS process scheduler, printer spooler
Message Queue Kafka, RabbitMQ — Producer/Consumer pattern
Event Loop JavaScript async task processing

Stack vs Queue Comparison

Aspect Stack Queue
Principle LIFO FIFO
Insert Position Top Rear
Remove Position Top Front
Search Algorithm DFS BFS
Key Use Cases Call stack, Undo, Bracket check Scheduling, Message queue, Events

Priority Queue

Items are processed by priority, not insertion order. Implemented with a Heap.

Operation Time
enqueue O(log n)
dequeue O(log n)
peek O(1)

Use Cases: Dijkstra's algorithm, task scheduling, event-driven systems


Reference

⚠️ **GitHub.com Fallback** ⚠️