Comprehensive Study Guide: Linear Data Structures, Dynamic Memory, Linked Lists, Stacks, and Queues

Fundamentals of Linear Data Structures: Arrays

• Definition of an Array:

  • An array is a linear data structure consisting of a collection of elements of the same data type stored in contiguous (consecutive) memory locations.
  • Individual elements are accessed directly using a zero-based numerical index.
  • Syntax for declaration in C++: dataType arrayName[size]; where dataType specifies the type of elements stored, arrayName is the identifier, and size is a positive integer defining the maximum number of elements.
  • Example: int grades[5]; declares an array named grades capable of holding $5$ integer values.

• Key Characteristics of Arrays:

  • Homogeneous Data: All elements stored within an array must belong to the exact same data type.
  • Contiguous Memory Allocation: Elements are assigned adjacent physical memory addresses. For an integer array starting at memory address $1000$, where each int occupies $4$ bytes, the element addresses are $1000, 1004, 1008, 1012,$ and $1016$.
  • Fixed Capacity: The size of an array is fixed at compile time (or upon declaration) and cannot expand or contract during runtime execution.
  • Zero-Based Indexing: In C++, indexing starts at $0$ (the first element) and ends at $n - 1$ (where $n$ is the array size). Valid indices for an array of size $n$ range strictly from $0$ to $n - 1$.

• Memory Layout & Indexing Mechanics:

  • Array Index Range: For size $n$, valid indices are $0, 1, 2, \dots, n - 1$.
  • Accessing outside this valid range (e.g., index $n$ or negative indices) causes out-of-bounds access, leading to runtime errors, data corruption, or Segmentation Faults.

• Array Declaration and Initialization Methods:

  • Full Initialization: Every element is explicitly assigned an initial value at declaration.
  • Example: int marks[3] = {100, 95, 90}; assigns index $0 = 100$, index $1 = 95$, and index 2 = 90$.\n * **Partial Initialization**: Fewer values than the declared size are provided. Uninitialized elements automatically default to 0 for numeric data types.\n * Example: `int marks[5] = {100, 95};` assigns index 0 = 100$, index$1 = 95$, and indices$2, 3, 4 = 0$.
  • Inferred Size (Implicit Dimensioning): The size specification is left empty inside the brackets, and the compiler automatically deduces the array size based on the initializer list.
  • Example: int marks[] = {100, 95, 90}; creates an array of size 3$.\n * **Character Array Initialization**: String literals auto-terminate with a null character `'\0'`.\n * Example: `char name[] = "C++";` creates an array of size 4 containing `'C'`, `'+'`, `'+'`, and `'\0'` at indices 0, 1, 2, 3 respectively.\n\n* **Arrays of Various Primitive Data Types**:\n * **Integer Array**: `int numbers[5] = {10, 20, 30, 40, 50};` (Stores whole numbers such as counts, IDs, or ages).\n * **Float Array**: `float prices[4] = {99.99, 120.50, 75.25, 150.00};` (Stores decimal floating-point values such as prices or measurements).\n * **Character Array**: `char letters[6] = {'C', 'P', 'P', 'R', 'O', 'G'};` (Stores single character literals such as initials or grades).\n * **Boolean Array**: `bool flags[4] = {true, false, true, true};` (Stores true/false logical states or flags).\n\n* **Primary Use Cases of Arrays in Systems & Software**:\n * **Storing Lists of Items**: Holding collections of related values under a single identifier (e.g., `string names[5] = {"Ana", "Ben", "Cara", "Dan", "Eli"};`).\n * **Processing Data in Loops**: Iterating through collections sequentially to compute sums, averages, or apply transforms.\n * **Searching Data**: Scanning entries to locate target values via Linear Search or Binary Search.\n * **Sorting Data**: Reordering elements into ascending or descending sequence using algorithms like Bubble Sort.\n * **Counting Occurrences**: Tracking frequency distributions for data aggregation.\n * **Implementing Stack Data Structures**: Foundation for Last-In, First-Out (LIFO) stacks via push and pop mechanics.\n * **Implementing Queue Data Structures**: Foundation for First-In, First-Out (FIFO) queues using front and rear indices.\n * **Matrix and Multi-Dimensional Data**: Representing grid-based or tabular structures (e.g., `int matrix[3][3];`).\n * **Frequency Analysis**: Accumulating tally arrays for statistical computation (e.g., `freq[value]++;`).\n * **Lookup Tables and Mapping**: Storing precomputed constants for instant O(1) retrieval (e.g., `int daysInMonth[12] = {31, 28, 31, 30, 31, 30, ...};`).\n\n# Array Operations and C++ Implementations\n\n* **Accessing Array Elements**:\n * Retrieves the value stored at a specific index without modifying the array contents.\n * Performance: Time Complexity O(1)$(Constant Time); Space Complexity$O(1) (Constant Space).\n * C++ Implementation:\n```cpp\n#include \n#include \nusing namespace std;\n\nint main() {\n int numbers[5] = {10, 20, 30, 40, 50};\n cout << "The value at index 0 is " << numbers[0] << endl;\n cout << "The value at index 1 is " << numbers[1] << endl;\n cout << "The value at index 2 is " << numbers[2] << endl;\n return EXIT_SUCCESS;\n}\n```\n * Output:\n * `The value at index 0 is 10`\n * `The value at index 1 is 20`\n * `The value at index 2 is 30`\n\n* **Traversing Array Elements**:\n * Sequential iteration over every array element from index 0$to$\text{size} - 1 exactly once.\n * Performance: Time Complexity O(n)$(Linear Time); Space Complexity$O(1) (Constant Space).\n * C++ Implementation:\n```cpp\n#include \n#include \nusing namespace std;\n\nint main() {\n int numbers[5] = {10, 20, 30, 40, 50};\n int size = 5;\n cout << "Traversing the array: " << endl;\n for (int i = 0; i < size; i++) {\n cout << "numbers[" << i << "]: " << numbers[i] << endl;\n }\n return EXIT_SUCCESS;\n}\n```\n\n* **Appending an Element (Add at End)**:\n * Inserts a new element at index position `size`, then increments `size` by 1. Requires checking `size < CAPACITY` to prevent memory overflow.\n * Performance: Time Complexity O(1)$(Constant Time); Space Complexity$O(1).\n * C++ Implementation:\n```cpp\n#include \n#include \nusing namespace std;\n\nint main() {\n const int CAPACITY = 5;\n int numbers[CAPACITY] = {10, 20, 30, 40};\n int size = 4;\n int newValue;\n cout << "Enter value to be appended at the end: ";\n cin >> newValue;\n if (size < CAPACITY) {\n numbers[size] = newValue;\n size++;\n cout << "Appended " << newValue << " at the end. New array size is " << size << endl;\n } else {\n cout << "Cannot append. Array is full." << endl;\n }\n return EXIT_SUCCESS;\n}\n```\n\n* **Inserting an Element at a Specific Position**:\n * Shifts existing elements at and to the right of target `position` one index to the right (starting from index `size` down to `position + 1`), places `newValue` at `numbers[position]`, and increments `size` by 1$.
  • Performance: Time Complexity $O(n)$ (Linear Time due to element shifting); Space Complexity $O(1)$.
  • C++ Implementation:

