Implement a Generic Stack in Java

Problem Implement a generic, type-parameterized Stack<T> in Java from scratch — no use of the built-in java.util.Stack or Deque.

Requirements

• void push(T item) — add to the top
• T pop() — remove and return the top; defined behaviour when empty
• T peek() — return the top without removing
• boolean isEmpty() and int size()
• All core operations in O(1) amortized time

Core design

• Two backing choices, both valid:
  • Array-backed: an Object[] cast to T[] (generic arrays can't be created directly), with top as the index of the next free slot. Fixed capacity means push must handle overflow; a growable version doubles capacity on full, giving O(1) amortized push.
  • Linked-list-backed: a private Node<T> { T value; Node<T> next; } with head as the top. push prepends, pop unlinks the head. Truly O(1) per operation, no resize, at the cost of a node allocation and pointer chasing per element.
• Empty-stack handling: throw EmptyStackException / NoSuchElementException to mirror the JDK, or return Optional<T> for a total API. Pick one and be consistent across pop and peek.
• Null the popped slot in the array version (arr[--top] = null) so the stack does not hold a stale strong reference and leak the object.

Discussion points

• Generics erasure: why new T[n] is illegal, why (T[]) new Object[n] triggers an unchecked-cast warning, and where @SuppressWarnings legitimately belongs.
• Trade-off: array gives cache locality and lower per-element overhead; linked list gives worst-case O(1) push and no resize copy spike.
• Growth policy: doubling vs. fixed increment, and why doubling is what makes amortized O(1) hold. Consider shrinking on heavy pop to avoid unbounded retention.
• Concurrency: the class is not thread-safe. Discuss synchronizing methods, a lock-free CAS stack on the head pointer, and the ABA problem it introduces.
• Extension: implement Iterable<T> (top-to-bottom order), and decide whether iteration should be fail-fast via a modCount.