Стек с помощью связанного списка на Java

Стек с использованием связанного списка на Java

LinkedListStackРанее мы уже писали свой стек с помощью одномерного массива. Однако в этой статье мы напишем реализацию стека с помощью связанного списка и напишем для него несколько юнит-тестов.

Своя реализация стека на Java

С теорией можно ознакомиться в нашей предыдущей реализации стека.

«А зачем переизобретать колесо?» — спросите вы, ведь все уже написано до нас и нужно просто уметь использовать. Абсолютно согласен с такой позицией, но для более глубокого понимания работы стека и как он устроен, часто следует писать свою реализацию. В этой реализации стека мы воспользуемся связанным списком.

Лучшие практики написания стека

Для начала хотелось бы выделить основные правила и подходы, которым я буду следовать при написании стека на Java. Естественно, это касается не только реализации на Java, ведь подходы к реализации структуры данных должны быть универсальны. Однако некоторые моменты будут в контексте Java-реализации.

Операции push, pop за постоянное время

Временная сложность для операций вставки (push) и получения (pop) должны быть O(1)Не имеет значения сколько элементов в стеке у нас будет, эти операции должны проводиться за постоянное время. Например, если мы вызываем операцию pop, то она должна вернуть последний добавленный элемент — O(1).

Избегаем печати в консоль

Методы, которые отвечают за отображение элементов списка также должны быть тестируемые. А тестирование метода, который просто печатает что-то в консоль, не совсем правильно. Вместо этого в Java-реализации можно переопределить метод toString() и работать с ним.

Универсальный стек

Вместо того, чтобы завязываться под определенный тип данных, можно сделать наш стек универсальным с использованием дженериков (родовых типов). И в качестве типа входных элементов стека использовать T.

Изобретение колеса

Когда мы пишем свою реализацию какой-то устоявшейся структуры данных, алгоритмов или шаблонов, желательно наследовать существующий подход (будь-то способ именования методов, обработки ошибок и т.д.). Для этого в Java хорошим примером является известный нам класс java.util.LinkedList.

Пишем стек с использованием связанного списка на Java

В реализации ниже используется параметризированный класс LinkedListStack, который использует внутри себя связанный список для работы с данными:

Из реализации видно, что у нас всего 3 класса:

  • LinkedList<T> — реализация связанного списка
  • Node<T>внутренний класс, который представляет собой элемент списка
  • LinkedListStack<T> — класс с реализацией базовых операций стека. Внутри себя использует LinkedList<T> для манипуляции данными.

Теперь напишем несколько юнит-тестов для проверки операций в нашей реализации стека. Используем стандартный JUnit:

Все наши тесты проходят, реализация стека на Java — успешная.

Следите за обновлениями и учите структуры данных вместе с Javadevblog.com.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *