Stack Examples

A comprehensive educational package demonstrating stack (LIFO) data structures and their practical applications in Python. This package provides multiple stack implementations, utility functions, and real-world examples with complete documentation and complexity analysis.

Features

• Multiple Stack Implementations
  • Basic Stack using Python list (efficient and practical)
  • StackTwoQueues (educational demonstration of building LIFO from FIFO)
• Utility Functions
  • Palindrome checker
  • String reversal
  • Find max/min values in stack
  • Balanced parentheses checker
  • Postfix expression evaluator
• Comprehensive Documentation with time and space complexity analysis
• Type Hints for all functions using Python 3.9+ syntax
• Full Test Coverage with pytest
• Interactive CLI for exploring stack operations
• Educational Focus with detailed explanations and examples

Installation

pip install -e .

For development with testing:

pip install -e ".[dev]"

Quick Start

Basic Stack Operations

from stack_examples import Stack

# Create a stack
stack = Stack()

# Push elements
stack.push(10)
stack.push(20)
stack.push(30)

# Peek at top element
print(stack.peek())  # 30

# Pop elements (LIFO order)
print(stack.pop())  # 30
print(stack.pop())  # 20

# Check size and emptiness
print(stack.size())  # 1
print(stack.is_empty())  # False

# Convert to list (top to bottom)
stack.push(20)
stack.push(30)
print(stack.to_list())  # [30, 20, 10]

Stack Using Two Queues

from stack_examples import StackTwoQueues

# Create stack from two queues
stack = StackTwoQueues()

# Same interface as basic stack
stack.push('A')
stack.push('B')
stack.push('C')

print(stack.pop())  # 'C' (LIFO)
print(stack.peek())  # 'B'

Palindrome Checking

from stack_examples import is_palindrome

# Check if strings are palindromes
print(is_palindrome("racecar"))  # True
print(is_palindrome("hello"))  # False

# Case-insensitive by default
print(is_palindrome("RaceCar"))  # True

# Case-sensitive checking
print(is_palindrome("RaceCar", case_sensitive=True))  # False

String Reversal

from stack_examples import reverse_string

# Reverse strings using stack
print(reverse_string("hello"))  # "olleh"
print(reverse_string("Python"))  # "nohtyP"

Finding Max/Min in Stack

from stack_examples import Stack, find_max_in_stack
from stack_examples.utils import find_min_in_stack

# Create stack with values
stack = Stack()
for val in [15, 42, -7, 23, 8]:
    stack.push(val)

# Find extremes without modifying stack
max_val = find_max_in_stack(stack)  # 42
min_val = find_min_in_stack(stack)  # -7

# Stack remains unchanged
print(stack.size())  # 5

Balanced Parentheses

from stack_examples import balanced_parentheses

# Check if brackets are balanced
print(balanced_parentheses("()"))  # True
print(balanced_parentheses("([{}])"))  # True
print(balanced_parentheses("([)]"))  # False

# Works with expressions
print(balanced_parentheses("if (x > 0) { return true; }"))  # True

Postfix Expression Evaluation

from stack_examples import evaluate_postfix

# Evaluate Reverse Polish Notation
print(evaluate_postfix("3 4 +"))  # 7.0
print(evaluate_postfix("3 4 + 2 *"))  # 14.0
print(evaluate_postfix("5 1 2 + 4 * + 3 -"))  # 14.0

Interactive Demonstrations

Run the interactive CLI to explore stack operations:

stack-demo

Or with Python:

python -m stack_examples.cli

The CLI includes:

1. Basic stack operations (push, pop, peek)
2. Stack using two queues demonstration
3. Palindrome checker examples
4. String reversal demonstrations
5. Finding max/min values
6. Balanced parentheses checker
7. Postfix expression evaluation
8. Practical applications overview
9. Complexity analysis tables

API Reference

Stack Class

Method	Description	Time	Space
__init__()	Initialize empty stack	O(1)	O(1)
push(item)	Add item to top	O(1) amortized	O(1)
pop()	Remove and return top item	O(1)	O(1)
peek()	Return top item without removing	O(1)	O(1)
is_empty()	Check if stack is empty	O(1)	O(1)
size()	Return number of elements	O(1)	O(1)
clear()	Remove all elements	O(1)	O(1)
to_list()	Convert to list (top to bottom)	O(n)	O(n)

