Для новичков с помощью ArrayList
Стек - одна из самых простых структур данных для понимания. Если у вас есть структуры данных в вашем научном сообществе, вы уже знаете, что это значит. Это простая очередь "последним вошел - первым ушел" (LIFO). Это означает, что последний элемент, который войдет в стек, будет первым элементом, который выйдет из стека. Давайте сначала попробуем понять концепцию с помощью нескольких иллюстраций.
Концепт
Предположим, у нас есть пустой контейнер, который выглядит как контейнер, показанный на изображении ниже:
Это довольно просто понять. Теперь предположим снова, что мы «проталкиваем» строку со значением «строка1» в этот пустой стек. Стек теперь выглядит так:
Это снова довольно просто понять. Значение, которое мы поместили в стек, переходит и располагается в самом низу стека. Теперь поместим в стек еще две строки со значениями «строка2» и «строка3». После этого стек будет выглядеть как на иллюстрации ниже.
Что произойдет, если мы вытолкнем элемент из стека? Итак, элемент наверху стека удаляется из стека и возвращается. Итак, после того, как мы извлекаем элемент из воображаемого стека, наш стек выглядит так:
Что такое ЛИФО?
Теперь нам нужно понять, какой элемент попал в стек первым, а какой - первым, поскольку это очередь LIFO. Представьте пустой стек как таблицу, а строковые значения, которые мы вставляли, как набор тарелок. Мы начали складывать эти тарелки одна на другую. Таким образом, первая тарелка, которую мы поместили на стол, находится в самом низу стопки, а последняя тарелка, которую мы поместили, находится наверху стопки. И когда вы хотите, чтобы на тарелке был сервирован тот потрясающий бутерброд, который вы сделали другу, вы возьмете тарелку вверху стопки, а не вытащите тарелку из нижней части стопки. Это то, что означает «последний пришел - первым ушел». Последняя пластина, которая попадет в стопку, будет первой пластиной, которая выйдет из стопки. Я попытался проиллюстрировать эту концепцию изображением ниже.
Процесс добавления тарелки в стопку называется «выталкиванием», а извлечение тарелки из стопки - «выталкиванием» из стопки. Таким образом, вы помещаете элемент в стек и выталкиваете элемент из стека. Теперь, когда мы знаем, что такое стек и как он работает, давайте посмотрим код на Java, чтобы понять, как мы можем реализовать эту концепцию.
Код
Для простоты я использую ArrayList в классе реализации стека, который остается частным для этого класса. Но когда вы пишете готовый к производству код, вам нужно реализовать интерфейс Collection ‹E› и переопределить все методы там, чтобы обеспечить все функции стека. Другой, и, как некоторые утверждают, лучший способ реализации стека - это использование специальной реализации класса LinkedList. Дайте мне знать, если вы хотите, чтобы я написал POC и для этого. Но внутреннего использования ArrayList достаточно для понимания концепции.
Для начала нам нужно создать класс реализации стека, который позволяет нам вставлять в него элементы, извлекать из него элементы и сохранять все элементы, которые мы вставляем в него. Я называю этот класс StackImpl, почему бы и нет? Поскольку мы пишем этот код на Java, нам нужно позаботиться о типах элементов, которые мы собираемся в нем хранить. Если мы создадим стек строк и в будущем захотим сохранить в стеке некоторые целочисленные значения, нам придется написать другую реализацию стека. Это большая работа. Так что избегайте этого дублирования кода, мы заставим нашу реализацию стека решать, какой тип данных хранить во время выполнения. Этого легко добиться с помощью универсального класса Java под названием T. Если мы используем это в нашей реализации, мы можем использовать этот класс стека практически с любыми типами данных, которые мы хотим складывать. Мы можем объявить наш класс с помощью этого универсального класса следующим образом:
class StackImpl<T> {
}
Как я уже упоминал, мы будем использовать ArrayList внутри типа T для поддержки наших элементов данных. Для готового к производству кода я предлагаю вам реализовать интерфейс Collection ‹E› или написать его, используя собственную реализацию LinkedList. А пока давайте объявим, что ArrayList:
// Creating a private array list of the generic T class. private List<T> list = new ArrayList<T>();
Теперь нам нужен способ помещать элементы в наш стек. Поскольку у нас есть ArrayList для внутреннего хранения наших элементов, мы просто добавляем элементы в этот список. Итак, наш метод «push» выглядит так:
void push(T value) {
list.add(value);
}
Это было просто. Здесь нам не нужно заботиться о большом количестве пожаров, потому что мы используем ArrayList для внутренних целей. В любом случае, теперь нам нужен метод для извлечения элементов из списка. Для этого напишем следующий метод pop ():
T pop() {
return this.list.get(this.list.size() — 1);
}
Но ждать! Это обязательно вернет последний элемент стека, но не удалит элемент из стека. Так что в следующий раз, когда мы откроем другой элемент, мы фактически получим тот же элемент. Это будет продолжаться до бесконечности. Поэтому всякий раз, когда мы извлекаем элемент из стека, мы также должны удалить этот элемент из ArrayList. Итак, давайте изменим наш метод pop (), чтобы справиться с этим:
T pop() {
// Getting the last value from the list.
T value = this.list.get(this.list.size() - 1);
// Removing the last value from the list,
// thereby popping the last value.
this.list.remove(this.list.size() - 1);
return value;
}
Хорошо, это должно сработать. Но подождите, еще раз! Что, если в стопке ничего нет и мы пытаемся что-то из нее извлечь? Что ж, мы тоже должны с этим справиться. Есть много способов справиться с этим, в зависимости от контекста проекта. В этом примере мы просто выбросим исключение. Но для этого нам сначала нужно создать класс исключения. Это довольно просто: просто создайте новый класс, расширите класс Exception и добавьте конструктор. Я называю это классом StackEmptyException, потому что опять же, почему бы и нет?
public class StackEmptyException extends Exception {
public StackEmptyException(String message) {
super(message);
}
}
Теперь нам нужно снова изменить наш метод pop (), чтобы вызвать это исключение. Итак, давайте сделаем это сейчас:
T pop() throws StackEmptyException {
// Throwing an exception if the list is empty.
if (this.list.isEmpty()) {
throw new StackEmptyException("The stack is empty. Push a value before popping it.");
}
// Getting the last value from the list.
T value = this.list.get(this.list.size() - 1);
// Removing the last value from the list, thereby popping the last value.
this.list.remove(this.list.size() - 1);
return value;
}
Это больше походит на это. И просто для удовольствия мы добавим метод, который возвращает размер нашего стека, который указывает количество элементов, которые у нас есть в стеке. Это тоже довольно простой метод:
public long size() {
return this.list.size();
}
И снова, чтобы повеселиться, мы напишем еще один метод, который вернет все элементы в нашем стеке в виде списка и полностью опустошит стек. Это может пригодиться, когда мы хотим использовать один и тот же стек для некоторых промежуточных результатов в середине обработки, но хотим восстановить стек с нашими фактическими значениями после завершения промежуточной обработки. Мы назовем этот метод методом getStackAndEmpty ():
List<T> getStackAndEmpty() {
List<T> stack = new ArrayList<T>(this.list);
this.list.removeAll(stack);
return stack;
}
И если мы хотим очистить стек, потерять все значения в стеке и восстановить стек, у нас также может быть метод flush ():
void flush() {
this.list = new ArrayList<>();
}
Это тоже довольно простой метод, мы просто переназначаем новый ArrayList нашей переменной частного списка. Мы закончили с нашей реализацией собственного стека. Полная реализация этого класса выглядит так:
class StackImpl<T> {
// Creating a private array list of the generic T class.
private List<T> list = new ArrayList<T>();
public long size() {
return this.list.size();
}
void push(T value) {
list.add(value);
}
T pop() throws StackEmptyException {
// Throwing an exception if the list is empty.
if (this.list.isEmpty()) {
throw new StackEmptyException("The stack is empty. Push a value before popping it.");
}
// Getting the last value from the list.
T value = this.list.get(this.list.size() - 1);
// Removing the last value from the list, thereby popping the last value.
this.list.remove(this.list.size() - 1);
return value;
}
List<T> getStackAndEmpty() {
List<T> stack = new ArrayList<T>(this.list);
this.list.removeAll(stack);
return stack;
}
void flush() {
this.list = new ArrayList<>();
}
}
Далее нам нужно увидеть этот стек в действии. Для этого создадим стопку строк:
StackImpl<String> stack = new StackImpl<String>();
Теперь поместим в стек пару элементов:
stack.push("First");
stack.push("Second");
Итак, теперь у нас должно быть два элемента в стеке. Мы можем использовать метод pop (), чтобы извлечь элемент из стека и проверить значение, чтобы увидеть, действительно ли мы следуем LIFO в нашей реализации:
String value = stack.pop();
System.out.println("Popped value: " + value);
Для этого мы должны получить следующий результат:
Popped value: Second
Итак, мы вытащили последний элемент, который попал в массив. У нас может быть еще несколько таких тестов:
StackImpl<String> stack = new StackImpl<String>();
stack.push("First");
stack.push("Second");
String value = stack.pop();
System.out.println("Popped value: " + value);
stack.push("Third");
List<String> completeStack = stack.getStackAndEmpty();
System.out.println("Complete stack: " + completeStack);
stack.push("First");
stack.push("Second");
long stackSize = stack.size();
System.out.println("Stack size before flush: " + stackSize);
stack.flush();
stackSize = stack.size();
System.out.println("Stack size after flush: " + stackSize);
String lastValue = stack.pop();
Мы можем использовать тот же класс StackImpl для целочисленного стека. И код очень похож на стек строк:
StackImpl<Integer> stack = new StackImpl<Integer>();
stack.push(100);
stack.push(200);
Integer value = stack.pop();
System.out.println("Popped value: " + value);
stack.push(300);
List<Integer> completeStack = stack.getStackAndEmpty();
System.out.println("Complete stack: " + completeStack);
stack.push(100);
stack.push(200);
long stackSize = stack.size();
System.out.println("Stack size before flush: " + stackSize);
stack.flush();
stackSize = stack.size();
System.out.println("Stack size after flush: " + stackSize);
Integer lastValue = stack.pop();
Я написал эту часть кода в своем основном классе. Полный класс выглядит так:
public class App {
public static void main(String[] args) {
stringStackExample();
integerStackExample();
}
private static void integerStackExample() {
try {
StackImpl<Integer> stack = new StackImpl<Integer>();
stack.push(100);
stack.push(200);
Integer value = stack.pop();
System.out.println("Popped value: " + value);
stack.push(300);
List<Integer> completeStack = stack.getStackAndEmpty();
System.out.println("Complete stack: " + completeStack);
stack.push(100);
stack.push(200);
long stackSize = stack.size();
System.out.println("Stack size before flush: " + stackSize);
stack.flush();
stackSize = stack.size();
System.out.println("Stack size after flush: " + stackSize);
Integer lastValue = stack.pop();
} catch (StackEmptyException e) {
System.out.println("Error: " + e.getMessage());
}
}
private static void stringStackExample() {
try {
StackImpl<String> stack = new StackImpl<String>();
stack.push("First");
stack.push("Second");
String value = stack.pop();
System.out.println("Popped value: " + value);
stack.push("Third");
List<String> completeStack = stack.getStackAndEmpty();
System.out.println("Complete stack: " + completeStack);
stack.push("First");
stack.push("Second");
long stackSize = stack.size();
System.out.println("Stack size before flush: " + stackSize);
stack.flush();
stackSize = stack.size();
System.out.println("Stack size after flush: " + stackSize);
String lastValue = stack.pop();
} catch (StackEmptyException e) {
System.out.println("Error: " + e.getMessage());
}
}
}
Это должно быть довольно легко понять, но я могу ошибаться. Сообщите мне, если пример или объяснение непонятны. Я постараюсь объяснить это получше. И опять же, это уже готовый к производству код. Это написано только для понимания концепции.
А если вы хотите сразу перейти к проекту, вы можете клонировать POC проекта Maven из моего репозитория Github.
Следуйте за мной в Twitter, чтобы узнать больше о Data Science, Machine Learning и общих технических новостях. Также вы можете следить за моим личным блогом.
