Data Structure (IT-303) - Unit 1 Short Notes

UNIT 1: Fundamental Data Structures and Algorithms

1. Introduction to Data Structures

Data Structure is a systematic way to organize and store data to enable efficient access and modification.
Importance: Optimizes time/space complexity, forms basis for complex algorithms, and is essential for problem-solving.

Classification:

Abstract Data Type (ADT): A theoretical model defining data and operations without implementation details.
Examples:

• Stack: LIFO; operations: push, pop, peek.

• Queue: FIFO; operations: enqueue, dequeue.

• List: Ordered collection; operations: insert, delete, search.

Algorithm Characteristics:

1. Input: Zero or more inputs.

2. Output: At least one output.

3. Definiteness: Each step precisely defined.

4. Finiteness: Terminates after finite steps.

5. Effectiveness: Each step is basic and feasible.

Asymptotic Notations:

• Big O (Upper bound): $$\displaystyle f(n) = O(g(n)) $$ if $$\displaystyle \exists c, n_0 $$ such that $0 \leq f(n) \leq c \cdot g(n)$ for $$\displaystyle n \geq n_0 $$.

• Omega (Lower bound): $$\displaystyle f(n) = \Omega(g(n)) $$ if $$\displaystyle \exists c, n_0 $$ such that $0 \leq c \cdot g(n) \leq f(n)$ for $$\displaystyle n \geq n_0 $$.

• Theta (Tight bound): $$\displaystyle f(n) = \Theta(g(n)) $$ if $$\displaystyle f(n) = O(g(n)) $$ and $$\displaystyle f(n) = \Omega(g(n)) $$.

Examples:

• $$\displaystyle 3n^2 + 2n + 1 = O(n^2) $$

• $$\displaystyle 5n^3 = \Omega(n^2) $$

• $$\displaystyle 4n^2 + 6n = \Theta(n^2) $$

Time & Space Complexity:

• Time Complexity: Number of primitive operations as function of input size $n$.

• Space Complexity: Amount of memory used.

Solving Recurrences:

• Substitution Method: Guess solution, verify by induction.

• Master Theorem: For $$\displaystyle T(n) = aT(n/b) + f(n) $$:

  • If $$\displaystyle f(n) = O(n^{\log_b a - \epsilon}) $$, then $$\displaystyle T(n) = \Theta(n^{\log_b a}) $$.

  • If $$\displaystyle f(n) = \Theta(n^{\log_b a}) $$, then $$\displaystyle T(n) = \Theta(n^{\log_b a} \log n) $$.

  • If $$\displaystyle f(n) = \Omega(n^{\log_b a + \epsilon}) $$, then $$\displaystyle T(n) = \Theta(f(n)) $$.

[!TIP]

• In exams, always state the recurrence form before applying Master Theorem.

• For $$\displaystyle T(n)=2T(n/2)+n\log n $$, compare $$\displaystyle f(n)=n\log n $$ with $$\displaystyle n^{\log_2 2}=n $$. Since $f(n)$ is larger by a factor of $\log n$, use Case 3? Actually, $$\displaystyle f(n)=\Omega(n^{1+\epsilon}) $$? No, $\log n$ grows slower than $$\displaystyle n^\epsilon $$. So it’s Case 2? Wait, $$\displaystyle f(n)=\Theta(n^{\log_b a} \log^k n) $$ with $$\displaystyle k=1 $$, so $$\displaystyle T(n)=\Theta(n \log^2 n) $$. Box this.

2. Linear Data Structures

2.1 Arrays

• One-dimensional: Contiguous memory, index-based access $O(1)$.

• Multi-dimensional: Row-major (C, Java) vs Column-major (Fortran, MATLAB).

Address Calculation:

• Row-major: $$\displaystyle \text{Address}(A[i][j]) = \text{Base} + ((i \times \text{COLS}) + j) \times \text{size} $$

• Column-major: $$\displaystyle \text{Address}(A[i][j]) = \text{Base} + ((j \times \text{ROWS}) + i) \times \text{size} $$

Sparse Matrices: Matrices with mostly zeros.

