Кратко ръководство за Java стека

1. Общ преглед

В тази бърза статия ще представим класа java.util.Stack и ще започнем да разглеждаме как можем да се възползваме от него.

Стекът е обща структура от данни, която представлява LIFO (последен вход, първи изход) колекция от обекти, позволяваща избутване / изскачане на елементи в постоянно време.

За новите реализации трябва да предпочетем интерфейса Deque и неговите реализации . Deque определя по-пълен и последователен набор от операции LIFO. Все пак може да се наложи да се справим с класа Stack , особено в наследения код, е важно да го познаваме по-добре.

2. Създайте стек

Нека започнем със създаването на празен екземпляр на Stack , като използваме конструктора по подразбиране, no-argument:

@Test public void whenStackIsCreated_thenItHasSizeZero() { Stack intStack = new Stack(); assertEquals(0, intStack.size()); }

Това ще създаде стек с капацитет по подразбиране 10. Ако броят на добавените елементи надвишава общия размер на стека , той ще се удвои автоматично. Размерът му обаче никога няма да се свие след премахване на елементи.

3. Синхронизация за стека

Stack е директен подклас на Vector ; това означава, че подобно на неговия суперклас, това е синхронизирано изпълнение.

Въпреки това, синхронизацията не винаги е необходима, в такива случаи се препоръчва да се използва 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-та , без да го премахваме:

@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. Премахване на множество елементи

Нека да разгледаме набързо как да премахнем множество елементи от стека, използвайки API на removeAll () - който ще вземе колекция като аргумент и ще премахне всички съвпадащи елементи от стека :

@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. Премахване на елементи с помощта на филтър

Можем да използваме и условие за премахване на елементи от стека. Нека да видим как да направим това с помощта на removeIf () , с израз на филтър като аргумент:

@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. Итерация над стека

Stack allows us to use both an Iterator and a ListIterator. The main difference is that the first one allows us to traverse Stack in one direction and second allows us to do this in both directions:

@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)); }

All Iterators returned by Stack are fail-fast.

9. Stream API for the Java Stack

Stack is a collection, which means we can use it with Java 8 Streams API. Using Stream with the Stack is similar to using it with any other Collection:

@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. Summary

This tutorial is a quick and practical guide to understand this core class in Java – the Stack.

Разбира се, можете да разгледате пълния API в Javadoc.

Както винаги, всички кодови проби могат да бъдат намерени в GitHub.