#include <iostream>
#include <cstdlib>
using namespace std;

int main() {
    const int CAPACITY = 6;
    int numbers[CAPACITY] = {10, 20, 30, 40, 50};
    int size = 5;
    int position, newValue;
    cout << "Enter position to insert (from 0 to 5): ";
    cin >> position;
    cout << "Enter value to insert: ";
    cin >> newValue;
    if (size < CAPACITY && position >= 0 && position <= size) {
        for (int i = size; i > position; i--) {
            numbers[i] = numbers[i - 1];
        }
        numbers[position] = newValue;
        size++;
        cout << "Array after insertion: " << endl;
        for (int i = 0; i < size; i++) {
            cout << numbers[i] << " ";
        }
        cout << endl;
    } else {
        cout << "Cannot insert. Array is full or position is invalid." << endl;
    }
    return EXIT_SUCCESS;
}

• Removing (Deleting) an Element at a Specific Position:

  • Removes element at position by shifting all subsequent elements one slot to the left (from index position up to size - 2), then decrements size by 1$.\n * Performance: Time Complexity O(n)$(Linear Time); Space Complexity$O(1).\n * C++ Implementation:\n```cpp\n#include \n#include \nusing namespace std;\n\nint main() {\n int numbers[5] = {10, 20, 30, 40, 50};\n int size = 5;\n int position;\n cout << "Remove element at index (0-4): ";\n cin >> position;\n if (size > 0 && position >= 0 && position < size) {\n for (int i = position; i < size - 1; i++) {\n numbers[i] = numbers[i + 1];\n }\n size--;\n cout << "Array after removing element at index " << position << ":" << endl;\n for (int i = 0; i < size; i++) {\n cout << numbers[i] << " ";\n }\n cout << endl;\n } else {\n cout << "Invalid position or empty array." << endl;\n }\n return EXIT_SUCCESS;\n}\n```\n\n* **Pop Operation (Delete from End)**:\n * Deletes the last element located at index `size - 1` by decrementing `size` by 1. Does not require shifting elements.\n * Performance: Time Complexity O(1)$(Constant Time); Space Complexity$O(1).\n * C++ Implementation:\n```cpp\n#include \n#include \nusing namespace std;\n\nint main() {\n int numbers[5] = {10, 20, 30, 40, 50};\n int size = 5;\n if (size > 0) {\n int popped = numbers[size - 1];\n size--;\n cout << "Popped element: " << popped << endl;\n cout << "Array after pop operation: " << endl;\n for (int i = 0; i < size; i++) {\n cout << numbers[i] << " ";\n }\n cout << endl;\n } else {\n cout << "Array is empty! Cannot perform pop." << endl;\n }\n return EXIT_SUCCESS;\n}\n```\n\n* **Searching Array Elements (Linear Search)**:\n * Compares target search value against elements sequentially from index 0$to `size - 1`. Returns matching index, or$-1 if not present.\n * Performance: Time Complexity O(n)$(Worst/Average Case$O(n)$, Best Case$O(1)$); Space Complexity$O(1).\n * C++ Implementation:\n```cpp\n#include \n#include \nusing namespace std;\n\nint main() {\n int numbers[5] = {10, 20, 30, 40, 50};\n int size = 5;\n int target;\n int found = -1;\n cout << "Enter a value to search: ";\n cin >> target;\n for (int i = 0; i < size; i++) {\n if (numbers[i] == target) {\n found = i;\n break;\n }\n }\n if (found != -1) {\n cout << target << " found at index " << found << endl;\n } else {\n cout << target << " not found in the array" << endl;\n }\n return EXIT_SUCCESS;\n}\n```\n\n* **Sorting Array Elements (Bubble Sort)**:\n * Repeatedly passes through array, comparing adjacent elements `numbers[j]` and `numbers[j + 1]`, and swapping them if `numbers[j] > numbers[j + 1]`. Bubbles largest unsorted element to correct rightmost position per pass.\n * Performance: Worst/Average Case Time Complexity O(n^2)$, Best Case Time Complexity$O(n)$(when already sorted and checked via `swapped` flag); Space Complexity$O(1).\n * C++ Implementation:\n```cpp\n#include \n#include \nusing namespace std;\n\nint main() {\n int numbers[5] = {50, 10, 30, 20, 40};\n int size = 5;\n for (int pass = 0; pass < size - 1; pass++) {\n bool swapped = false;\n for (int j = 0; j < size - 1 - pass; j++) {\n if (numbers[j] > numbers[j + 1]) {\n int temp = numbers[j];\n numbers[j] = numbers[j + 1];\n numbers[j + 1] = temp;\n swapped = true;\n }\n }\n if (!swapped) break;\n }\n cout << "Sorted Array (Ascending): " << endl;\n for (int i = 0; i < size; i++) {\n cout << numbers[i] << " ";\n }\n cout << endl;\n return EXIT_SUCCESS;\n}\n```\n\n# Array Performance, Limitations, and Memory Allocation\n\n* **Advantages of Arrays**:\n * **Fast Random Access**: Direct access to any element in O(1) constant time using `arrayName[index]` without traversing preceding entries.\n * **Simple Traversal**: Straightforward sequential iteration using standard loops.\n * **Memory Efficiency**: Low memory overhead per element since data resides in contiguous blocks without needing extra link pointers.\n * **Simple Implementation**: Easy to declare, initialize, and integrate into fixed-size data models.\n * **Algorithmic Foundation**: Building block for complex data structures (stacks, queues, matrices, hash tables).\n\n* **Limitations of Arrays**:\n * **Fixed Capacity**: Array size is defined prior to execution and cannot change dynamically.\n * **Costly Insertions and Deletions**: Inserting or deleting elements in the middle requires shifting elements right or left, incurring O(n) time.\n * **Memory Waste (Unused Allocated Capacity)**: Allocating dynamic bounds larger than actual stored items leaves memory idle.\n * **Homogeneous Data Restriction**: Stores only identical data types.\n * **Contiguous Allocation Requirement**: Requires a single unbroken physical memory block; allocation fails if contiguous memory is unavailable.\n\n* **Out-of-Bounds Execution Errors**:\n * Attempting to store elements past maximum declared array bounds (e.g., storing student 41$in `int students[40];` at index$40) causes runtime errors, memory corruption, or Segmentation Faults.\n\n# Dynamic Memory Allocation and Pointers\n\n* **Static (Fixed) Memory vs. Dynamic Memory**:\n * **Static/Fixed Memory**: Memory size and location allocated at compile time. Flexible capacity is unavailable; size remains static during program lifetime.\n * **Dynamic Memory (Heap Memory)**: Allocated dynamically during execution (runtime) from the Heap. Size can expand or contract to match program execution requirements.\n\n* **The Dynamic Memory Allocation Cycle**:\n 1. **Request**: Program asks the operating system heap for a block of memory of specified byte size.\n 2. **Allocate**: Operating system reserves the memory block and returns its starting memory address.\n 3. **Use**: Program reads, writes, and manipulates data within allocated heap space via pointers.\n 4. **Release**: Program explicitly returns memory block back to heap when no longer needed.\n\n* **Pointer Fundamentals in C++**:\n * **Definition**: A pointer is a special variable that stores the physical memory address of another variable.\n * **Operators**:\n * Address-of Operator (`&`): Obtains physical address of variable (e.g., `&age`).\n * Dereference / Pointer Declaration Operator (`*`): Declares pointer type or dereferences pointer address to access stored underlying value (e.g., `int* pAge = &age;`, `cout << *pAge;`).\n * **Dynamic Allocation Operators**:\n * `new`: Requests memory from the heap dynamically (e.g., `int* grades = new int[5];`).\n * `delete[]`: Deallocates dynamic array memory back to heap (e.g., `delete[] grades;`). Failure to call `delete[]` causes memory leaks.\n * `nullptr`: Pointer literal assigned after deallocation to remove references and prevent dangling pointer access.\n\n* **Dynamic Array Resizing (Growing and Shrinking at Runtime)**:\n * C++ Implementation demonstrating allocating initial array, requesting new size, copying valid elements, freeing old memory block, and reassigning pointers:\n```cpp\n#include \n#include \nusing namespace std;\n\nint main() {\n int size = 5;\n int* grades = new int[size];\n cout << "Enter 5 grades: " << endl;\n for (int i = 0; i < size; i++) {\n grades[i] = 80 + i;\n }\n \n int newSize;\n cout << "Enter the new array size: ";\n cin >> newSize;\n \n int* newGrades = new int[newSize];\n int copySize = (newSize < size) ? newSize : size;\n for (int i = 0; i < copySize; i++) {\n newGrades[i] = grades[i];\n }\n \n delete[] grades;\n grades = newGrades;\n size = newSize;\n \n if (newSize > copySize) {\n cout << "Enter additional grades: " << endl;\n for (int i = copySize; i < size; i++) {\n cin >> grades[i];\n }\n }\n \n cout << "Final grades: " << endl;\n for (int i = 0; i < size; i++) {\n cout << grades[i] << " ";\n }\n cout << endl;\n \n delete[] grades;\n grades = nullptr;\n return EXIT_SUCCESS;\n}\n```\n\n# Fundamentals of Linked Lists\n\n* **Concept and Structure**:\n * A linked list is a dynamic data structure comprising individual units called **nodes**, connected logically using pointer references.\n * Unlike arrays, linked list nodes do not require contiguous memory addresses; nodes can be located anywhere in memory.\n * Memory expands and contracts per element insertion/deletion without requiring global reallocations or element shifts.\n\n* **Node Anatomy**:\n * A basic Node consists of two core components:\n 1. **Data Field**: Stores the actual value/payload (primitive or complex data type).\n 2. **Pointer Field(s)**: Stores memory address links pointing to neighboring nodes (`next` for singly/circular lists; `prev` and `next` for doubly lists).\n\n* **Logical Order vs. Physical Memory**:\n * Nodes are chained logically via memory addresses stored in node pointers.\n * Example Physical Memory vs Logical Sequence:\n * Node 1: Address `3000`, Data `10`, Next `1500`\n * Node 2: Address `1500`, Data `20`, Next `2400`\n * Node 3: Address `2400`, Data `30`, Next `1000`\n * Node 4: Address `1000`, Data `40`, Next `nullptr`\n * Traversing starting from `HEAD = 3000` yields ordered values: `10 -> 20 -> 30 -> 40 -> NULL` regardless of non-sequential memory addresses.\n\n# Singly Linked List Operations and C++ Implementations\n\n* **Structure of Singly Linked List**:\n * Each node contains a single data payload and a single pointer (`next`) pointing to the sequential successor.\n * `HEAD` pointer stores the address of the first node.\n * Terminal node's `next` pointer holds `nullptr` (or `NULL`), marking the list end.\n\n* **Singly Linked List Node Declaration in C++**:\n```cpp\nstruct Node {\n int data;\n Node* next;\n};\n```\n\n* **Traversal Operation**:\n * Sequential access starting from `head` up to `nullptr`.\n * Time Complexity O(n)$, Space Complexity$O(1).\n * C++ Implementation:\n```cpp\nNode* current = head;\nwhile (current != nullptr) {\n cout << current->data << " ";\n current = current->next;\n}\ncout << endl;\n```\n\n* **Insertion at the Beginning**:\n * Creates new node, sets `newNode->next = head`, updates `head = newNode`.\n * Time Complexity O(1).\n * C++ Implementation:\n```cpp\nNode* newNode = new Node;\nnewNode->data = num;\nnewNode->next = head;\nhead = newNode;\n```\n\n* **Insertion at the End**:\n * Creates new node (`newNode->next = nullptr`), traverses list until `current->next == nullptr`, links `current->next = newNode`.\n * Time Complexity O(n).\n * C++ Implementation:\n```cpp\nNode* newNode = new Node;\nnewNode->data = num;\nnewNode->next = nullptr;\nif (head == nullptr) {\n head = newNode;\n} else {\n Node* current = head;\n while (current->next != nullptr) {\n current = current->next;\n }\n current->next = newNode;\n}\n```\n\n* **Insertion Between Nodes (At Specific Position)**:\n * Traverses list to target position - 1 (`current`), links `newNode->next = current->next`, then updates `current->next = newNode`.\n * Time Complexity O(n).\n * C++ Implementation:\n```cpp\nNode* newNode = new Node;\nnewNode->data = num;\nNode* current = head;\nfor (int i = 1; i < position - 1; i++) {\n current = current->next;\n}\nnewNode->next = current->next;\ncurrent->next = newNode;\n```\n\n* **Deletion of a Node**:\n * Bypasses targeted node by re-linking predecessor node directly to successor node, then frees memory using `delete`.\n * If deleting first node: updates `head = head->next`, then deletes old head.\n * Time Complexity O(n).\n * C++ Implementation:\n```cpp\nif (position == 1) {\n Node* temp = head;\n head = head->next;\n delete temp;\n} else {\n Node* current = head;\n for (int i = 1; i < position - 1; i++) {\n current = current->next;\n }\n Node* temp = current->next;\n current->next = temp->next;\n delete temp;\n}\n```\n\n* **Searching a Node**:\n * Traverses list sequentially comparing `current->data == searchValue` until match found or `nullptr` reached.\n * Time Complexity O(n).\n * C++ Implementation:\n```cpp\nNode* current = head;\nint position = 1;\nwhile (current != nullptr && current->data != searchValue) {\n current = current->next;\n position++;\n}\nif (current != nullptr) {\n cout << searchValue << " found at position " << position << endl;\n} else {\n cout << searchValue << " not found." << endl;\n}\n```\n\n# Doubly Linked Lists\n\n* **Concept and Structure**:\n * Each node contains three fields: data payload, `prev` pointer (points to preceding node), and `next` pointer (points to succeeding node).\n * Maintained by `HEAD` pointer (first node) and `TAIL` pointer (last node).\n * First node `prev` points to `nullptr`; last node `next` points to `nullptr`.\n\n* **Doubly Linked List Node Declaration in C++**:\n```cpp\nstruct Node {\n int data;\n Node* prev;\n Node* next;\n};\n```\n\n* **Two-Way Traversal Mechanics**:\n * **Forward Traversal**: Start at `HEAD`, follow `next` pointers until `nullptr`.\n * **Backward Traversal**: Start at `TAIL`, follow `prev` pointers until `nullptr`.\n * C++ Implementation:\n```cpp\n// Forward Traversal\nNode* current = head;\nwhile (current != nullptr) {\n cout << current->data << " ";\n current = current->next;\n}\ncout << endl;\n\n// Backward Traversal\ncurrent = tail;\nwhile (current != nullptr) {\n cout << current->data << " ";\n current = current->prev;\n}\ncout << endl;\n```\n\n# Circular Linked Lists\n\n* **Concept and Structure**:\n * Linked list variant where the final node's `next` pointer points back to `HEAD` node instead of `nullptr`, forming an unbroken circular loop.\n * Does not contain `nullptr` terminally during active traversal.\n\n* **Traversal Mechanics**:\n * Traversal executed using `do-while` loops to guarantee processing initial head node prior to evaluating loop continuation condition (`current != head`).\n * Memory cleanup requires explicitly severing circular pointer (`lastNode->next = nullptr`) before node deallocation loops.\n * C++ Implementation:\n```cpp\nNode* current = head;\ndo {\n cout << current->data << " ";\n current = current->next;\n} while (current != head);\ncout << endl;\n```\n\n# Comparative Analysis and Use Cases of Linked Lists\n\n* **Structural Comparison Matrix**:\n * **Singly Linked List**:\n * Forward movement: Yes\n * Backward movement: No\n * Last points to `nullptr`: Yes\n * Last connects to first: No\n * Memory per node: Lower (1 pointer)\n * Primary Characteristics: Sequential traversal\n * **Doubly Linked List**:\n * Forward movement: Yes\n * Backward movement: Yes\n * Last points to `nullptr`: Yes\n * Last connects to first: No\n * Memory per node: Higher (2 pointers)\n * Primary Characteristics: Bidirectional traversal\n * **Circular Linked List**:\n * Forward movement: Yes\n * Backward movement: Depends on implementation (Singly/Doubly Circular)\n * Last points to `nullptr`: No\n * Last connects to first: Yes\n * Memory per node: Depends\n * Primary Characteristics: Repeating loop cycles\n\n\n\n* **Domain-Specific Use Cases**:\n * **Singly Linked List**: Dynamic collections with frequent insert/delete operations, stack and queue implementations, polynomial arithmetic representation.\n * **Doubly Linked List**: Web browser navigation history (Back/Forward), text editor undo/redo buffers, Least Recently Used (LRU) Cache structures.\n * **Circular Linked List**: Operating system Round-Robin CPU scheduling, multiplayer turn-based gaming rotations, continuous audio/video playback playlists, circular ring buffer structures.\n\n# Stack Data Structure: LIFO Architecture\n\n* **Definition and Fundamental Principle**:\n * A stack is an ordered linear data structure operating strictly under the **Last In, First Out (LIFO)** policy.\n * Insertions and deletions are restricted strictly to a single operational end called the **TOP**.\n * The bottom of the stack (**BOTTOM**) remains fixed; elements stored below TOP cannot be accessed directly without popping preceding items.\n\n* **Real-World Analogies**:\n * Stack of cafeteria plates (top plate added last is retrieved first).\n * Web browser back button history navigation.\n * Text editor multi-level UNDO action buffers.\n\n* **Core Stack Operations**:\n 1. `push(value)`: Inserts element onto TOP of stack.\n 2. `pop()`: Removes and returns topmost element from TOP of stack.\n 3. `peek()` / `top()`: Returns topmost element value without deleting it.\n 4. `isEmpty()`: Returns `true` if stack contains zero elements, else `false`.\n 5. `isFull()`: Returns `true` if array capacity bounds are reached (for static stacks).\n\n* **Stack Error Boundary Conditions**:\n * **Stack Overflow**: Attempting to execute `push()` when stack is full (`top == MAX - 1`).\n * **Stack Underflow**: Attempting to execute `pop()` or `peek()` when stack is empty (`top == -1` or `top == nullptr`).\n\n# Stack Implementations in C++\n\n* **1. Array-Based Stack Implementation**:\n```cpp\n#include \n#include \nusing namespace std;\n\nconst int MAX = 10;\nint stackArray[MAX];\nint top = -1;\n\nbool isEmpty() {\n return top == -1;\n}\n\nvoid push(int value) {\n if (top == MAX - 1) {\n cout << "Stack Overflow" << endl;\n } else {\n top++;\n stackArray[top] = value;\n cout << "Pushed: " << value << endl;\n }\n}\n\nvoid pop() {\n if (isEmpty()) {\n cout << "Stack Underflow" << endl;\n } else {\n cout << "Popped: " << stackArray[top] << endl;\n top--;\n }\n}\n\nvoid peek() {\n if (isEmpty()) {\n cout << "Stack is empty." << endl;\n } else {\n cout << "Top element: " << stackArray[top] << endl;\n }\n}\n\nvoid display() {\n if (isEmpty()) {\n cout << "Stack is empty." << endl;\n } else {\n cout << "STACK ELEMENTS (Top to Bottom):" << endl;\n for (int i = top; i >= 0; i--) {\n cout << stackArray[i] << endl;\n }\n }\n}\n```\n\n* **2. Singly Linked List-Based Stack Implementation**:\n```cpp\n#include \n#include \nusing namespace std;\n\nstruct Node {\n int data;\n Node* next;\n};\n\nNode* top = nullptr;\n\nbool isEmpty() {\n return top == nullptr;\n}\n\nvoid push(int value) {\n Node* newNode = new Node;\n newNode->data = value;\n newNode->next = top;\n top = newNode;\n cout << "Pushed: " << value << endl;\n}\n\nvoid pop() {\n if (isEmpty()) {\n cout << "Stack Underflow" << endl;\n } else {\n Node* temp = top;\n cout << "Popped: " << top->data << endl;\n top = top->next;\n delete temp;\n }\n}\n\nvoid peek() {\n if (isEmpty()) {\n cout << "Stack is empty." << endl;\n } else {\n cout << "Top element: " << top->data << endl;\n }\n}\n\nvoid display() {\n if (isEmpty()) {\n cout << "Stack is empty." << endl;\n } else {\n cout << "STACK ELEMENTS (Top to Bottom):" << endl;\n Node* current = top;\n while (current != nullptr) {\n cout << current->data << endl;\n current = current->next;\n }\n }\n}\n```\n\n# Stack Applications and Practical Execution\n\n* **Text Editor UNDO Simulation Trace**:\n * Action 1: Type "A" \rightarrow$Push("A")$\rightarrow Stack State: `[A]` (Top: A)\n * Action 2: Type "B" \rightarrow$Push("B")$\rightarrow Stack State: `[B, A]` (Top: B)\n * Action 3: Type "C" \rightarrow$Push("C")$\rightarrow Stack State: `[C, B, A]` (Top: C)\n * Action 4: Delete "B" \rightarrow$Push("Delete B")$\rightarrow Stack State: `[Delete B, C, B, A]` (Top: Delete B)\n * User presses UNDO \rightarrow$Pop() removes "Delete B"$\rightarrow Restores state to `[C, B, A]`\n * User presses UNDO \rightarrow$Pop() removes "C"$\rightarrow Restores state to `[B, A]`\n * User presses UNDO \rightarrow$Pop() removes "B"$\rightarrow Restores state to `[A]`\n\n# Queue Data Structure: FIFO Architecture\n\n* **Definition and Fundamental Principle**:\n * A queue is a linear data structure operating under the **First In, First Out (FIFO)** principle.\n * Insertions occur exclusively at the **REAR** end of the queue (**Enqueue** operation).\n * Deletions occur exclusively at the **FRONT** end of the queue (**Dequeue** operation).\n\n* **Real-World System Use Cases**:\n * Shared network printer queues.\n * Operating system CPU process scheduling queues.\n * Telecommunication call center incoming call routing.\n * Network packet switching buffers.\n * Graph Breadth-First Search (BFS) node processing.\n\n* **Core Queue Operations**:\n 1. `enqueue(value)`: Inserts element at REAR of queue.\n 2. `dequeue()`: Removes element from FRONT of queue.\n 3. `peek()` / `front()`: Reads value at FRONT without removing it.\n 4. `isEmpty()`: Returns `true` if queue holds no elements.\n 5. `isFull()`: Returns `true` if queue array capacity is fully occupied.\n\n# Queue Variants: Linear, Circular, and Priority Queues\n\n* **1. Linear Queue (Array-Based)**:\n * Both `front` and `rear` pointers move strictly forward (rightward).\n * Empty Condition: `front == -1 && rear == -1`.\n * Full Condition: `rear == MAX - 1`.\n * **Limitation (Wasted Space / False Full Condition)**:\n * Once `rear` reaches `MAX - 1`, subsequent `enqueue()` calls trigger Queue Overflow errors, even if preceding `dequeue()` operations have freed slots at the front of the array (indices 0, 1, \dots).\n\n* **2. Circular Queue (Array-Based)**:\n * Connects array end back to index 0$using modulo circular arithmetic:$\text{next} = (i + 1) \pmod{\text{MAX}}.
  • Empty Condition: front == -1 && rear == -1.
  • Full Condition: (rear + 1) % MAX == front.
  • Prevents wasted memory slots by allowing rear to wrap around to fill deallocated front positions.

