[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.