Advanced Study Notes: Linear Data

Structures & Recursion

STACKS, QUEUES, DEQUEUES, AND RECURSIVE PRINCIPLES

1. Stack: Definition & Implementations

A Stack is an abstract linear data structure operating under the strict LIFO (Last-In, First-Out) paradigm. The
structural behavior mandates that elements can only be inserted or retrieved from a single operational point
designated as the Top.

Core Operations

• Push: Places an element onto the top of the stack.

• Pop: Removes and returns the topmost element. Triggers an underflow condition if the structure is empty.

• Peek / Top: Inspects and references the top element without mutating the structure.

• isEmpty: Returns a boolean evaluation checking if the stack contains zero elements.

• isFull: Validates if static memory allocations have reached maximum capacity.

Array-Based Implementation

In a continuous sequence array implementation, a fixed-capacity buffer holds the data segments while an
index pointer top traces the topmost active boundary. The initial state is systematically represented by setting
top = -1.

• Advantages: Access velocities are fixed at deterministic O(1) time complexities with minimal raw memory
footprint overhead.

• Limitations: Subject to physical static allocation limits, presenting inherent structural risks of Stack
Overflow or memory inefficiencies.

Data Structures & Algorithms Study Notes 1

 class ArrayStack:
def __init__(self, capacity):
[Link] = capacity
[Link] = [None] * capacity
[Link] = -1

def push(self, item):

if [Link] == [Link] - 1:
raise OverflowError("Stack Overflow Condition")
[Link] += 1
[Link][[Link]] = item

def pop(self):
if [Link] == -1:
raise IndexError("Stack Underflow Condition")
item = [Link][[Link]]
[Link] -= 1
return item

Linked List Implementation

Dynamic configuration uses isolated dynamic nodes where the top pointer points to the head node of the
linked sequence. Each element explicitly routes to its successor via a dynamic reference pointer.

• Advantages: Continuous dynamic scaling properties; memory allocations scale reactively to execution
demands.

• Limitations: Imposes dynamic structural pointer overhead and unpredictable memory fragmentation
allocations.

class Node:
def __init__(self, data):
[Link] = data
[Link] = None

class LinkedListStack:
def __init__(self):
[Link] = None

def push(self, item):

new_node = Node(item)
new_node.next = [Link]
[Link] = new_node

def pop(self):
if [Link] is None:
raise IndexError("Stack Underflow Condition")
item = [Link]
[Link] = [Link]
return item

Data Structures & Algorithms Study Notes 2

 2. Applications of Stack

Infix to Postfix Conversion

Compilers leverage Postfix (Reverse Polish) notation to systematically process mathematical syntax without
relying on expensive parentheses logic or continuous operator backtracking. Operators follow their
corresponding operands.

Operator Precedence & Associativity Matrix

• ^ (Exponentiation): Maximum Priority Level, Right-to-Left evaluation.

• *, / (Multiplicative operations): Intermediate Priority Level, Left-to-Right evaluation.

• +, - (Additive operations): Baseline Priority Level, Left-to-Right evaluation.

Algorithmic Mechanics

1. Scan the linear infix expression string progressively from left to right.

2. If an operand is discovered, append it directly to the outgoing string.

3. If an open parenthesis '(' is encountered, immediate push operations route it onto the structural stack.

4. If a close parenthesis ')' is found, pop iteratively and append to the output string until the corresponding
open parenthesis is exposed. Evict and discard the matching parenthesis.

5. If an operator is processed:
◦ While the stack remains active and the element residing at the top possesses a greater or equivalent
precedence value to the scanned token, pop and append to the output string.

◦ Subsequently, push the scanned operator onto the stack.

6. Upon reaching the end of the input string, clear the remaining operational stack nodes, appending each to
the output.

Example Processing Sequence: A + B * C

• Scan A → Output: A

• Scan + → Stack: [+]

• Scan B → Output: A B

• Scan * → Stack: [+, *] (Since priority of * is greater than +)

• Scan C → Output: A B C

• End reached → Flush Stack → Final String: A B C * +

Data Structures & Algorithms Study Notes 3

Postfix Evaluation

To evaluate mathematical suffixes, operands are buffered in a temporary data stack until an evaluation
operator is processed.

Algorithmic Mechanics

1. Parse the expression tokens from left to right.

2. Upon identifying an operand, pass it to the stack buffer.

3. Upon identifying an operator, execute a dual pop operation sequence:

◦ The absolute first popped token defines Operand 2 (op2).

◦ The following secondary popped token defines Operand 1 (op1).

◦ Compute the expression value: op1 [operator] op2.

◦ Push the resultant value back onto the processing stack.

4. The remaining element on the stack is the final result.

Critical Operational Warning: Evaluation sequence correctness relies on proper operand order. Non-
commutative computations like division (/) or subtraction (-) require that the first value popped from the
stack constitutes the right side of the operational expression.

3. Recursion

Recursion is an algorithmic strategy where a function invokes itself to break a problem down into smaller,
manageable sub-problems.

Structural Mechanics

1. Base Case: A fixed conditional check that stops further recursive cycles and initiates stack unwinding.

2. Recursive Case: A execution path that invokes the selfsame function with altered parameters that
progressively approach the base condition.

The Call Stack & Activation Records

Every dynamic recursive execution cycle generates an explicit Activation Record (Stack Frame) allocated
directly onto the system's runtime Call Stack. Each individual frame retains dedicated blocks for internal local
scope tracking, dynamic input arguments, and the precise return address pointer. If code paths lack definitive
base case resolution or overflow safety thresholds, execution environments crash via a Stack Overflow.

