Stack

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