1. Обзор
В этой быстрой статье мы познакомимся с классом java.util.Stack и начнем рассматривать, как мы можем его использовать.
Стек — это универсальная структура данных, которая представляет набор объектов в порядке LIFO (последним пришел — первым вышел), что позволяет помещать/извлекать элементы за постоянное время .
Для новых реализаций мы должны отдавать предпочтение интерфейсу Deque и его реализациям . Deque определяет более полный и непротиворечивый набор операций LIFO. Однако нам все еще может понадобиться иметь дело с классом Stack , особенно в устаревшем коде, поэтому важно хорошо его понимать.
2. Создайте стек
Начнем с создания пустого экземпляра Stack с помощью стандартного конструктора без аргументов:
@Test
public void whenStackIsCreated_thenItHasSizeZero() {
Stack<Integer> intStack = new Stack<>();
assertEquals(0, intStack.size());
}
Это создаст стек с емкостью по умолчанию 10. Если количество добавленных элементов превышает общий размер стека , он будет автоматически удвоен. Однако его размер никогда не уменьшится после удаления элементов.
3. Синхронизация для стека
Stack является прямым подклассом Vector ; это означает, что, как и его суперкласс, это синхронизированная реализация.
Однако синхронизация нужна не всегда, в таких случаях рекомендуется использовать ArrayDeque .
4. Добавить в стек
Начнем с добавления элемента в начало стека с помощью метода push() , который также возвращает добавленный элемент:
@Test
public void whenElementIsPushed_thenStackSizeIsIncreased() {
Stack<Integer> intStack = new Stack<>();
intStack.push(1);
assertEquals(1, intStack.size());
}
Использование метода push() имеет тот же эффект, что и использование addElement(). Единственное отличие состоит в том, что addElement() возвращает результат операции, а не добавленный элемент.
Мы также можем добавить несколько элементов одновременно:
@Test
public void whenMultipleElementsArePushed_thenStackSizeIsIncreased() {
Stack<Integer> intStack = new Stack<>();
List<Integer> intList = Arrays.asList(1, 2, 3, 4, 5, 6, 7);
boolean result = intStack.addAll(intList);
assertTrue(result);
assertEquals(7, intList.size());
}
5. Получить из стека
Далее давайте посмотрим, как получить и удалить последний элемент в стеке :
@Test
public void whenElementIsPoppedFromStack_thenElementIsRemovedAndSizeChanges() {
Stack<Integer> intStack = new Stack<>();
intStack.push(5);
Integer element = intStack.pop();
assertEquals(Integer.valueOf(5), element);
assertTrue(intStack.isEmpty());
}
Мы также можем получить последний элемент стека S, не удаляя его:
@Test
public void whenElementIsPeeked_thenElementIsNotRemovedAndSizeDoesNotChange() {
Stack<Integer> intStack = new Stack<>();
intStack.push(5);
Integer element = intStack.peek();
assertEquals(Integer.valueOf(5), element);
assertEquals(1, intStack.search(5));
assertEquals(1, intStack.size());
}
6. Поиск элемента в стеке
6.1. Поиск
Стек позволяет нам искать элемент `` и получать его расстояние от вершины:
@Test
public void whenElementIsOnStack_thenSearchReturnsItsDistanceFromTheTop() {
Stack<Integer> intStack = new Stack<>();
intStack.push(5);
intStack.push(8);
assertEquals(2, intStack.search(5));
}
Результатом является индекс данного объекта. Если присутствует более одного элемента, возвращается индекс `` ближайшего к вершине . Элемент, который находится на вершине стека, считается на позиции 1.
Если объект не найден, search() вернет -1.
6.2. Получение индекса элемента
Чтобы получить индекс элемента в стеке S , мы также можем использовать методы indexOf() и lastIndexOf() :
@Test
public void whenElementIsOnStack_thenIndexOfReturnsItsIndex() {
Stack<Integer> intStack = new Stack<>();
intStack.push(5);
int indexOf = intStack.indexOf(5);
assertEquals(0, indexOf);
}
lastIndexOf() всегда находит индекс элемента, который находится ближе всего к вершине стека . Это работает очень похоже на search() — с той важной разницей, что она возвращает индекс, а не расстояние от вершины: `` ``
@Test
public void whenMultipleElementsAreOnStack_thenIndexOfReturnsLastElementIndex() {
Stack<Integer> intStack = new Stack<>();
intStack.push(5);
intStack.push(5);
intStack.push(5);
int lastIndexOf = intStack.lastIndexOf(5);
assertEquals(2, lastIndexOf);
}
7. Удалить элементы из стека
Помимо операции pop() , используемой как для удаления, так и для извлечения элементов, мы также можем использовать несколько операций, унаследованных от класса Vector , для удаления элементов.
7.1. Удаление указанных элементов
Мы можем использовать метод removeElement() для удаления первого вхождения данного элемента:
@Test
public void whenRemoveElementIsInvoked_thenElementIsRemoved() {
Stack<Integer> intStack = new Stack<>();
intStack.push(5);
intStack.push(5);
intStack.removeElement(5);
assertEquals(1, intStack.size());
}
Мы также можем использовать removeElementAt() для удаления элементов с указанным индексом в стеке:
@Test
public void whenRemoveElementAtIsInvoked_thenElementIsRemoved() {
Stack<Integer> intStack = new Stack<>();
intStack.push(5);
intStack.push(7);
intStack.removeElementAt(1);
assertEquals(-1, intStack.search(7));
}
7.2. Удаление нескольких элементов
Давайте кратко рассмотрим, как удалить несколько элементов из стека с помощью API removeAll() , который примет коллекцию в качестве аргумента и удалит все соответствующие элементы из стека :
@Test
public void givenElementsOnStack_whenRemoveAllIsInvoked_thenAllElementsFromCollectionAreRemoved() {
Stack<Integer> intStack = new Stack<>();
List<Integer> intList = Arrays.asList(1, 2, 3, 4, 5, 6, 7);
intStack.addAll(intList);
intStack.add(500);
intStack.removeAll(intList);
assertEquals(1, intStack.size());
assertEquals(1, intStack.search(500));
}
Также возможно удалить все элементы из стека с помощью методов clear () или removeAllElements() ; оба эти метода работают одинаково:
@Test
public void whenRemoveAllElementsIsInvoked_thenAllElementsAreRemoved() {
Stack<Integer> intStack = new Stack<>();
intStack.push(5);
intStack.push(7);
intStack.removeAllElements();
assertTrue(intStack.isEmpty());
}
7.3. Удаление элементов с помощью фильтра
Мы также можем использовать условие для удаления элементов из стека. Давайте посмотрим, как это сделать с помощью removeIf () с выражением фильтра в качестве аргумента:
@Test
public void whenRemoveIfIsInvoked_thenAllElementsSatysfyingConditionAreRemoved() {
Stack<Integer> intStack = new Stack<>();
List<Integer> intList = Arrays.asList(1, 2, 3, 4, 5, 6, 7);
intStack.addAll(intList);
intStack.removeIf(element -> element < 6);
assertEquals(2, intStack.size());
}
8. Итерация по стеку
Stack позволяет нам использовать как Iterator , так и ListIterator. Основное отличие состоит в том, что первый позволяет нам перемещаться по стеку в одном направлении, а второй позволяет нам делать это в обоих направлениях:
@Test
public void whenAnotherStackCreatedWhileTraversingStack_thenStacksAreEqual() {
Stack<Integer> intStack = new Stack<>();
List<Integer> intList = Arrays.asList(1, 2, 3, 4, 5, 6, 7);
intStack.addAll(intList);
ListIterator<Integer> it = intStack.listIterator();
Stack<Integer> result = new Stack<>();
while(it.hasNext()) {
result.push(it.next());
}
assertThat(result, equalTo(intStack));
}
Все итераторы , возвращаемые стеком , являются отказоустойчивыми.
9. Stream API для стека Java
Стек — это коллекция, что означает, что мы можем использовать его с Java 8 Streams API. Использование Stream со стеком аналогично использованию его с любой другой коллекцией:
@Test
public void whenStackIsFiltered_allElementsNotSatisfyingFilterConditionAreDiscarded() {
Stack<Integer> intStack = new Stack<>();
List<Integer> inputIntList = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 9, 10);
intStack.addAll(inputIntList);
List<Integer> filtered = intStack
.stream()
.filter(element -> element <= 3)
.collect(Collectors.toList());
assertEquals(3, filtered.size());
}
10. Резюме
Это руководство является кратким и практическим руководством для понимания этого основного класса в Java — стека .
Конечно, вы можете изучить полный API в Javadoc .
И, как всегда, все примеры кода можно найти на GitHub .