Определение стека символов в Java

1. Обзор

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

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

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

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 .