Data Structures
Complete Study Guide

// Stack interface (ADT)
interface Stack {
    void push(int x);
    int  pop();
    int  peek();
    boolean isEmpty();
    boolean isFull();
}

// Array-based implementation
class ArrayStack implements Stack {
    int[] arr;
    int top, maxSize;

    ArrayStack(int size) {
        maxSize = size;
        arr = new int[maxSize];
        top = -1;  // -1 means empty
    }

    public boolean isEmpty() { return top == -1; }
    public boolean isFull()  { return top == maxSize - 1; }

    public void push(int x) {
        if (isFull())
            System.out.println("Stack Overflow!");
        else
            arr[++top] = x;
    }

    public int pop() {
        if (isEmpty()) {
            System.out.println("Stack Underflow!");
            return -1;
        }
        return arr[top--];
    }

    public int peek() {
        if (isEmpty()) return -1;
        return arr[top];
    }
}Java

• Expression conversion — Infix to Postfix/Prefix
• Expression evaluation — Evaluating Postfix expressions
• Function call stack — Recursion management
• Undo operation — In text editors
• Balanced parentheses checking
• Browser history — Back button

Key Formulae (Circular Queue)

• Enqueue: rear = (rear + 1) % maxSize
• Dequeue: front = (front + 1) % maxSize
• Empty: front == -1
• Full: (rear + 1) % maxSize == front

class CircularQueue {
    int[] arr;
    int front, rear, maxSize;

    CircularQueue(int size) {
        maxSize = size;
        arr = new int[maxSize];
        front = rear = -1;
    }

    boolean isEmpty() { return front == -1; }

    boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

    void enqueue(int x) {
        if (isFull()) { System.out.println("Queue Full!"); return; }
        if (isEmpty()) front = 0;
        rear = (rear + 1) % maxSize;
        arr[rear] = x;
    }

    int dequeue() {
        if (isEmpty()) { System.out.println("Queue Empty!"); return -1; }
        int val = arr[front];
        if (front == rear) front = rear = -1; // last element removed
        else front = (front + 1) % maxSize;
        return val;
    }
}Java

1. Scan expression left to right
2. If it's an operand, add to output
3. If it's a '(', push onto stack
4. If it's a ')', pop from stack to output until '(' is found; discard '('
5. If it's an operator: pop operators from stack with greater or equal precedence to output, then push current operator
6. At end, pop all remaining operators from stack to output

Convert: A + B * C - D

1. Reverse the infix expression
2. Swap '(' with ')' and vice versa in the reversed expression
3. Apply the Infix to Postfix algorithm on this modified expression
4. Reverse the resulting postfix expression to get prefix

Algorithm

1. Scan postfix expression left to right
2. If operand, push onto stack
3. If operator, pop two operands (b then a), compute a op b, push result
4. Final result is left on top of stack

Example: Evaluate 5 3 2 * + 1 -

Scan 5 → push 5     Stack: [5]
Scan 3 → push 3     Stack: [5,3]
Scan 2 → push 2     Stack: [5,3,2]
Scan * → pop 2,3 → 3*2=6, push 6   Stack: [5,6]
Scan + → pop 6,5 → 5+6=11, push 11 Stack: [11]
Scan 1 → push 1     Stack: [11,1]
Scan - → pop 1,11 → 11-1=10, push 10

Result: 10

Node Structure in Java

class Node {
    int data;
    Node next;

    Node(int d) {
        data = d;
        next = null;
    }
}Java

void reverse() {
    Node prev = null;
    Node curr = head;
    Node next = null;

    while (curr != null) {
        next = curr.next;   // save next
        curr.next = prev;   // reverse pointer
        prev = curr;        // move prev forward
        curr = next;        // move curr forward
    }
    head = prev;  // new head is old tail
}Java

boolean isEmpty() {
    return head == null;
}

void display() {
    Node t = head;
    while (t != null) {
        System.out.print(t.data+" → ");
        t = t.next;
    }
    System.out.println("null");
}

Extract Element at Position

int getElement(int pos) {
    Node temp = head;
    for (int i = 1; i < pos && temp != null; i++)
        temp = temp.next;
    return (temp != null) ? temp.data : -1;
}

Array vs Linked List Comparison

Balanced Binary Tree

1. Inorder Traversal — Left → Root → Right

Visit left subtree, then root, then right subtree.

void inorder(Node root) {
    if (root == null) return;
    inorder(root.left);    // Left
    System.out.print(root.data + " ");  // Root
    inorder(root.right);   // Right
}

2. Preorder Traversal — Root → Left → Right

Visit root first, then left subtree, then right subtree.

void preorder(Node root) {
    if (root == null) return;
    System.out.print(root.data + " ");  // Root
    preorder(root.left);   // Left
    preorder(root.right);  // Right
}

3. Postorder Traversal — Left → Right → Root

Visit left subtree, right subtree, then root last.

void postorder(Node root) {
    if (root == null) return;
    postorder(root.left);   // Left
    postorder(root.right);  // Right
    System.out.print(root.data + " ");  // Root
}

Memory Trick

• Max nodes at level l = 2^l (where root is level 0)
• Max nodes in tree of height h = 2^h+1 − 1
• Min height for n nodes = ⌊log₂n⌋
• In a full binary tree: leaves = internal nodes + 1
• A complete binary tree with n nodes has height = ⌊log₂n⌋

// Stack ADT defined as interface
interface StackADT {
    void    push(int x);
    int     pop();
    int     peek();
    boolean isEmpty();
    int     size();
}

// Implementation 1: using array
class ArrayStack implements StackADT {
    int[] arr = new int[100];
    int top = -1;

    public void push(int x) { arr[++top] = x; }
    public int  pop()       { return arr[top--]; }
    public int  peek()      { return arr[top]; }
    public boolean isEmpty() { return top == -1; }
    public int  size()      { return top + 1; }
}

// Implementation 2: using linked list node
class LinkedStack implements StackADT {
    private class Node {
        int data; Node next;
        Node(int d) { data = d; }
    }
    Node top = null;
    int count = 0;

    public void push(int x) {
        Node n = new Node(x);
        n.next = top; top = n; count++;
    }
    public int pop() {
        int v = top.data; top = top.next; count--; return v;
    }
    public int     peek()    { return top.data; }
    public boolean isEmpty() { return top == null; }
    public int     size()    { return count; }
}

// Usage with polymorphism
StackADT s1 = new ArrayStack();
StackADT s2 = new LinkedStack();
// Both can be used the same way!Java

• All methods in an interface are implicitly public and abstract
• A class uses implements keyword to implement an interface
• A class must override all methods of the interface
• One class can implement multiple interfaces
• Interface references can hold objects of implementing classes (polymorphism)
• Interfaces cannot be instantiated directly