================================================================================
         DATA STRUCTURES AND ALGORITHMS (C)
         PRACTICAL LAB SESSION 3: Stacks & Queues
         State University of Zanzibar (SUZA)
================================================================================

OBJECTIVES:
- Implement stack using arrays
- Apply stacks to expression evaluation and bracket matching
- Implement queue and circular queue using arrays
- Solve problems using stack and queue data structures

================================================================================
PART A: STACK BASICS
================================================================================

Stack Structure:
   #define MAX 100
   int stack[MAX], top = -1;

1. Stack Operations:
   Implement push, pop, peek, isEmpty, isFull, and display.
   void push(int value);
   int pop();
   int peek();
   void display();
   Test: push(10), push(20), push(30), pop() -> 30, peek() -> 20

2. Stack Using Struct:
   Implement a stack using a struct:
   struct Stack { int items[MAX]; int top; };
   void push(struct Stack *s, int value);
   int pop(struct Stack *s);

3. Reverse a String Using Stack:
   Read a string and reverse it using a character stack.
   void reverseString(char str[]);
   Test: "Hello" -> "olleH"

4. Decimal to Binary Using Stack:
   Convert decimal to binary using a stack.
   void decToBin(int n);
   Test: 13 -> 1101

5. Check Palindrome Using Stack:
   Push first half, compare with second half.
   int isPalindrome(char str[]);
   Test: "racecar" -> 1 (true)

================================================================================
PART B: STACK APPLICATIONS
================================================================================

6. Balanced Brackets:
   Check if expression has balanced brackets (){}[].
   int isBalanced(char expr[]);
   Test: "{[()]}" -> 1 (balanced)
   Test: "{[(])}" -> 0 (not balanced)

7. Infix to Postfix:
   Convert infix expression to postfix.
   void infixToPostfix(char infix[], char postfix[]);
   Test: "A+B*C" -> "ABC*+"
   Test: "(A+B)*C" -> "AB+C*"

8. Postfix Evaluation:
   Evaluate a postfix expression with single-digit operands.
   int evalPostfix(char expr[]);
   Test: "231*+9-" -> -4  (2+3*1-9)

9. Next Greater Element:
   For each element, find the next greater element to its right.
   void nextGreater(int arr[], int n, int result[]);
   Test: [4,5,2,25] -> [5,25,25,-1]

10. Stock Span Problem:
    Find stock span for each day (consecutive days price was <= today).
    void stockSpan(int price[], int n, int span[]);
    Test: [100,80,60,70,60,75,85] -> [1,1,1,2,1,4,6]

================================================================================
PART C: QUEUE BASICS
================================================================================

Queue Structure:
   int queue[MAX], front = -1, rear = -1;

11. Queue Operations:
    Implement enqueue, dequeue, peek, isEmpty, isFull, display.
    void enqueue(int value);
    int dequeue();
    void display();
    Test: enqueue(10), enqueue(20), enqueue(30), dequeue() -> 10

12. Circular Queue:
    Implement circular queue to avoid wasted space.
    void cEnqueue(int value);
    int cDequeue();
    Use: front = (front + 1) % MAX; rear = (rear + 1) % MAX;

13. Generate Binary Numbers 1 to N:
    Use a queue to generate binary numbers from 1 to N.
    void generateBinary(int n);
    Test: n=5 -> 1, 10, 11, 100, 101

14. Reverse a Queue:
    Reverse all elements in a queue using a stack.
    void reverseQueue();

15. Queue Using Two Stacks:
    Implement a queue using two stacks.
    struct QueueUsingStacks { int s1[MAX], s2[MAX]; int top1, top2; };
    void qEnqueue(struct QueueUsingStacks *q, int value);
    int qDequeue(struct QueueUsingStacks *q);

================================================================================
PART D: EXTRA PRACTICE (LeetCode / HackerRank Style)
================================================================================

16. [Easy] Valid Parentheses (LeetCode 20)
    Check if string of brackets (){}[] is valid.
    int isValid(char *s);
    Test: "()[]{}" -> 1 | "(]" -> 0 | "([)]" -> 0

17. [Easy] Implement Queue using Stacks (LeetCode 232)
    Implement queue operations using only two stacks.
    Test: push(1), push(2), peek() -> 1, pop() -> 1

18. [Medium] Min Stack (LeetCode 155)
    Design a stack that supports push, pop, top, getMin in O(1).
    Use auxiliary stack to track minimums.

19. [Medium] Next Greater Element I (LeetCode 496)
    Given two arrays, find next greater element for each element of arr1 in arr2.
    Test: nums1=[4,1,2] nums2=[1,3,4,2] -> [-1,3,-1]

20. [Medium] Evaluate Reverse Polish Notation (LeetCode 150)
    Evaluate postfix expression with multi-digit operands.
    Test: ["2","1","+","3","*"] -> 9

21. [Medium] Sliding Window Maximum (LeetCode 239)
    Find maximum in each sliding window of size k.
    void maxSlidingWindow(int arr[], int n, int k, int result[]);
    Test: [1,3,-1,-3,5,3,6,7] k=3 -> [3,3,5,5,6,7]

================================================================================