Класс Java Stack, java.util.Stack, представляет собой классическую структуру данных стека. Вы можете поместить элементы на вершину стека и снова извлечь их, что означает чтение и удаление элементов с его вершины.
Класс фактически реализует интерфейс List, но вы редко используете его в качестве списка — за исключением, когда нужно проверить все элементы, хранящиеся в данный момент в стеке.
Обратите внимание, что класс Stack является подклассом Vector, более старого класса Java, который синхронизируется. Эта синхронизация добавляет небольшую нагрузку на вызовы ко всем методам стека. Кроме того, класс Vector использует несколько более старых (не рекомендуемых) частей Java, таких как Enumeration, который заменяется интерфейсом Iterator.Если вы хотите избежать этих проблем, вы можете использовать Deque вместо стека.
Основы
Стек — это структура данных, в которой вы добавляете элементы к «вершине» стека, а также снова удаляете элементы сверху. Это также называется принципом «первым пришел — первым вышел (LIFO)». В отличие от этого, Queue использует принцип «первым пришел — первым обслужен (FIFO)», когда элементы добавляются в конец очереди и удаляются из начала очереди.
Как создать стек в Java?
Для использования стека необходимо сначала создать экземпляр класса Stack:
Stack stack = new Stack();
Как создать с универсальным типом
Можно задать универсальный тип стека, указав тип объектов, которые может содержать экземпляр стека. Тип стека указывается при объявлении переменной стека. Вот пример:
Stack stack = new Stack();
Стек, созданный выше, может содержать только экземпляры String.
Рекомендуется использовать универсальный тип в ваших экземплярах стека, поскольку он упрощает код (не требуется преобразование при доступе к объектам в стеке) и снижает риск того, что вы поместите объект неправильного типа в стек.
Толкающий элемент
Получив экземпляр Stack, вы можете поместить элементы в верхнюю часть стека. Они должны быть объектами. Таким образом, вы фактически толкаете объекты в стек.
Stack stack = new Stack();
stack.push("1");
Этот пример помещает строку с текстом 1 в стек. Строка 1 затем сохраняется в верхней части стека.
Вытолкнутый элемент
Как только элемент помещен в стек, вы можете снова извлечь его. Как только он извлечен, удаляется из стека. В этом случае верхний элемент стека — это любой элемент, который был помещен в стек непосредственно перед тем, как элемент вытолкнулся.
Stack stack = new Stack();
stack.push("1");
String topElement = stack.pop();
Как только элемент извлечен из стека, элемент больше не присутствует в стеке.
Как увидеть верхний элемент
Класс имеет метод peek (), который позволяет увидеть верхний элемент в стеке, не удаляя его:
Stack stack = new Stack();
stack.push("1");
String topElement = stack.peek();
После запуска этого примера переменная topElement будет содержать объект String 1, который был помещен в стек непосредственно перед вызовом peek(). Объект String все еще присутствует в стеке после вызова peek().
Поиск
Вы можете искать объект, чтобы получить его индекс, используйте метод search(). Метод вызывается для каждого объекта, чтобы определить, присутствует ли искомый объект в стеке. Индекс, который вы получаете, является индексом с вершины стека, то есть верхний элемент имеет индекс 1.
Stack stack = new Stack();
stack.push("1");
stack.push("2");
stack.push("3");
int index = stack.search("3"); //index = 3
Перебор элементов
Можно выполнить итерацию элементов, получив итератор из стека с помощью метода iterator().
Stack stack = new Stack();
stack.push("123");
stack.push("456");
stack.push("789");
Iterator iterator = stack.iterator();
while(iterator.hasNext()){
Object value = iterator.next();
}
Использование потока
Также возможно обрабатывать элементы через API Stream. Вы делаете это, сначала получая его из стека с помощью метода stream().
Как только вы получили поток, можете обрабатывать элементы в потоке.
Stack stack = new Stack();
stack.push("A");
stack.push("B");
stack.push("C");
Stream stream = stack.stream();
stream.forEach((element) -> {
System.out.println(element); // print element
});
Обратите внимание, что этот пример использует Lambda в качестве параметра для метода Stream.forEach(). Лямбда просто распечатывает элемент в System.out.
Обратный список
Вы можете использовать стек для реверсирования списка. Вы делать это, перемещая все элементы из списка в стек, начиная с элемента с индексом 0, затем 1 и т. д. Каждый элемент удаляется из списка, а затем помещается в стек. После того, как все элементы находятся в стеке, вы вытаскиваете элементы один за другим и добавляете их обратно в пустой список.
List list = new ArrayList();
list.add("A");
list.add("B");
list.add("C");
System.out.println(list);
Stack stack = new Stack();
while(list.size() > 0) {
stack.push(list.remove(0));
}
while(stack.size() > 0){
list.add(stack.pop());
}
System.out.println(list);