• 3. Priority Queue:

  • Elements are dequeued based on assigned priority ranking rather than insertion arrival sequence.
  • Example Trace (Higher number = higher priority):
  • Enqueue Sequence: D(10), E(7), B(5), A(2), C(1)
  • Dequeue Order: D(10) -> E(7) -> B(5) -> A(2) -> C(1)

• Queue Variant Feature Comparison Matrix:

  • Linear Queue:
  • Order of Removal: FIFO
  • Memory Utilization: May waste space at front
  • Overflow Condition: rear == MAX - 1
  • Primary Applications: Printer queues, simple buffering, BFS
  • Circular Queue:
  • Order of Removal: FIFO with wrap-around
  • Memory Utilization: Uses all slots efficiently
  • Overflow Condition: (rear + 1) % MAX == front
  • Primary Applications: CPU Round-Robin scheduling, ring buffers
  • Priority Queue:
  • Order of Removal: Highest / Lowest priority value
  • Memory Utilization: Structure-dependent (Heap / Sorted List)
  • Overflow Condition: When heap/array capacity is reached
  • Primary Applications: Priority CPU scheduling, Dijkstra's algorithm, interrupt handling

Queue Implementations in C++

• 1. Circular Array-Based Queue Implementation:

#include <iostream>
#include <cstdlib>
using namespace std;

