# Stack

## Problem Description

Implement a stack data structure that follows the Last-In-First-Out (LIFO) principle.

## What is a Stack?

A stack is a linear data structure where elements are added and removed from the same end (the "top"). Like a stack of plates, you can only add or remove from the top.

## Characteristics

- **Time Complexity**: 
  - Push: O(1)
  - Pop: O(1)
  - Peek: O(1)
- **Space Complexity**: O(n) where n is number of elements
- **Access Pattern**: LIFO (Last In, First Out)
- **Implementation**: Can use array or linked list

## Core Operations

1. **Push**: Add an element to the top
2. **Pop**: Remove and return the top element
3. **Peek**: View the top element without removing it
4. **isEmpty**: Check if stack is empty
5. **size**: Get the number of elements

## Your Task

Implement the following methods in `Stack.java`:

1. `push(T element)` - Add element to top
2. `pop()` - Remove and return top element
3. `peek()` - Return top element without removing
4. `isEmpty()` - Check if empty
5. `size()` - Return number of elements

## Implementation Considerations

### Array-Based Stack
- **Pros**: Fast access, cache-friendly
- **Cons**: Fixed size (needs resizing)
- **When to resize**: When array is full

### Linked List-Based Stack
- **Pros**: Dynamic size, no resizing needed
- **Cons**: Extra memory for pointers

## Test Cases to Consider

- Push multiple elements and pop them
- Peek without removing
- Pop from empty stack (should throw exception)
- Check isEmpty on empty and non-empty stack
- Push beyond initial capacity (test resizing)
- Mixed operations

## Hints

- For array implementation: keep a `top` index
- When array is full, create new array with double capacity
- Throw `EmptyStackException` when popping/peeking empty stack
- Consider using generics for type safety

## Applications

- Function call stack (recursion)
- Undo/Redo functionality
- Expression evaluation (infix to postfix)
- Backtracking algorithms
- Browser history (back button)
- Syntax parsing
- Depth-First Search

## Common Problems Using Stacks

1. Balanced parentheses checker
2. Evaluate postfix expressions
3. Convert infix to postfix
4. Next greater element
5. Stock span problem
6. Implement queue using stacks

## Follow-up Questions

1. How would you implement a stack that supports getMin() in O(1)?
2. How would you reverse a stack using recursion?
3. How would you implement two stacks in one array?
4. Can you implement a stack that automatically keeps track of its maximum element?

## Common Pitfalls

- Not handling empty stack errors
- Array index out of bounds when not resizing
- Memory leaks (not clearing references in array implementation)
- Not updating size counter

## Edge Cases

- Operations on empty stack
- Single element stack
- Stack at capacity (for array implementation)
- Null elements (should you allow them?)

## Related Data Structures

- Queue (FIFO counterpart)
- Deque (double-ended queue)
- Priority Queue