• Triplet Representation: Store only non-zero elements as $(row, col, value)$.

• Upper/Lower Triangular: Store only elements above/below diagonal.

• Space-efficient: For $n \times n$ triangular matrix, store $$\displaystyle \frac{n(n+1)}{2} $$ elements.

• Address Formula (lower triangular, row-major):

$$ \text{Address}(A[i][j]) = \text{Base} + \left( \frac{i(i-1)}{2} + j \right) \times \text{size} \quad (j \leq i) $$

Operations & Limitations:

• Compaction: Shifting elements to remove gaps (costly, $O(n)$).

• Overflow: Insertion when array full.

• Underflow: Deletion from empty array.

2.2 Comparison of Arrays and Linked Lists

2.3 Linked Lists

Singly Linked List:

• Node: data + next pointer.

• Operations:

  • Insertion at head: new->next = head; head = new; $O(1)$.

  • Insertion after node p: new->next = p->next; p->next = new; $O(1)$ given p.

  • Deletion of node p (given previous prev): prev->next = p->next; free(p); $O(1)$.

  • Traversal: Start from head, follow next until NULL.

• Drawbacks: No backward traversal, extra memory for pointers, slower access.

Doubly Linked List:

• Node: prev + data + next.

• Search/Modify: Traverse from head/tail, $O(n)$.

• Insertion (after node p):

  
  new->next = p->next;
  
  new->prev = p;
  
  if (p->next) p->next->prev = new;
  
  p->next = new;
  
  

• Deletion (node p):

  
  p->prev->next = p->next;
  
  if (p->next) p->next->prev = p->prev;
  
  free(p);
  
  

Circular Linked List:

• Last node points to head.

• Insertion at head:

  
  if (head == NULL) { new->next = new; head = new; }
  
  else {
  
    new->next = head->next;
  
    head->next = new;
  
    swap(new->data, head->data); // if inserting before head
  
  }
  
  

• Deletion of head:

  
  if (head->next == head) { free(head); head = NULL; }
  
  else {
  
    p = head;
  
    while (p->next != head) p = p->next;
  
    p->next = head->next;
  
    free(head);
  
    head = p->next;
  
  }
  
  

• Application: Josephus problem — $n$ people in circle, eliminate every $k$-th until one remains.

Applications:

1. Polynomial Representation: Each node stores (coefficient, exponent); sorted by exponent.

2. Merging Sorted Lists: Merge two sorted linked lists in $O(n+m)$.

3. Finding Merging Point (intersecting lists):

   • Compute lengths $$\displaystyle L_1, L_2 $$.

   • Advance longer list by $$\displaystyle |L_1 - L_2| $$ nodes.

   • Traverse both together until nodes match.

   • Time: $O(n+m)$, Space: $O(1)$.

[!TIP]

• For merging point, ensure lists actually intersect (same tail node).

• In circular list deletion, careful with single node case.

3. Tree Data Structures

3.1 Binary Trees

Terminology:

• Node: Element.

• Root: Top node (no parent).

• Leaf: Node with no children.

• Internal Node: Non-leaf.

• Height: Longest path from root to leaf (edges).

• Depth: Path length from root to node.

• Level: Depth + 1 (root at level 1).

• Degree: Number of children.

• Order: Maximum children per node (binary = 2).

Properties:

• Max nodes at height $h$: $$\displaystyle 2^{h+1} - 1 $$.

  Proof: Levels 0 to $h$: sum $$\displaystyle 2^0 + 2^1 + ... + 2^h = 2^{h+1} - 1 $$.

• Min nodes at height $h$: $h+1$ (skewed tree).

• Relation: For $n$ nodes, height $$\displaystyle h \geq \lfloor \log_2 n \rfloor $$.

Traversals:

• Inorder (Left-Root-Right): Gives sorted order for BST.

• Preorder (Root-Left-Right): Used to copy tree.

• Postorder (Left-Right-Root): Used to delete tree.

• Level-order (BFS): Use queue.

Example (tree: root A, left B, right C, B has left D, right E):

