«1. Обзор

В этом руководстве мы обсудим, как создать стек символов в Java. Сначала мы посмотрим, как это можно сделать с помощью Java API, а затем рассмотрим некоторые пользовательские реализации.

Стек — это структура данных, которая следует принципу LIFO (Last In First Out). Вот некоторые из его распространенных методов:

    push(E item) — помещает элемент на вершину стека; возвращает объект наверху стека, не удаляя его

2. Стек символов с использованием Java API

Java имеет встроенный API с именем java.util.Stack. Поскольку char является примитивным типом данных, который нельзя использовать в дженериках, мы должны использовать класс-оболочку java.lang.Character для создания стека: 

Stack<Character> charStack = new Stack<>();

Теперь мы можем использовать push, pop и peek методы с нашим стеком.

С другой стороны, нас могут попросить создать собственную реализацию стека. Поэтому мы рассмотрим несколько различных подходов.

3. Пользовательская реализация с использованием LinkedList

Давайте реализуем стек символов, используя LinkedList в качестве внутренней структуры данных: 

public class CharStack {

    private LinkedList<Character> items;

    public CharStack() {
        this.items = new LinkedList<Character>();
    }
}

Мы создали переменную items, которая инициализируется в конструкторе.

Теперь нам нужно реализовать методы push, peek и pop: 

public void push(Character item) {
    items.push(item);
}

public Character peek() {
    return items.getFirst();
}

public Character pop() {
    Iterator<Character> iter = items.iterator();
    Character item = iter.next();
    if (item != null) {
        iter.remove();
        return item;
    }
    return null;
}

Методы push и peek используют встроенные методы LinkedList. Для pop мы сначала использовали итератор, чтобы проверить, есть ли элемент вверху или нет. Если он есть, мы удаляем элемент из списка, вызывая метод удаления.

4. Пользовательская реализация с использованием массива

Мы также можем использовать массив для нашей структуры данных: 

public class CharStackWithArray {

    private char[] elements;
    private int size;

    public CharStackWithArray() {
        size = 0;
        elements = new char[4];
    }

}

Выше мы создали массив символов, который мы инициализируем в конструкторе с начальной емкостью 4 Кроме того, у нас есть переменная размера, чтобы отслеживать, сколько записей присутствует в нашем стеке.

Теперь давайте реализуем метод push: 

public void push(char item) {
    ensureCapacity(size + 1);
    elements[size] = item;
    size++;
}

private void ensureCapacity(int newSize) {
    char newBiggerArray[];
    if (elements.length < newSize) {
        newBiggerArray = new char[elements.length * 2];
        System.arraycopy(elements, 0, newBiggerArray, 0, size);
        elements = newBiggerArray;
    }
}

Помещая элемент в стек, нам сначала нужно проверить, есть ли в нашем массиве место для его хранения. Если нет, мы создаем новый массив и удваиваем его размер. Затем мы копируем старые элементы во вновь созданный массив и присваиваем его нашей переменной elements.

Примечание: для объяснения того, почему мы хотим удвоить размер массива, а не просто увеличить размер на единицу, обратитесь к этому сообщению StackOverflow.

Наконец, давайте реализуем методы peek и pop: 

public char peek() {
    if (size == 0) {
        throw new EmptyStackException();
    }
    return elements[size - 1];
}

public char pop() {
    if (size == 0) {
        throw new EmptyStackException();
    }
    return elements[--size];
}

Для обоих методов, после проверки того, что стек не пуст, мы возвращаем элемент с размером позиции – 1. Для pop, в дополнение к возвращая элемент, мы уменьшаем размер на 1.

5. Заключение

В этой статье мы узнали, как создать стек символов с помощью Java API, и мы увидели пару пользовательских реализаций.

Код, представленный в этой статье, доступен на GitHub.