DSA: Stack and Queue

Arrays let you access _any index at any time_.

Stacks and queues intentionally limit how data is accessed to model real-world processes:

• Function calls
• Undo / redo
• Task scheduling
• Message processing
• Algorithms like DFS, BFS, parsing, and backtracking

In DSA terms:

**They trade flexibility for safety, predictability, and performance guarantees.**

Stack (LIFO – Last In, First Out)

A stack allows access from one end only: the top.

Core Operations

• push → add element to top
• pop → remove top element
• top / peek → read top without removing
• isEmpty

Mental Model

Think of a **stack of plates** , You can only take the **top plate**.

Top
 ┌───────┐
 │  30   │  ← pushed last
 ├───────┤
 │  20   │
 ├───────┤
 │  10   │
 └───────┘
Bottom

Example Flow

push(10)
push(20)
push(30)

pop() → 30
pop() → 20

Implementation Options

• Array-based stack
• Dynamic array (vector)
• Linked list

Most modern stacks are built on **dynamic arrays** for cache efficiency.

Why Stack Exists (When to Use It)

Stacks are perfect when:

• Order must be reversed
• You need nested context
• The most recent item must be handled first

Real Uses

• Function call stack
• Undo / redo in editors
• Expression evaluation
• Syntax parsing (parentheses matching)
• Depth-First Search (DFS)

Queue (FIFO – First In, First Out)

A queue processes data in the same order it arrives.

Core Operations

• enqueue → add at rear
• dequeue → remove from front
• front
• isEmpty

Mental Model

Think of a **line at the supermarket**

Front                 Rear
 ┌───────┬───────┬───────┐
 │  10   │  20   │  30   │
 └───────┴───────┴───────┘

dequeue() → 10

Key Property

**Fairness** — no one jumps the line.

Why Queue Exists (When to Use It)

Queues are ideal when:

• Order of arrival matters
• Tasks must be processed sequentially
• You want fairness

Real Uses

• Task scheduling
• Buffers (I/O, networking)
• Breadth-First Search (BFS)
• Message queues
• Producer–consumer systems

Circular Queue (Fixing a Big Problem)

The Problem

Using a normal array-based queue causes wasted space after dequeues.

[ _ _ _ 20 30 ]

The Solution → Circular Queue

• Wrap indices using modulo
• Reuse freed space

      ┌───────────┐
      ↓           │
[ 10 ][ 20 ][ 30 ][ _ ][ _ ]
  ↑                 ↓
 rear              front

Deque (Double-Ended Queue)

A deque allows insertion and removal from both ends.

Operations

• push_front
• push_back
• pop_front
• pop_back

Front ↔ [ 10 ][ 20 ][ 30 ] ↔ Rear

Why Deque Exists

• Combines stack + queue behavior

• Used in:
• Sliding window algorithms
• Caches (LRU)
• Task schedulers

Priority Queue (Order by Importance)

A priority queue removes elements based on priority, not insertion order.

Example

(priority, value)
(1, "critical")
(3, "low")
(2, "medium")

dequeue() → "critical"

Implementation

• Usually implemented using a heap
• Not a FIFO structure

Used In

• CPU scheduling
• Dijkstra’s algorithm
• Event simulation
• Real-time systems

Stack vs Queue (Clear Comparison)

Time Complexity Summary