Data Structures & Algorithms Study Notes 4

Tail Recursion and Optimization

A function is defined as strictly tail-recursive if the recursive call represents the absolute final evaluation
instruction step of that context loop. No deferred mathematical computation or state restoration actions can
follow the self-invocation path.

# Non-Tail Recursive Structure

def standard_factorial(n):
if n == 1: return 1
return n * standard_factorial(n - 1) # Deferred multiplication occurs after call
returns

# Tail-Recursive Structure
def optimized_factorial(n, accumulator=1):
if n == 1: return accumulator
return optimized_factorial(n - 1, n * accumulator) # Immediate final execution call

Modern production compilers leverage Tail Call Optimization (TCO) to overwrite active stack frames instead
of appending new ones. This optimization reduces runtime space complexities from O(n) down to a flat space
coefficient of O(1).

Tower of Hanoi Mathematical Puzzle

The objective is to relocate n distinct, sorted disks across three discrete physical rods: Source (A), Destination
(C), and Auxiliary (B), keeping larger disks below smaller ones at all times.

Algorithmic Strategy:

1. Relocate the upper n - 1 elements from Source (A) to Auxiliary (B), using Destination (C) as temporary
storage.

2. Transfer the single largest base disk directly from Source (A) to Destination (C).

3. Relocate the n - 1 suspended elements from Auxiliary (B) to Destination (C), using Source (A) as
temporary storage.

def tower_of_hanoi(n, source, destination, auxiliary):

if n == 1:
print(f"Move disk 1 from {source} to {destination}")
return
tower_of_hanoi(n - 1, source, auxiliary, destination)
print(f"Move disk {n} from {source} to {destination}")
tower_of_hanoi(n - 1, auxiliary, destination, source)

• Time Complexity: O(2^n) — exponential growth scale profiles.

• Space Complexity: O(n) — dictated by maximum active frame depth.

Data Structures & Algorithms Study Notes 5

 4. Queue: Definition & Architecture Models

A Queue is an abstract linear structure enforcing a strict FIFO (First-In, First-Out) order. Items append
exclusively via the Rear boundary and vacate via the Front boundary.

Array-Based Architectures

1. Physical / Linear Shifting Model

The front point remains permanently anchored to array index 0. While insertions at the trailing edge achieve
O(1) speeds, data element extractions require a full structural left-shift of all remaining items, dropping
extraction efficiencies to a costly O(n) loop.

2. Floating Pointer Linear Model

To eliminate shifting overhead, independent tracking variables track both front and rear boundaries. However,
as pointers advance through operations, they eventually hit the array's physical storage limit. This creates a
False Overflow state, where the queue reports it is full despite having unused memory slots at the front.

3. Circular Model Optimization

The circular structure addresses false overflows by using modular arithmetic to wrap the trailing edge back to
the beginning index, treating the storage array as an continuous loop.

index_{next} = (index_{current} + 1) \pmod{capacity}

Data Structures & Algorithms Study Notes 6

 class CircularQueue:
def __init__(self, capacity):
[Link] = capacity
[Link] = [None] * capacity
[Link] = [Link] = -1

def is_full(self):
return ([Link] + 1) % [Link] == [Link]

def is_empty(self):
return [Link] == -1

def enqueue(self, item):

if self.is_full(): raise OverflowError("Queue Overflow")
if self.is_empty(): [Link] = 0
[Link] = ([Link] + 1) % [Link]
[Link][[Link]] = item

def dequeue(self):
if self.is_empty(): raise IndexError("Queue Underflow")
item = [Link][[Link]]
if [Link] == [Link]:
[Link] = [Link] = -1
else:
[Link] = ([Link] + 1) % [Link]
return item

Linked List Queue Implementation

Maintains explicit references to both the head node (front) and the tail node (rear). Enqueue operations
append to the tail node, and dequeue operations advance the head pointer, ensuring optimal efficiency.

class LinkedListQueue:
def __init__(self):
[Link] = [Link] = None

def enqueue(self, item):

new_node = Node(item)
if [Link] is None:
[Link] = [Link] = new_node
return
[Link] = new_node
[Link] = new_node

def dequeue(self):
if [Link] is None: raise IndexError("Queue Underflow")
item = [Link]
[Link] = [Link]
if [Link] is None: [Link] = None
return item

Data Structures & Algorithms Study Notes 7

 5. Dequeue (Double-Ended Queue)

A Dequeue (Double-Ended Queue) extends standard queue behaviors by allowing insertion and deletion
operations at both the Front and Rear boundaries.

Structural Variances

Variant Model Permitted Input Points Permitted Output Points

Single designated boundary (Rear

Input-Restricted Dequeue Dual boundaries (Both Front & Rear)
only)

Output-Restricted Single designated boundary (Front

Dual boundaries (Both Front & Rear)
Dequeue only)

6. Comparative Architectural Matrix

Structure Governing Insertion Time Deletion Time

Primary System Use Case
Type Logic Complexity Complexity

Call Stack Parsing,

Stack LIFO O(1) O(1)
Expression Undo Engine

Queue CPU Core Scheduling, IO

FIFO O(1) O(1)
(Circular) Buffering Pipelines

Flexible Edge Sliding Window Optimization,

Dequeue O(1) O(1)
Access Web Browser History

Data Structures & Algorithms Study Notes 8