Избранное сообщение

Фетісов В. С. Комп’ютерні технології в тестуванні. Навчально-методичний посібник. 2-ге видання, перероблене та доповнене / Мои публикации

В 10-х годах я принимал участие в программе Европейского Союза Tempus "Освітні вимірювання, адаптовані до стандартів ЄС". В рамк...

Благодаря Интернету количество писателей и поэтов увеличивается в геометрической прогрессии. Поголовье читателей начинает заметно отставать.

вторник, 7 марта 2017 г.

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

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

Своя реализация стека на 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.

Смотри также:

Автор: на

Комментариев нет:

Отправить комментарий