• Inorder: D, B, E, A, C

• Preorder: A, B, D, E, C

• Postorder: D, E, B, C, A

• Level-order: A, B, C, D, E

Construction from Traversals:

• Given inorder and preorder: First element of preorder is root. Find root in inorder; left part is left subtree, right part is right subtree. Recurse.

• Given inorder and postorder: Last element of postorder is root. Split inorder, recurse.

3.2 Binary Search Trees (BST)

Definition: For any node, left subtree values < node value < right subtree values.

Operations:

• Search:

  
  while (current != NULL) {
  
    if (key == current->data) return current;
  
    else if (key < current->data) current = current->left;
  
    else current = current->right;
  
  }
  
  return NULL;
  
  

  Time: Average $O(\log n)$, worst $O(n)$ (skewed).

• Insertion:

  
  if (root == NULL) root = new Node(key);
  
  else {
  
    current = root;
  
    while (true) {
  
      if (key < current->data) {
  
        if (current->left == NULL) { current->left = new Node(key); break; }
  
        else current = current->left;
  
      } else {
  
        if (current->right == NULL) { current->right = new Node(key); break; }
  
        else current = current->right;
  
      }
  
    }
  
  }
  
  

• Deletion (three cases):

  1. Leaf: Simply remove.

  2. One child: Replace node with child.

  3. Two children: Find inorder successor (smallest in right subtree), copy its value to node, delete successor (which has at most one child).

Example: Insert [45, 26, 10, 60, 70, 30, 40] → BST.

Delete 10 (leaf), then 60 (one child: 70), then 45 (two children: successor 70? Actually after deleting 60, 70 becomes child of 45? Step-by-step required in exam).

3.3 Balanced Binary Search Trees

AVL Trees:

• Balance Factor (BF): $$\displaystyle BF = \text{height(left)} - \text{height(right)} $$. Must be -1, 0, or 1.

• Rotations (single):

  • LL (left-left): Right rotate at unbalanced node.

  • RR (right-right): Left rotate.

  • LR (left-right): Left rotate on left child, then right rotate on node.

  • RL (right-left): Right rotate on right child, then left rotate on node.

• Insertion: Insert as BST, update heights, check BF from bottom up, rotate if $$\displaystyle |BF|>1 $$.

• Deletion: Delete as BST, update heights, rebalance up to root.

Example: Insert 485, 575, 655, 745, 830, 910, 100, 110, 520, 130, 340, 450, 365, 525, 204, 155, 130, 35 (Jun 2024). Show rotations step-by-step.

Red-Black Trees:

• Properties:

  1. Every node is red or black.

  2. Root is black.

  3. All leaves (NIL) are black.

  4. Red node’s children are black.

  5. Every path from node to leaves has same black-height.

• Comparison: AVL more strictly balanced (better for search), Red-Black fewer rotations (better for frequent insertions/deletions).

B+ Trees:

• All leaves at same level, linked list at leaves.

• Internal nodes store keys for routing.

• Applications: Databases (indexing), file systems.

3.4 Expression Trees

• Construction: From infix (using stack for operators), prefix (scan right to left), postfix (scan left to right).

• Traversals:

  • Inorder: Infix (add parentheses).

  • Preorder: Prefix.

  • Postorder: Postfix.

Example: $(a + b \times c) + (d \times e + f \times g)$

Tree: root +, left subtree + (a, *(b,c)), right subtree + (*(d,e), *(f,g)).

Traversals:

• Inorder: (a + (b * c)) + ((d * e) + (f * g))

• Preorder: + + a * b c * * d e f g

• Postorder: a b c * + d e * f g * +

[!TIP]

• Inorder traversal of expression tree requires parentheses to preserve order.

• For construction from infix, use operator precedence and stack.

4. Graph Data Structures

4.1 Graph Fundamentals

• Vertices (V), Edges (E).

• Directed (digraph): Edges have direction.

• Undirected: Edges bidirectional.

• Weighted: Edges have weights.

• Connected: Path between every pair (undirected).

• Cyclic: Contains cycle.

Representations:

Example:

