Module 7: Stack & Queue

Stacks and Queues are behavior-based data structures.
They are not about how data is stored, but how data is accessed.

Many complex problems become easy once you identify whether they follow:

• LIFO (Last In, First Out) → Stack
• FIFO (First In, First Out) → Queue

This module builds that instinct.

STACK

What is a Stack?

A stack follows Last In, First Out (LIFO) order.
Think of a stack of plates:

• You add plates on top
• You remove plates from the top

Basic Operations

• push → insert element
• pop → remove top element
• peek/top → view top element
• isEmpty

All operations run in O(1) time

Stack Implementation

Stack Using Array

class StackArray {
    int[] stack;
    int top;

    StackArray(int size){
        stack = new int[size];
        top = -1;
    }

    void push(int x){
        stack[++top] = x;
    }

    int pop(){
        return stack[top--];
    }
}

Limitations:

• Fixed size
• Overflow risk

Stack Using Linked List

class StackLL {
    Node top;

    void push(int x){
        Node node = new Node(x);
        node.next = top;
        top = node;
    }

    int pop(){
        int val = top.data;
        top = top.next;
        return val;
    }
}

Advantages:

• Dynamic size
• No overflow until memory is full

Expression Evaluation

Stacks are used to evaluate expressions because:

• Operators depend on previous operands
• Order matters

Postfix Expression Evaluation

Expression: 23*54*+9-

Steps:

• Push operands
• On operator, pop two values, apply operation, push result

Stack<Integer> st = new Stack<>();

for(char c : exp.toCharArray()){
    if(Character.isDigit(c))
        st.push(c - '0');
    else{
        int b = st.pop();
        int a = st.pop();
        st.push(apply(a, b, c));
    }
}

Infix, Postfix & Prefix Conversion

Expression Types

• Infix: A + B
• Postfix: AB+
• Prefix: +AB

Why Conversion?

Computers evaluate postfix/prefix easily without parentheses.

---

Infix to Postfix (Concept)

• Use operator stack
• Respect precedence
• Handle parentheses

while(!stack.isEmpty() && precedence(stack.peek()) >= precedence(curr)){
    result += stack.pop();
}

Used heavily in:

• Compilers
• Expression evaluators

Balanced Parentheses

Problem

Check if brackets are balanced.

Example:

• {[()]} → Valid
• {[(])} → Invalid

Approach

• Push opening brackets
• On closing bracket, pop and compare

Stack<Character> st = new Stack<>();
for(char c : s.toCharArray()){
    if(c=='('||c=='{'||c=='[')
        st.push(c);
    else{
        if(st.isEmpty()) return false;
        char top = st.pop();
        if(!match(top, c)) return false;
    }
}
return st.isEmpty();

Time: O(n)

Next Greater Element

Problem

For each element, find the next element greater than it on the right.

Example:
[4, 5, 2, 25] → [5, 25, 25, -1]

Approach

• Traverse from right
• Maintain decreasing stack

Stack<Integer> st = new Stack<>();
for(int i = n - 1; i >= 0; i--){
    while(!st.isEmpty() && st.peek() <= arr[i])
        st.pop();
    res[i] = st.isEmpty() ? -1 : st.peek();
    st.push(arr[i]);
}

Stock Span Problem

Problem

Find number of consecutive days before today with price ≤ today.

Approach

• Monotonic decreasing stack

for(int i = 0; i < n; i++){
    while(!st.isEmpty() && price[st.peek()] <= price[i])
        st.pop();
    span[i] = st.isEmpty() ? i + 1 : i - st.peek();
    st.push(i);
}

Classic interview problem.

Monotonic Stack

What is a Monotonic Stack?

A stack that maintains:

• Increasing order
• Or decreasing order

Used in:

• Next greater/smaller element
• Histogram area
• Sliding window problems

Key insight:

Stack stores useful candidates only

QUEUE

What is a Queue?

Queue follows First In, First Out (FIFO).

Example:

• People in a line
• Task scheduling

Basic operations:

• enqueue
• dequeue
• front

Simple Queue

Array Implementation

int[] q = new int[n];
int front = 0, rear = -1;

void enqueue(int x){
    q[++rear] = x;
}

Problem:

• Wasted space after dequeues

---

Circular Queue

Why Circular Queue?

Reuses freed space by wrapping around.

Concept:

• (rear + 1) % size

Used in:

• Buffers
• OS scheduling

Deque (Double Ended Queue)

What is Deque?

Insert and delete from both ends.

Operations:

• addFirst
• addLast
• removeFirst
• removeLast

Used in:

• Sliding window problems
• Palindrome checks

Priority Queue

What is Priority Queue?

Elements are removed based on priority, not order.

Internally implemented using heap.

Example:

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(10);
pq.add(5);
pq.poll();

Used in:

• Scheduling
• Dijkstra’s algorithm
• Top K problems

Queue Using Stacks

Idea

Use two stacks:

• One for input
• One for output

void enqueue(int x){
    in.push(x);
}

int dequeue(){
    if(out.isEmpty()){
        while(!in.isEmpty())
            out.push(in.pop());
    }
    return out.pop();
}

Amortized O(1)

Sliding Window Maximum

Problem

Find maximum in each window of size k.

Optimal Approach

• Use Deque
• Maintain decreasing order

Deque<Integer> dq = new ArrayDeque<>();

for(int i = 0; i < n; i++){
    while(!dq.isEmpty() && dq.peekFirst() <= i - k)
        dq.pollFirst();

    while(!dq.isEmpty() && arr[dq.peekLast()] <= arr[i])
        dq.pollLast();

    dq.addLast(i);

    if(i >= k - 1)
        result[i - k + 1] = arr[dq.peekFirst()];
}

Time: O(n)

BFS Introduction

What is BFS?

Breadth First Search explores nodes level by level.

Why Queue?

Queue maintains order of exploration.

Queue<Integer> q = new LinkedList<>();
q.add(start);

while(!q.isEmpty()){
    int node = q.poll();
    for(int neigh : graph[node]){
        q.add(neigh);
    }
}

Used in:

• Shortest path
• Graph traversal
• Level order traversal