Перейти к основному содержимому

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

· 3 мин. чтения

Задача: Наибольшая подстрока палиндром

Для заданной строки s, верните наибольшую подстроку палиндром входящую в s. Подстрока — это непрерывная непустая последовательность символов внутри строки. Стока является палиндромом, если она читается одинаково в обоих направлениях...

ANDROMEDA 42

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 .