Matrix:

   V0 V1 V2 V3

V0  0  1  1  0

V1  0  0  1  1

V2  0  0  0  1

V3  1  0  0  0

Graph: V0→V1, V0→V2, V1→V2, V1→V3, V2→V3, V3→V0.

Graph vs Tree Traversal:

• Graph: May have cycles → need visited array.

• Multiple components: Loop over all vertices.

• Tree: No cycles, single component.

4.2 Graph Traversal Algorithms

Breadth-First Search (BFS):

• Algorithm:

  1. Mark start visited, enqueue.

  2. While queue not empty: dequeue u, for each neighbor v of u: if not visited, mark visited, enqueue v.

• Example: Graph above from V0:

  Queue: [V0] → dequeue V0, enqueue V1,V2 → [V1,V2] → dequeue V1, enqueue V3 → [V2,V3] → dequeue V2 (no new) → dequeue V3 (no new). Order: V0,V1,V2,V3.

• Applications: Shortest path in unweighted graphs, web crawling.

Depth-First Search (DFS):

• Algorithm (recursive):

  
  DFS(u):
  
    visited[u] = true;
  
    for each neighbor v of u:
  
      if (!visited[v]) DFS(v);
  
  

  Or iterative with stack.

• Example: Same graph from V0:

  Stack: [V0] → pop V0, push V1,V2 → [V1,V2] → pop V2, push V3 → [V1,V3] → pop V3, push V0 (visited) → [V1] → pop V1, push V2 (visited), V3 (visited). Order: V0,V2,V3,V1.

• Applications: Topological sort, cycle detection, connected components.

Comparison:

Valid DFS Sequences (Dec 2023 question): Given graph, check sequences by simulating stack and adjacency list order.

4.3 Spanning Trees and MST

• Spanning Tree: Subgraph connecting all vertices, no cycles, $V-1$ edges.

• Minimum Spanning Tree (MST): Spanning tree with minimum total edge weight.

Prim's Algorithm:

• Steps:

  1. Start with arbitrary vertex.

  2. Grow tree by adding minimum-weight edge connecting tree to outside vertex.

  3. Repeat until all vertices included.

• Example: Use adjacency matrix/list, update key array (min edge to tree).

• Time:

  • Matrix: $$\displaystyle O(V^2) $$.

  • Binary heap: $O(E \log V)$.

Kruskal's Algorithm:

• Steps:

  1. Sort all edges by weight.

  2. Initialize disjoint sets (union-find).

  3. For each edge in order: if endpoints in different sets, add edge, union sets.

• Time: $O(E \log E)$ (sorting dominates) = $O(E \log V)$.

Comparison:

• Prim's: Dense graphs ($$\displaystyle E \approx V^2 $$), $$\displaystyle O(V^2) $$ better than $O(E \log V)$.

• Kruskal's: Sparse graphs ($$\displaystyle E \ll V^2 $$), easy to parallelize.

4.4 Shortest Path Algorithms

Dijkstra's Algorithm (non-negative weights):

• Steps:

  1. dist[source]=0, others=∞.

  2. Set S = empty (vertices with final shortest path).

  3. While not all vertices in S:

     • Pick u not in S with min dist[u].

     • Add u to S.

     • For each neighbor v of u: if dist[u] + weight(u,v) < dist[v], update dist[v].

• Time: $$\displaystyle O(V^2) $$ (simple), $O(E \log V)$ with priority queue.

• Example: Step-by-step distance updates.

4.5 Connected Components

• Algorithm (undirected graph):

  
  count = 0;
  
  for each vertex v:
  
    if (!visited[v]) {
  
      count++;
  
      DFS(v) or BFS(v);
  
    }
  
  

• Time: $O(V + E)$.

5. Sorting Algorithms

5.1 Comparison-Based Sorts

Selection Sort:

• Algorithm:

  
  for i=0 to n-2:
  
    min = i;
  
    for j=i+1 to n-1:
  
      if (A[j] < A[min]) min = j;
  
    swap(A[i], A[min]);
  
  

