Stacks

Stack: A linear list that permits insertion or deletion operations to occur at only one designated end.
Top: The specific end of the linear list where insertions or deletions are allowed to take place.
Bottom: The fixed, opposite end of the linear list where insertions and deletions are strictly prohibited.
Characteristics: A restricted linear list that retains linear relationships; follows the Last-In, First-Out (LIFO) principle.

Sequential Stacks

Utilizes sequential storage to allocate data elements from the bottom upward, with a pointer indicating the current position of the top element.
Basic Operations:

    s.top = -1;             // Check if empty / Initialize empty state
    s.data[++s.top] = x;    // Push operation (Increment top, then insert)
    x = s.data[s.top--];    // Pop operation (Retrieve top, then decrement)
    x = s.data[s.top];      // Peek operation (Read top element without removing)

Two distinct stacks share a single, contiguous one-dimensional array workspace.
The two stacks are initialized at opposite ends of the shared memory space.
Their respective top pointers grow inward toward the center as elements are added.
Highly efficient for optimizing memory space utilization.

Linked Stacks

Implemented using a linked storage structure (nodes with pointers).
Facilitates efficient dynamic storage sharing among multiple stack instances.
Offers high execution efficiency since memory is allocated dynamically without size limits.

Queues

A linear list that restricts insertions to one end and deletions to the opposite end.
Front: The designated end where deletion operations are performed.
Rear: The designated end where insertion operations are performed.
Characteristics: Follows the First-In, First-Out (FIFO) principle.

Sequential Queues

Allocates a contiguous block of memory storage cells.
The front pointer indicates the position of the head element.
The rear pointer indicates the position where the next element will be appended.

Circular Queues

A sequential storage queue logically mapped to connect the front and rear ends in a continuous loop.
Basic Operations:

    Q.rear = Q.front = 0;                           // Initialize queue empty state
    rear = (rear + 1) % MaxSize;                    // Enqueue operation
    front = (front + 1) % MaxSize;                  // Dequeue operation
    queueLen = (rear + MaxSize - front) % MaxSize;  // Compute current queue length

Determining Empty vs. Full States:

    // Approach 1: Sacrificing one storage slot to differentiate empty from full
    (Q.rear + 1) % MaxSize == Q.front;  // Queue Full Condition
    Q.front == Q.rear;                  // Queue Empty Condition

    // Approach 2: Introducing an explicit element counter variable in the structure
    Q.size == 0;                        // Queue Empty Condition
    Q.size == MaxSize;                  // Queue Full Condition

    // Approach 3: Utilizing an explicit boolean 'tag' state flag
    tag == 0;                           // Queue is empty if front == rear after a pop/dequeue
    tag == 1;                           // Queue is full if front == rear after a push/enqueue

Linked Queues

A queue layout implemented using a singly linked list mechanism, accompanied by distinct front and rear pointers to safely lock the head and tail tracking locations.

Double-Ended Queues (Deques)

A generalized linear list that permits elements to be inserted or removed from both ends.
Output-Restricted Deque: A double-ended queue that allows insertions at both ends but restricts deletions to only one designated end.
Input-Restricted Deque: A double-ended queue that allows deletions at both ends but restricts insertions to only one designated end.

Practical Applications

1. Stack Application: Bracket Matching (Parenthesis Matching)

Algorithmic Concept

Initialize an empty stack and read input characters sequentially from left to right.
Closing Bracket Encountered: Check the top of the stack. If it is a matching opening bracket, pop it to resolve the pair. Otherwise, the sequence is illegal (mismatched, exit with failure).
Opening Bracket Encountered: Push it onto the top of the stack as a higher priority element to be matched later.
End of Input: If the stack is completely empty, the bracket sequence is successfully matched; otherwise, unmatched brackets remain, indicating an invalid sequence.

2. Stack Application: Expression Evaluation

Converts standard Infix Expressions (e.g., A + B) into executable Postfix Expressions (Reverse Polish Notation, e.g., A B +) to facilitate stack-based computer evaluation.

3. Stack Application: Recursion Implementation

Core Concept: Solves a complex programming challenge by breaking down the original problem into smaller sub-problems that share identical properties.
Formulate the mathematical recursive relation.
Define explicit base conditions (recursion termination exits) to prevent infinite loops.

4. Queue Application: Level-Order Traversals

Extensively used in hierarchical data processing, such as Breadth-First Search (BFS) graphs or Level-Order Traversals of Trees, to ensure nodes are visited line-by-line.

5. Queue Application: Computer Systems Management

Speed Buffering: Resolves performance mismatches between fast central processors (CPUs) and slower external peripheral devices (e.g., printer print queues).
Resource Contention: Manages multi-user resource scheduling allocation setups fairly using first-come, first-served (FCFS) queuing schemes.

Compression Storage for Special Matrices

Array Storage Formats

Row-Major Order: Elements are stored row by row. Elements with smaller row indices are allocated first; within the same row, elements with smaller column indices are stored first.
Column-Major Order: Elements are stored column by column. Elements with smaller column indices are allocated first; within the same column, elements with smaller row indices are stored first.

Symmetric Matrices of Order $n$

A matrix featuring an upper triangle, a main diagonal, and a lower triangle where elements across the diagonal mirror each other identically ($a_{ij} = a_{ji}$).
To save space, it is compressed from a 2D array into a 1D array. An element $a_{ij}$ maps to a 1D array index $k$ (using 0-based indexing).
Index Mapping Relationships (Row-Major Lower-Triangular Target Mapping):

\[i \ge j \implies k = \frac{i(i - 1)}{2} + j - 1 \quad \text{(Lower triangle and main diagonal elements)}\] \[i < j \implies k = \frac{j(j - 1)}{2} + i - 1 \quad \text{(Upper triangle elements, mapped via symmetry to } a_{ji}\text{)}\]

Triangular Matrices of Order $n$

Includes Lower Triangular Matrices (where all elements above the main diagonal are a uniform constant) and Upper Triangular Matrices (where all elements below the main diagonal are a uniform constant).
Compressed into a 1D array to omit storing redundant constant blocks. An element $a_{ij}$ maps to a 1D array index $k$.
Index Mapping Relationships for a Lower Triangular Matrix (Row-Major):

\[i \ge j \implies k = \frac{i(i - 1)}{2} + j - 1 \quad \text{(Variable elements section)}\] \[i < j \implies k = \frac{n(n + 1)}{2} \quad \text{(Constant placeholder element located at the end of the 1D array)}\]

Data Structures: Stacks and Queues