MODULE 2 — ARRAYS, STACKS, QUEUES & SEARCHING (CST201)
1. ARRAYS 4. EXPRESSION NOTATIONS
• Set of (index, value) pairs. Ops: CREATE, RETRIEVE, STORE • Infix: A+B Prefix: +AB Postfix: AB+
• Address = α + (i − L) [1-D array, α=base addr, L=lower bound]
• Total elements = U − L + 1 Infix → Postfix (Stack Rules)
•Operand → output directly
2-D Arrays •'(' → push onto stack
• Row Major: addr = α + (i−L₁)×n + (j−L₂) [n = #cols] •')' → pop & output till '(' (discard both)
• Col Major: addr = α + (i−L₁) + (j−L₂)×m [m = #rows] •Operator → pop & output while stack top has
Ex: A[5:7,2:4], find A(6,3), α=10 → 10+(6-5)*3+(3-2)=14 - ≥ priority, then push current operator
• End: pop & output everything remaining
Polynomial Representation • Priority: *,/ (high) > +,- (low)
• Method 1: coeff array, index = exponent (fixed size) Ex: A*(B+C)*D → ABC+*D*
• Method 2: array size = highest degree → wastes space Ex: P*(Q+R)/S → PQR+*S/ (common exam Q)
• Method 3: store (coeff,exp) pairs + pointers af,al / bf,bl
• Last term: el = ef + (n−1) Postfix Evaluation
• Scan L→R: operand→push; operator→pop 2, compute, push
3. STACK (LIFO) result
• Insert=PUSH, Delete=POP — both at TOP • Time Complexity = O(n)
PUSH: if(top==n) full; else top++; stack[top]=item Ex: 2 3*8 2/2*+6 2*-4+ → result = 6 (work bottom-up)
POP : if(top==0) empty; else item=stack[top]; top--
• Applications: function calls, expr eval, undo, recursion, 5. QUEUE (FIFO)
- number conversion, expr conversion, string reversal • Insert=enqueue (rear), Delete=dequeue (front)
• Empty: front==rear | Full: rear==n
• Length = rear − front
Circular Queue
• rear=(rear+1) mod n; if front==rear→full else insert
• front=(front+1) mod n; dequeue → solves wasted-space issue of
linear queue
• Priority Queue: higher priority served first;
- equal priority → FIFO order (array or linked list)
6. SEARCHING
• Linear Search: Best O(1), Worst O(n), Avg = (n+1)/2
• Binary Search: needs SORTED array
• mid = (L+U)/2; compare, discard half each time
• TC = O(log₂ n) — Best case O(1)
Matrix Multiplication
• Valid only if cols(A) = rows(B), i.e. n = p
• TC = O(m·n·q)
⭐ Exam favorites: Infix→Postfix conversion (P*(Q+R)/S type), Circular Queue insert/delete algorithms, Sparse matrix/polynomial via arrays, Binary search TC
derivation (O(log n))