StackTwoQueues Class

Method	Description	Time	Space
__init__()	Initialize empty stack	O(1)	O(1)
push(item)	Add item to top	O(n)	O(1)
pop()	Remove and return top item	O(1)	O(1)
peek()	Return top item without removing	O(1)	O(1)
is_empty()	Check if stack is empty	O(1)	O(1)
size()	Return number of elements	O(1)	O(1)
clear()	Remove all elements	O(1)	O(1)

Utility Functions

Function	Description	Time	Space
is_palindrome(text, case_sensitive)	Check if string is palindrome	O(n)	O(n)
reverse_string(text)	Reverse a string	O(n)	O(n)
find_max_in_stack(stack)	Find maximum value	O(n)	O(n)
find_min_in_stack(stack)	Find minimum value	O(n)	O(n)
balanced_parentheses(expr)	Check bracket balance	O(n)	O(n)
evaluate_postfix(expr)	Evaluate RPN expression	O(n)	O(n)

Where n is the number of elements or length of input.

Use Cases

Algorithm Implementation

• Expression Evaluation: Parsing and evaluating mathematical expressions
• Syntax Checking: Validating balanced brackets in code
• Postfix Conversion: Converting infix to postfix notation

Application Development

• Browser History: Back/forward button implementation
• Undo/Redo: Managing action history in applications
• Function Call Stack: Understanding program execution flow

Data Processing

• String Manipulation: Reversing and analyzing text
• Palindrome Detection: Identifying symmetrical patterns
• Stack-based Algorithms: DFS, backtracking, etc.

Educational Learning

• Data Structure Fundamentals: Understanding LIFO principle
• Stack vs Queue: Comparing LIFO and FIFO structures
• Implementation Patterns: Building stacks from other structures

Practical Applications

1. Browser History

history = Stack()
history.push("google.com")
history.push("github.com")
history.push("python.org")

# Back button
previous = history.pop()  # Returns to github.com

2. Undo Functionality

undo_stack = Stack()
redo_stack = Stack()

# Perform action
undo_stack.push("typed 'hello'")

# Undo
action = undo_stack.pop()
redo_stack.push(action)

# Redo
action = redo_stack.pop()
undo_stack.push(action)

3. Expression Validation

# Check if code has balanced brackets
code = "if (x > 0) { return arr[i]; }"
is_valid = balanced_parentheses(code)

Running Tests

Run all tests:

pytest

Run with verbose output:

pytest -v

Run with coverage:

pytest --cov=stack_examples --cov-report=html

Project Structure

stack_examples/
├── src/
│   └── stack_examples/
│       ├── __init__.py           # Package initialization and exports
│       ├── stack.py              # Basic Stack implementation
│       ├── stack_two_queues.py   # Stack using two queues
│       ├── utils.py              # Utility functions
│       └── cli.py                # Interactive demonstrations
├── tests/
│   └── test_stack_examples.py    # Comprehensive test suite
├── palindrome_and_max_value/     # Original example code (reference)
│   ├── my_stack.py
│   └── palindrome_maxvalue.py
├── stack_2_queues/               # Original example code (reference)
│   ├── Queue_PlistLR.py
│   └── stack_2_queues.py
├── pyproject.toml                # Package configuration
├── LICENSE                       # MIT License
└── README.md                     # This file

Complexity Analysis

Stack Operations

• Push: O(1) amortized - appending to Python list
• Pop: O(1) - removing from end of list
• Peek: O(1) - accessing last element
• Search: O(n) - must check all elements

StackTwoQueues Operations

• Push: O(n) - must rearrange all elements
• Pop: O(1) - dequeue from front
• Trade-off: Demonstrates concept but not practical

Utility Functions

• Palindrome Check: O(n) time, O(n) space
• String Reversal: O(n) time, O(n) space
• Find Max/Min: O(n) time, O(n) space
• Balanced Parentheses: O(n) time, O(n) space (worst case)
• Postfix Evaluation: O(n) time, O(n) space

Authorship

Authored 20 November, 2025 by Maxwell Hauser

License

This project is licensed under the MIT License - see the LICENSE file for details.