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