• Example: [29,10,14,37,13] → pass1: min=10 at index1, swap with 29 → [10,29,14,37,13]...

• Complexity: Always $$\displaystyle O(n^2) $$ (comparisons: $$\displaystyle \frac{n(n-1)}{2} $$, swaps: $n-1$).

Insertion Sort:

• Algorithm:

  
  for i=1 to n-1:
  
    key = A[i];
  
    j = i-1;
  
    while (j>=0 && A[j] > key) {
  
      A[j+1] = A[j];
  
      j--;
  
    }
  
    A[j+1] = key;
  
  

• Example: [29,10,14,37,13] → i=1: key=10, shift 29 → [10,29,14,37,13]...

• Complexity:

  • Best: $O(n)$ (already sorted).

  • Worst: $$\displaystyle O(n^2) $$ (reverse sorted).

  • Adaptive, stable.

Merge Sort (Divide & Conquer):

• Recursive:

  
  mergeSort(A, l, r):
  
    if (l < r) {
  
      mid = (l+r)/2;
  
      mergeSort(A, l, mid);
  
      mergeSort(A, mid+1, r);
  
      merge(A, l, mid, r);
  
    }
  
  

  merge uses temporary array, $O(n)$.

• Iterative (bottom-up): Merge subarrays of size 1, then 2, etc.

• Complexity: All cases $O(n \log n)$, space $O(n)$.

• Example: [38,27,43,3,9,82,10] → split, merge step-by-step.

Quick Sort:

• Partition (Lomuto, pivot=last):

  
  partition(A, low, high):
  
    pivot = A[high];
  
    i = low-1;
  
    for j=low to high-1:
  
      if (A[j] <= pivot) {
  
        i++;
  
        swap(A[i], A[j]);
  
      }
  
    swap(A[i+1], A[high]);
  
    return i+1;
  
  

• Algorithm:

  
  quickSort(A, low, high):
  
    if (low < high) {
  
      pi = partition(A, low, high);
  
      quickSort(A, low, pi-1);
  
      quickSort(A, pi+1, high);
  
    }
  
  

• Example: [26,56,47,36,13,95,85,32] (pivot=32). Partition: elements ≤32 to left. Final pivot position? Show steps.

• Complexity:

  • Best/Average: $O(n \log n)$.

  • Worst: $$\displaystyle O(n^2) $$ (sorted input with bad pivot).

• Improvements: Random pivot, median-of-three.

Sorting Summary:

5.2 Internal vs External Sorting

• Internal: Data fits in main memory (all above).

• External: Data too large; use multi-way merge sort, replacement selection (create initial runs longer than memory).

5.3 Sorting in Practice

• Small $n$: Insertion sort (low overhead).

• General purpose: Quick sort (average fast, in-place).

• Stable required: Merge sort.

• Nearly sorted: Insertion/bubble sort.

• Worst-case guarantee: Merge sort or heap sort.

6. Searching Algorithms

6.1 Linear Search

• Algorithm: Scan array sequentially until key found or end.

• Complexity: $O(n)$ worst/average, $O(1)$ best (first element).

• Applications: Unsorted lists, small arrays.

6.2 Binary Search

• Precondition: Sorted array.

• Algorithm (iterative):

  
  low=0, high=n-1;
  
  while (low <= high) {
  
    mid = (low+high)/2;
  
    if (A[mid] == key) return mid;
  
    else if (A[mid] < key) low = mid+1;
  
    else high = mid-1;
  
  }
  
  return -1;
  
  

• Complexity: $O(\log n)$.

• Applications: Dictionary lookup, database indexing.

6.3 Fibonacci Search

• Technique: Use Fibonacci numbers to divide array. Mid = low + F_{k-2} where $$\displaystyle F_k $$ is largest Fibonacci ≤ n.

• Steps:

  1. Find smallest Fibonacci $\geq n$.

  2. Compare key with element at offset + F_{k-2}.

  3. If key smaller, search left subarray of size $$\displaystyle F_{k-2} $$.

  4. If key larger, search right subarray of size $$\displaystyle F_{k-3} $$, update offset.