const int MAX = 10;
int queueArray[MAX];
int front = -1;
int rear = -1;

bool isEmpty() {
    return front == -1 && rear == -1;
}

bool isFull() {
    return (rear + 1) % MAX == front;
}

void enqueue(int value) {
    if (isFull()) {
        cout << "Queue Overflow" << endl;
    } else {
        if (isEmpty()) {
            front = 0;
            rear = 0;
        } else {
            rear = (rear + 1) % MAX;
        }
        queueArray[rear] = value;
        cout << "Enqueued: " << value << endl;
    }
}

void dequeue() {
    if (isEmpty()) {
        cout << "Queue Underflow" << endl;
    } else {
        cout << "Dequeued: " << queueArray[front] << endl;
        if (front == rear) {
            front = -1;
            rear = -1;
        } else {
            front = (front + 1) % MAX;
        }
    }
}

void peek() {
    if (isEmpty()) {
        cout << "Queue is empty." << endl;
    } else {
        cout << "Front element: " << queueArray[front] << endl;
    }
}

void display() {
    if (isEmpty()) {
        cout << "Queue is empty." << endl;
    } else {
        cout << "QUEUE ELEMENTS (Front to Rear): ";
        int current = front;
        while (true) {
            cout << queueArray[current] << " ";
            if (current == rear) break;
            current = (current + 1) % MAX;
        }
        cout << endl;
    }
}

