Beginner LevelData Structures & Algorithms
What are Stack and Queue data structures and where are they used?
ā Interview Prompt: Explain Stack (LIFO) and Queue (FIFO) semantics, their core operations, time complexities, and real-world use cases.
Stack follows LIFO (Last-In, First-Out) ā the most recently added element is removed first.
Queue follows FIFO (First-In, First-Out) ā the oldest element is removed first.
Operations (both $O(1)$):
| Structure | Add | Remove | Peek |
|---|---|---|---|
| Stack | push | pop | peek/top |
| Queue | enqueue | dequeue | front |
Real-World Use Cases:
ā¢
Stack: Browser back/forward history, call stack (recursion), undo/redo, balanced parenthesis checking, DFS traversal.
ā¢
Queue: CPU/disk task scheduling, BFS traversal, print spoolers, request queues in web servers.
Code Implementation Example
typescript
// Stack using array
class Stack<T> {
private data: T[] = [];
push(val: T) { this.data.push(val); }
pop(): T | undefined { return this.data.pop(); }
peek(): T | undefined { return this.data[this.data.length - 1]; }
isEmpty(): boolean { return this.data.length === 0; }
}
// Queue using array (O(N) dequeue ā use doubly linked list for O(1))
class Queue<T> {
private data: T[] = [];
enqueue(val: T) { this.data.push(val); }
dequeue(): T | undefined { return this.data.shift(); }
front(): T | undefined { return this.data[0]; }
isEmpty(): boolean { return this.data.length === 0; }
}š”Stack (LIFO) and Queue (FIFO) implementations in TypeScript.
šÆ Interview Key Takeaway
Stacks model LIFO access (DFS, recursion); Queues model FIFO access (BFS, scheduling). Both offer O(1) push/pop/enqueue/dequeue with proper implementations.
#DSA#Stack#Queue#LIFO#FIFO#Beginner
Back to all Data Structures & Algorithms Questionsā