Как реализовать упрощённый стек

Что проверяют

Базовое владение Java: массивы, дженерики, исключения и асимптотика. Задача простая, поэтому оценивают детали: что происходит при переполнении, нет ли утечки памяти, что вы выбрали бы в боевом коде. Следом часто просят стек с получением минимума за O(1).

Как отвечать

Покажите реализацию на массиве и проговорите решения:

• дженерик: class ArrayStack<T> с полем Object[] elements и приведением (T) в pop и peek. Массив T[] в Java напрямую не создать из-за стирания типов;
• рост: при заполнении массив увеличивается через Arrays.copyOf(elements, elements.length * 2). Тогда push работает за амортизированное O(1), а искусственного предела вместимости нет;
• обнуление ячейки: в pop после чтения пишите elements[--size] = null. Иначе ссылка остаётся в массиве, и сборщик мусора не освободит объект, пока ячейку не перезапишут;
• пустой стек: pop и peek бросают EmptyStackException или NoSuchElementException, это привычные контракты коллекций;
• имя: не называйте класс Stack, иначе он конфликтует с java.util.Stack при импорте.

Альтернатива на связном списке: узел хранит значение и ссылку на следующий, push и pop меняют голову. Честное O(1) без копирования, но лишний объект на каждый элемент и хуже локальность в кэше процессора.

Закончите тем, что в продакшене своя реализация не нужна. java.util.Stack устарел: он наследует Vector с синхронизацией на каждом методе. Документация Deque прямо рекомендует его вместо Stack, обычно это ArrayDeque с методами push, pop, peek. Учтите, что ArrayDeque не принимает null.

Где спотыкаются

Бросают StackOverflowError при переполнении. Это Error виртуальной машины про переполнение стека вызовов потока, его не бросают из прикладного кода. Для фиксированной вместимости подходит IllegalStateException.

Забывают обнулить ячейку при pop. Это классическая утечка из «Effective Java», и интервьюеры её любят.

Возвращают -1 или 0 из pop на пустом стеке для int. Так пустоту не отличить от настоящего значения, и ошибка всплывает далеко от места, где стек опустел.