• 2. Singly Linked List-Based Queue Implementation:

#include <iostream>
#include <cstdlib>
using namespace std;

struct Node {
    int data;
    Node* next;
};

Node* front = nullptr;
Node* rear = nullptr;

bool isEmpty() {
    return front == nullptr && rear == nullptr;
}

void enqueue(int value) {
    Node* newNode = new Node;
    newNode->data = value;
    newNode->next = nullptr;
    if (isEmpty()) {
        front = newNode;
        rear = newNode;
    } else {
        rear->next = newNode;
        rear = newNode;
    }
    cout << "Enqueued: " << value << endl;
}

void dequeue() {
    if (isEmpty()) {
        cout << "Queue Underflow" << endl;
    } else {
        Node* temp = front;
        cout << "Dequeued: " << front->data << endl;
        front = front->next;
        if (front == nullptr) {
            rear = nullptr;
        }
        delete temp;
    }
}

void peek() {
    if (isEmpty()) {
        cout << "Queue is empty." << endl;
    } else {
        cout << "Front element: " << front->data << endl;
    }
}

void display() {
    if (isEmpty()) {
        cout << "Queue is empty." << endl;
    } else {
        cout << "QUEUE ELEMENTS (Front to Rear): ";
        Node* current = front;
        while (current != nullptr) {
            cout << current->data << " ";
            current = current->next;
        }
        cout << endl;
    }
}