• Comparison: Fewer comparisons than binary search in some cases (uses only addition/subtraction).

7. Hashing

7.1 Hash Tables

• Concept: Direct access via hash function $h(key)$ → index in table.

• Hash Functions:

  1. Division: $$\displaystyle h(key) = key \mod m $$ (m = table size, prime preferred).

  2. Mid-square: Square key, extract middle digits.

  3. Folding:

     • Shift-fold: Split key into parts, sum them.

     • Boundary-fold: Reverse alternate parts before sum.

• Properties: Uniform distribution, simple computation, minimize collisions.

7.2 Collision Resolution

• Collision: Two keys hash to same index.

• Separate Chaining:

  • Array of linked lists.

  • Insert: table[h(key)]->insert(key).

  • Example: Insert [32,50,700,140,76,85,46,92,70,73,101] with key mod 7:

    • 32 mod 7 = 4 → bucket4: 32

    • 50 mod 7 = 1 → bucket1: 50

    • 700 mod 7 = 0 → bucket0: 700

    • 140 mod 7 = 0 → bucket0: 700→140

    • ... continue.

• Open Addressing (all in array):

  • Linear probing: $$\displaystyle h_i(key) = (h(key) + i) \mod m $$.

  • Quadratic probing: $$\displaystyle h_i(key) = (h(key) + c_1 i + c_2 i^2) \mod m $$.

  • Double hashing: $$\displaystyle h_i(key) = (h_1(key) + i \cdot h_2(key)) \mod m $$.

7.3 Hash Table Implementation

Java HashMap:

• put(key, value): Compute hash, handle collisions (separate chaining with linked lists, treeify if list > 8 in JDK8).

• get(key): Compute hash, traverse chain.

• remove(key): Remove from chain.

C Implementation (separate chaining):

#define TABLE_SIZE 7

typedef struct Node {

  int key;

  struct Node* next;

} Node;

Node* table[TABLE_SIZE];

int hash(int key) { return key % TABLE_SIZE; }

void insert(int key) {

  int idx = hash(key);

  Node* new = malloc(sizeof(Node));

  new->key = key; new->next = table[idx];

  table[idx] = new;

}

7.4 Applications of Hashing

1. Compiler Symbol Table: Store variable names (keys) and attributes (type, scope). Fast lookup for compilation.

2. Database Indexing: Hash indexes for equality searches (e.g., WHERE id = 5).

3. Caches: Web cache (URL → content), CPU cache (memory addresses).

4. Deduplication: Hash files to find duplicates.

5. Password Storage: Store salted hashes (not plain passwords).

Detailed Example 1: Symbol Table:

• Compiler uses hash table to store identifiers.

• On encountering int x;, hash "x" → bucket, insert entry {name:"x", type:int, scope:current}.

• On x = 5;, hash "x" → find entry, check type compatibility.

Detailed Example 2: LRU Cache:

• Policy: Evict least recently used item when full.

• Implementation: Hash map (key → node) + doubly linked list (access order).

• Operations:

  • get(key): If exists, move node to head (most recent), return value.

  • put(key, value): If exists, update, move to head; else create node, add to head. If full, remove tail (least recent) from list and map.

• Time: $O(1)$ for both.

7.5 LRU Cache

• Data Structures:

  • Doubly linked list: Head = most recent, tail = least recent.

  • Hash map: key → pointer to list node.

• Algorithm:

  • get(key):

    
    if (map.contains(key)) {
    
      node = map[key];
    
      moveToHead(node); // remove from current position, add after head
    
      return node->value;
    
    }
    
    return -1;
    
    

  • put(key, value):

    
    if (map.contains(key)) {
    
      node = map[key];
    
      node->value = value;
    
      moveToHead(node);
    
    } else {
    
      node = new Node(key, value);
    
      map[key] = node;
    
      addToHead(node);
    
      if (size > capacity) {
    
        tail = removeTail();
    
        map.erase(tail->key);
    
        free(tail);
    
      }
    
    }
    
    

[!TIP]

