Stack

A Stack is a linear data structure in which all element insertions and deletions are restricted to a single end, universally referred to as the TOP of the stack. It operates strictly under the LIFO (Last-In, First-Out) or FILO (First-In, Last-Out) access discipline.

Core Primitive Operations:

• `push(item)`: Inserts a new element at the TOP of the stack. Increments stack size.
• `pop()`: Removes and returns the element currently residing at the TOP of the stack. Decrements stack size. If the stack is empty, triggers Stack Underflow.
• `peek()` / `top()`: Returns the value of the top element *without* removing it. Triggers Underflow if the stack is empty.
• `isEmpty()`: Boolean predicate returning `True` if the stack contains zero elements, `False` otherwise.

Stack Boundary Conditions:

• Stack Underflow: An error condition that occurs when an algorithm attempts to execute a `pop()` or `peek()` operation on a stack that contains no elements (`isEmpty() == True`).
• Stack Overflow: An error condition that occurs in a bounded, fixed-capacity stack when a `push()` is attempted on an already full stack. (Note: Dynamic Python lists grow automatically, so overflow occurs only when physical system memory is exhausted or recursive recursion limits are exceeded).

In Python, a stack is natively implemented using a standard dynamic list where the end of the list (`lst[-1]`) acts as the TOP of the stack because `append()` and `pop()` operate at the end in $O(1)$ constant amortized time:

# Production-Grade Stack Implementation:
def create_stack():
    return []

def isEmpty(stack):
    return len(stack) == 0

def push(stack, item):
    stack.append(item)
    print(f"Pushed: {item} | Current Stack: {stack}")

def pop(stack):
    if isEmpty(stack):
        print("Stack Underflow Error: Cannot pop from an empty stack!")
        return None
    removed_item = stack.pop()
    print(f"Popped: {removed_item} | Remaining Stack: {stack}")
    return removed_item

def peek(stack):
    if isEmpty(stack):
        print("Stack Underflow: Stack is empty!")
        return None
    return stack[-1]

# Demonstration:
stk = create_stack()
push(stk, 10)
push(stk, 20)
push(stk, 30)
print("Top element is:", peek(stk))  # 30
pop(stk)                             # Removes 30
pop(stk)                             # Removes 20
pop(stk)                             # Removes 10
pop(stk)                             # Stack Underflow Error!

A. String Reversal

To reverse a string $S$, push all characters sequentially onto a stack, then pop them one by one. Because of LIFO, the characters emerge in reverse order ($O(n)$ time complexity).

B. Balanced Parentheses Checking

Compilers verify syntax balance (e.g., in math or code) using a stack:

• Scan the expression character by character from left to right.
• Whenever an opening bracket (`(`, `{`, `[`) is encountered, push it onto the stack.
• Whenever a closing bracket (`)`, `}`, `]`) is encountered:
  • If the stack is empty, report Unbalanced (closing bracket with no matching opener).
  • Else, pop the top bracket and verify if it matches the current closing bracket. If mismatched, report Unbalanced.
• At the end of the string, if the stack is completely empty, the expression is Balanced; otherwise, unbalanced.