Queue Applications and Practical Execution

• Printer Queue Simulation Execution Trace:
  • Four print jobs submitted sequentially: User A (Doc A), User B (Doc B), User C (Doc C), User D (Doc D).
  • Execution Log:
  • Step 1: User A sends Doc A \rightarrow$Enqueue(<code>Doc A</code>)$\rightarrow Queue: [Doc A] (Front: Doc A, Rear: Doc A)
  • Step 2: User B sends Doc B \rightarrow$Enqueue(<code>Doc B</code>)$\rightarrow Queue: [Doc A, Doc B] (Front: Doc A, Rear: Doc B)
  • Step 3: User C sends Doc C \rightarrow$Enqueue(<code>Doc C</code>)$\rightarrow Queue: [Doc A, Doc B, Doc C] (Front: Doc A, Rear: Doc C)
  • Step 4: User D sends Doc D \rightarrow$Enqueue(<code>Doc D</code>)$\rightarrow Queue: [Doc A, Doc B, Doc C, Doc D] (Front: Doc A, Rear: Doc D)
  • Step 5: Printer processes Doc A \rightarrow$Dequeue()$\rightarrow$Prints <code>Doc A</code>$\rightarrow Queue: [Doc B, Doc C, Doc D]
  • Step 6: Printer processes Doc B \rightarrow$Dequeue()$\rightarrow$Prints <code>Doc B</code>$\rightarrow Queue: [Doc C, Doc D]
  • Step 7: Printer processes Doc C \rightarrow$Dequeue()$\rightarrow$Prints <code>Doc C</code>$\rightarrow Queue: [Doc D]
  • Step 8: Printer processes Doc D \rightarrow$Dequeue()$\rightarrow$Prints <code>Doc D</code>$\rightarrow$$ Queue: Empty (front = -1, rear = -1)
  • Final Printed Output Order: Doc A -> Doc B -> Doc C -> Doc D (Strict FIFO Order).