• In separate chaining, load factor $$\displaystyle \alpha = n/m $$ (n=elements, m=buckets). High $\alpha$ → longer chains.

• For open addressing, table should not be too full ($$\displaystyle \alpha < 0.7 $$) to avoid clustering.

8. Advanced and Additional Topics

8.1 Priority Queues

• Definition: Queue where each element has priority; dequeue highest priority first.

• Operations: insert, deleteMax/deleteMin, peek.

• Implementation: Binary heap (array-based).

  • Heap property: Parent ≥ children (max-heap).

  • Insert: Add at end, heapify-up.

  • DeleteMax: Replace root with last element, heapify-down.

• Example: Insert [10,20,15,12,40,25,18] into max-heap, show array after each insert.

8.2 Hybrid Data Structures

Mixed Representation (Jun 2023, Dec 2023):

• Sequentially map $n$ data objects into array $[1,n]$.

• First $$\displaystyle n_1 $$ objects are stacks, rest are queues.

• Implementation:

  • Use array A[1..n].

  • For stacks: maintain top[i] for stack $i$ ($$\displaystyle 1 \leq i \leq n_1 $$).

  • For queues: maintain front[i], rear[i] for queue $i$ ($$\displaystyle n_1+1 \leq i \leq n $$).

• Algorithms:

  • add(obj, value):

    
    if (obj <= n1) { // stack
    
      if (top[obj] == capacity) overflow;
    
      top[obj]++;
    
      A[top[obj]] = value;
    
    } else { // queue
    
      if (rear[obj] == capacity) overflow;
    
      rear[obj]++;
    
      A[rear[obj]] = value;
    
      if (front[obj] == -1) front[obj] = rear[obj];
    
    }
    
    

  • delete(obj):

    
    if (obj <= n1) { // stack
    
      if (top[obj] == -1) underflow;
    
      value = A[top[obj]];
    
      top[obj]--;
    
    } else { // queue
    
      if (front[obj] == -1) underflow;
    
      value = A[front[obj]];
    
      front[obj]++;
    
      if (front[obj] > rear[obj]) front[obj]=rear[obj]=-1; // empty
    
    }
    
    

8.3 Recursion in Data Structures

• Role: Natural for tree traversals, DFS, merge sort, expression evaluation.

• Design: Base case + recursive case.

• Stack Usage: Each call pushes frame; can cause stack overflow for deep recursion (e.g., skewed tree).

8.4 Expression Conversion and Evaluation

Infix to Postfix (using stack):

• Algorithm:

  1. Initialize empty stack.

  2. Scan infix left to right:

     • Operand → output.

     • '(' → push.

     • ')' → pop and output until '('.

     • Operator: while stack top has higher/equal precedence (and not '('), pop to output; then push current.

  3. Pop all remaining operators.

• Precedence: ^ (right assoc) > *,/ > +,- (left assoc).

• Example: a+b*c → postfix: abc*+.

Postfix Evaluation:

• Algorithm:

  
  Initialize empty stack.
  
  For each token in postfix:
  
    If operand: push.
  
    If operator: pop two operands (b = pop(), a = pop()), compute a op b, push result.
  
  Result = pop();
  
  

• Example: 2 3 9 * + 2 3 ^ - 6 2 / +

  Steps:

  • Push 2,3,9 → stack [2,3,9]

  • *: pop 9,3 → 3*9=27, push → [2,27]

  • +: pop 27,2 → 2+27=29, push → [29]

  • Push 2,3 → [29,2,3]

  • ^: pop 3,2 → 2^3=8, push → [29,8]

  • -: pop 8,29 → 29-8=21, push → [21]

  • Push 6,2 → [21,6,2]

  • /: pop 2,6 → 6/2=3, push → [21,3]

  • +: pop 3,21 → 21+3=24 → result 24.

Prefix Conversion: Reverse infix, convert to postfix (adjust parentheses), reverse result.

[!TIP]

• In infix to postfix, for equal precedence, pop if left-associative (e.g., -), don't pop if right-associative (e.g., ^).

• Postfix evaluation: order of operands matters for non-commutative operators (subtraction, division).