# Abstract Data Structures: Static and Dynamic ## Overview Abstract Data Structures (ADTs) are essential tools in computer science for organizing and managing data efficiently. This study note focuses on **static** and **dynamic** data structures, their features, and their implementation using stacks and queues. --- ## Static vs. Dynamic Data Structures ### Key Differences Static and dynamic data structures differ primarily in their ability to change size during program execution. #### **Static Data Structures** - **Definition**: Fixed size determined at creation; cannot change during execution. - **Memory Usage**: - May waste memory if the allocated size is too large. - May run out of space if the allocated size is too small. - **Common Use**: Often associated with **FOR loops**. - **Example**: Arrays used as static stacks or queues. #### **Dynamic Data Structures** - **Definition**: Can grow or shrink in size during execution. - **Memory Usage**: - Efficient memory allocation; only uses memory as needed. - **Common Use**: Often associated with **WHILE loops**. - **Example**: Linked lists, trees, hash tables. --- ## Static Data Structures: Stacks and Queues ### Static Stack (Array-Based) A **stack** is a Last-In-First-Out (LIFO) data structure where elements are added and removed from the **top**. #### **Operations** 1. **Initialization**: - Create a fixed-size array. - Initialize a variable `top` to track the stack's top position (e.g., `top = -1` for an empty stack). 2. **Push**: - Increment `top`. - Place the new element at the `top` index. 3. **Pop**: - Retrieve the element at the `top` index. - Decrement `top`. #### **Example** Initial stack: `[]` After `push(1)`: `[1]` After `push(2)`: `[1, 2]` After `push(3)`: `[1, 2, 3]` After `pop()`: `[1, 2]` After `pop()`: `[1]` --- ### Static Queue (Array-Based) A **queue** is a First-In-First-Out (FIFO) data structure where elements are added at the **rear** and removed from the **front**. #### **Operations** 1. **Initialization**: - Create a fixed-size array. - Initialize `front` and `rear` indices (e.g., `front = 0`, `rear = 0` for an empty queue). 2. **Enqueue**: - Increment `rear`. - Place the new element at the `rear` index. 3. **Dequeue**: - Retrieve the element at the `front` index. - Increment `front`. #### **Example** Initial queue: `[]` After `enqueue(1)`: `[1]` After `enqueue(2)`: `[1, 2]` After `dequeue()`: `[2]` After `enqueue(3)`: `[2, 3]` --- ## Dynamic Data Structures: Features and Examples ### Features of Dynamic Data Structures 1. **Dynamic Size**: - Can grow or shrink as needed. - Automatically adjusts size based on the number of elements. 2. **Memory Management**: - Uses dynamic memory allocation (e.g., heap memory). - Allocates or deallocates memory as elements are added or removed. 3. **Efficient Memory Usage**: - Avoids wasting memory by allocating only what is needed. ### Common Dynamic Data Structures - **ArrayList** (Java) - **std::vector** (C++) - **Linked Lists**: - Singly linked list - Doubly linked list - **Trees**: - Binary search tree - **Hash Tables** - **Graphs** Dynamic data structures are ideal for scenarios where the size of the data structure is unpredictable or frequently changes. --- ## Advantages and Limitations of Static vs. Dynamic Queues ### Static Queue #### **Advantages**: - **Simplicity**: Easy to implement; no dynamic resizing required. - **Predictable Memory Usage**: Fixed size ensures consistent memory allocation. #### **Limitations**: - **Fixed Size**: Cannot grow beyond its initial capacity, leading to overflow risks. - **Wasteful Memory Usage**: If the size is set too high, unused memory is wasted. #### **Example Use Case**: A static queue might be preferred in embedded systems where memory constraints are strict and predictable behavior is required. --- ### Dynamic Queue #### **Advantages**: - **Flexible Size**: Can grow or shrink as needed, avoiding overflow or wasted memory. - **Efficient Memory Usage**: Allocates memory only when necessary. #### **Limitations**: - **Complexity**: Requires dynamic memory management, which can introduce overhead. - **Unpredictable Memory Usage**: May lead to fragmentation in some cases. #### **Example Use Case**: A dynamic queue is ideal for applications like task scheduling in operating systems, where the number of tasks varies over time. --- ## Practice Questions ### **Question 1** Explain the concept of a static Abstract Data Type (ADT) using an array-based stack as an example. Describe how the push and pop operations work in this ADT. Provide an example demonstrating the push and pop operations on a stack with an initial capacity of 5 elements. Focus on the fixed size of the stack and the mechanics of push/pop operations. --- ### **Question 2** Discuss the advantages and limitations of using a static array-based queue compared to a dynamic array-based queue. Provide examples of scenarios where a static queue might be preferred over a dynamic one. Highlight the trade-offs between simplicity and flexibility. --- ## Key Takeaways - **Static Data Structures**: Fixed size; simple but inflexible. - **Dynamic Data Structures**: Flexible size; efficient but complex. - **Stacks**: LIFO structure; operations on the top. - **Queues**: FIFO structure; operations on the front and rear. - **Choosing Between Static and Dynamic**: Depends on the application's memory constraints and size predictability. Many students confuse the dynamic resizing of a data structure with its ability to store dynamic data types. These are separate concepts!