EN_CS_Stack_Queue

Q5: Stack and Queue

Question: Explain how stacks and queues work from the LIFO/FIFO perspective, and describe their time complexity and practical use cases.

Key Terms

Term	Description
Stack	LIFO (Last In First Out) — last-in, first-out data structure
Queue	FIFO (First In First Out) — first-in, first-out data structure
Push/Pop	Stack insert/delete operations
Enqueue/Dequeue	Queue insert/delete operations
Call Stack	Stack structure that stores function call information
Priority Queue	Priority-based queue (implemented with a Heap)

Stack — LIFO

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

Operations and Time Complexity

Operation	Description	Time Complexity
push(item)	Add to the top of the stack	O(1)
pop()	Remove and return the top element	O(1)
peek()	View the top element (without removing)	O(1)
isEmpty()	Check whether empty	O(1)

Use Cases

Use Case	Description
Function Call Stack	Manages each function frame as a stack during recursive calls
DFS (Depth-First Search)	Stores nodes to visit on a stack to explore the deepest path first
Bracket Validation	Push opening brackets, pop on a closing bracket to check the match
Undo/Redo	Manages operation history as a stack

Queue — FIFO

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

Operations and Time Complexity

Operation	Description	Time Complexity
enqueue(item)	Add to the rear of the queue	O(1)
dequeue()	Remove and return the front element	O(1)
peek()	View the front element (without removing)	O(1)
isEmpty()	Check whether empty	O(1)

Use Cases

Use Case	Description
BFS (Breadth-First Search)	Stores nodes to visit in a queue to explore in level order
Task Scheduling	OS process scheduler, printer spooler
Message Queue	Kafka, RabbitMQ — Producer/Consumer pattern
Event Processing	Task Queue of the JavaScript event loop

Stack vs Queue Comparison

Aspect	Stack	Queue
Principle	LIFO	FIFO
Insert Position	Top	Rear
Remove Position	Top	Front
Search Algorithm	DFS	BFS
Main Uses	Function calls, Undo, bracket validation	Scheduling, message queues, event processing

Priority Queue

Unlike a regular queue, items with higher priority are processed first. Implemented with a Heap data structure.

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

Uses: Dijkstra shortest path, task scheduling, event-driven systems

→ Back to List