[Adult Learning Log] Data Structures – Week 3 Review

○ Key Takeaways from Week 3

• Learned about stacks, related operations, practical uses, and implementation methods.
• Understood the difference between static and dynamic stack connections and their implementation.
• Practiced writing size() and print_stack() for a stack implemented using a linked list.
• Studied expression evaluation and conversion using stacks.
• Learned about multiple stacks implemented in one array.

---

○ Stack: Last-In First-Out (LIFO) Structure

• Think of a stack like a pile of plates: the last one added is the first to be removed.
• The top of the stack is called top.
• The bottom does not need to be accessed directly.

Abstract Data Type (ADT) for Stack

Common Operations:

1. init() – initialize the stack
2. push(a) – add element a to the top
3. pop() – remove and return the top element
4. is_empty() – return TRUE if empty, else FALSE
5. is_full() – return TRUE if full, else FALSE
6. peek() – return top element without removing it

• If push() is called on a full stack → Overflow Error
• If pop() or peek() is called on an empty stack → Underflow Error

Common Use Cases:

Undo actions, back button in browsers, parenthesis matching, calculators, maze solving, etc.

---

○ Dynamically Linked Stack

• Unlike array-based stacks, dynamic stacks using linked lists allocate memory using malloc() as needed.
• The top pointer dynamically moves with each operation.
• Memory-efficient and flexible but more complex to implement and slower.

Example Usage (C):

typedef int Element;
#include "LinkedStack.h"

void main() {
    int A[7] = {0, 1, 1, 2, 3, 5, 8};

    printf("Stack Test\nInput Data: ");
    for(int i = 0; i < 7; i++) {
        printf("%3d", A[i]);
        push(A[i]);
    }

    printf("\nOutput Data: ");
    while (!is_empty())
        printf("%3d", pop());

    printf("\n");
    destroy_stack();  // Free all dynamic nodes
}

---

○ Stack Size and Print (Linked List Version)

• In a linked stack, each node contains data and a link to the next.
• The top node is the most recently pushed.
• Must traverse the list to count or print.

size() Example:

top → A → B → C → D → NULL
Returns: 4 (O(4) time complexity)

print_stack():

• Traverse from top and print each node’s data.
• Prints in reverse order of input.

---

○ Expression Evaluation and Notation Conversion

• Three common forms: prefix, infix, postfix
  • Humans use infix, computers use postfix
  • a + b → infix, ab+ → postfix

Expression Handling via Stack:

• Infix → Postfix conversion then calculate
• Operators with higher precedence (*, /) should be output before lower ones (+, -)
• Left parenthesis always pushed (lowest priority)
• Right parenthesis triggers pop until left parenthesis is removed

---

○ Multiple Stacks in a Single Array

• Implementing two or more stacks in one array improves memory efficiency.
• Typically: Stack 1 grows from left, Stack 2 grows from right.