Ранее мы уже писали свой стек с помощью одномерного массива. Однако в этой статье мы напишем реализацию стека с помощью связанного списка и напишем для него несколько юнит-тестов.
Своя реализация стека на Java
С теорией можно ознакомиться в нашей предыдущей реализации стека.
«А зачем переизобретать колесо?» — спросите вы, ведь все уже написано до нас и нужно просто уметь использовать. Абсолютно согласен с такой позицией, но для более глубокого понимания работы стека и как он устроен, часто следует писать свою реализацию. В этой реализации стека мы воспользуемся связанным списком.
Лучшие практики написания стека
Для начала хотелось бы выделить основные правила и подходы, которым я буду следовать при написании стека на Java. Естественно, это касается не только реализации на Java, ведь подходы к реализации структуры данных должны быть универсальны. Однако некоторые моменты будут в контексте Java-реализации.
Операции push, pop за постоянное время
Временная сложность для операций вставки (push) и получения (pop) должны быть O(1). Не имеет значения сколько элементов в стеке у нас будет, эти операции должны проводиться за постоянное время. Например, если мы вызываем операцию pop, то она должна вернуть последний добавленный элемент — O(1).
Избегаем печати в консоль
Методы, которые отвечают за отображение элементов списка также должны быть тестируемые. А тестирование метода, который просто печатает что-то в консоль, не совсем правильно. Вместо этого в Java-реализации можно переопределить метод toString() и работать с ним.
Универсальный стек
Вместо того, чтобы завязываться под определенный тип данных, можно сделать наш стек универсальным с использованием дженериков (родовых типов). И в качестве типа входных элементов стека использовать T.
Изобретение колеса
Когда мы пишем свою реализацию какой-то устоявшейся структуры данных, алгоритмов или шаблонов, желательно наследовать существующий подход (будь-то способ именования методов, обработки ошибок и т.д.). Для этого в Java хорошим примером является известный нам класс java.util.LinkedList.
Пишем стек с использованием связанного списка на Java
В реализации ниже используется параметризированный класс LinkedListStack, который использует внутри себя связанный список для работы с данными:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
public class LinkedListStack<T> { private final LinkedList<T> linkedList = new LinkedList<>(); public void push(T data) { linkedList.addFirst(data); } public T pop() { return linkedList.removeFirst(); } public boolean isEmpty() { return linkedList.isEmpty(); } @Override public String toString() { return linkedList.toString(); } } class LinkedList<T> { // внутренний класс, который представляет элемент списка private static class Node<T> { // данные private T data; // указатель на следующий элемент private Node<T> next; public Node(T data) { this.data = data; } @Override public String toString() { return data.toString(); } } private Node<T> first = null; // используется для push операции public void addFirst(T data) { Node<T> newFirst = new Node<T>(data); newFirst.next = first; first = newFirst; } // используется для pop операции public T removeFirst() { Node<T> oldFirst = first; first = first.next; return oldFirst.data; } @Override public String toString() { StringBuilder listBuilder = new StringBuilder(); Node currentNode = first; while (currentNode != null) { listBuilder.append(currentNode).append(","); currentNode = currentNode.next; } return listBuilder.toString(); } public boolean isEmpty() { return first == null; } } |
Из реализации видно, что у нас всего 3 класса:
LinkedList<T>— реализация связанного спискаNode<T>— внутренний класс, который представляет собой элемент спискаLinkedListStack<T>— класс с реализацией базовых операций стека. Внутри себя использует LinkedList<T> для манипуляции данными.
Теперь напишем несколько юнит-тестов для проверки операций в нашей реализации стека. Используем стандартный JUnit:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
import org.junit.Before; import org.junit.Test; import java.util.Arrays; import java.util.List; import static junit.framework.Assert.assertEquals; import static org.junit.Assert.assertFalse; import static org.junit.Assert.assertTrue; public class TestLinkedListStack { List<Integer> testData; @Before public void init() { testData = Arrays.asList(600, 1200, 1500, 2100); } @Test public void testPushPop() { LinkedListStack<Integer> stack = new LinkedListStack<>(); stack.push(1200); stack.push(1500); assertEquals("1500,1200,", stack.toString()); assertEquals(1500, (int) stack.pop()); assertEquals("1200,", stack.toString()); } @Test public void testPopIsEmpty() { LinkedListStack<Integer> stack = new LinkedListStack<>(); assertTrue(stack.isEmpty()); for (Integer value : testData) { stack.push(value); } assertFalse(stack.isEmpty()); for (int i = testData.size(); i > 0; --i) { assertEquals(testData.get(i - 1), stack.pop()); } } @Test public void testPushIsEmpty() { LinkedListStack<Integer> stack = new LinkedListStack<>(); assertTrue(stack.isEmpty()); for (Integer value : testData) { stack.push(value); } assertFalse(stack.isEmpty()); } } |
Все наши тесты проходят, реализация стека на Java — успешная.
Следите за обновлениями и учите структуры данных вместе с Javadevblog.com.
