Quick Guide to the Java Stack – Java栈的快速指南

1. Overview

1.概述

In this quick article, we’ll introduce the java.util.Stack class and start looking at how we can make use of it.

在这篇快速文章中，我们将介绍java.util.Stack类，并开始研究如何利用它。

A stack is a generic data structure that represents a LIFO (last in, first out) collection of objects allowing for pushing/popping elements in constant time.

堆栈是一个通用的数据结构，它表示一个后进先出的对象集合，允许在恒定的时间内推送/跳转元素。

For the new implementations, we should favor the Deque interface and its implementations. Deque defines a more complete and consistent set of LIFO operations. However, we may still need to deal with the Stack class, especially in legacy code, so it’s important to understand it well.

对于新的实现，我们应该支持Deque接口和其实现。Deque定义了一套更完整、更一致的LIFO操作。然而，我们可能仍然需要与Stack类打交道，尤其是在遗留代码中，所以充分了解它很重要。

2. Create a Stack

2.创建一个堆栈

Let’s start by creating an empty instance of Stack, by using the default, no-argument constructor:

让我们从创建一个Stack的空实例开始，通过使用默认的、无参数的构造函数。

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

This will create a Stack with the default capacity of 10. If the number of added elements exceeds the total Stack size, it will be doubled automatically. However, its size will never shrink after removing elements.

这将创建一个默认容量为10的Stack。如果添加的元素数量超过了总的Stack大小，它将被自动增加一倍。然而，在移除元素后，其大小将永远不会缩小。

3. Synchronization for Stack

3.堆栈的同步化

Stack is a direct subclass of Vector; this means that similarly to its superclass, it’s a synchronized implementation.

Stack是Vector的直接子类；这意味着与它的超类相似，它是一个同步的实现。

However, synchronization isn’t always needed, in such cases, it’s advised to use ArrayDeque.

然而，并不总是需要同步，在这种情况下，我们建议使用ArrayDeque。

4. Add into a Stack

4.添加到一个堆栈中

Let’s start by adding an element to the top of the Stack, with the push() method – which also returns the element that was added:

让我们先用push()方法将一个元素添加到Stack的顶部，该方法也会返回被添加的元素。

@Test
public void whenElementIsPushed_thenStackSizeIsIncreased() {
    Stack<Integer> intStack = new Stack<>();
    intStack.push(1);
    
    assertEquals(1, intStack.size());
}

Using push() method has the same effect as using addElement(). The only difference is that addElement() returns the result of the operation, instead of the element that was added.

使用push()方法与使用addElement()的效果相同。T唯一的区别是，addElement()返回操作的结果，而不是被添加的元素。

We can also add multiple elements at once:

我们还可以一次添加多个元素。

@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. Retrieve from a Stack

5.从堆栈中检索

Next, let’s have a look at how to get and remove the last element in a Stack:

接下来，让我们看看如何获取和删除Stack中的最后一个元素。

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

We can also get the last element of the Stack without removing it:

我们也可以得到Stack的最后一个元素，而不去掉它。

@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. Search for an Element in a Stack

6.在堆栈中搜索一个元素

6.1. Search

6.1.搜索

Stack allows us to search for an element and get its distance from the top:

Stack允许我们搜索一个元素并获得它与顶部的距离。

@Test
public void whenElementIsOnStack_thenSearchReturnsItsDistanceFromTheTop() {
    Stack<Integer> intStack = new Stack<>();
    intStack.push(5);
    intStack.push(8);

    assertEquals(2, intStack.search(5));
}

The result is an index of a given object. If more than one element is present, the index of the one closest to the top is returned. The item that is on the top of the stack is considered to be at position 1.

其结果是一个给定对象的索引。如果有一个以上的元素，将返回最接近顶部的那个元素的索引。在堆栈顶部的项目被认为是在位置1。

If the object is not found, search() will return -1.

如果没有找到该对象，search() 将返回-1。

6.2. Getting Index of Element

6.2.获取元素的索引

To get an index of an element on the Stack, we can also use the indexOf() and lastIndexOf() methods:

为了获得一个元素在Stack上的索引，我们也可以使用 indexOf() 和lastIndexOf()方法。

@Test
public void whenElementIsOnStack_thenIndexOfReturnsItsIndex() {
    Stack<Integer> intStack = new Stack<>();
    intStack.push(5);
    
    int indexOf = intStack.indexOf(5);
    
    assertEquals(0, indexOf);
}

The lastIndexOf() will always find the index of the element that’s closest to the top of the stack. This works very similarly to search() – with the important difference that it returns the index, instead of the distance from the top:

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. Remove Elements from a Stack

7.从堆栈中移除元素

Apart from the pop() operation, used both for removing and retrieving elements, we can also use multiple operations inherited from the Vector class to remove elements.

除了pop()操作（用于移除和检索元素）之外，我们还可以使用从Vector类继承的多个操作来移除元素。

7.1. Removing Specified Elements

7.1.删除指定的元素

We can use the removeElement() method to remove the first occurrence of the given element:

我们可以使用removeElement()方法来删除给定元素的第一次出现。

@Test
public void whenRemoveElementIsInvoked_thenElementIsRemoved() {
    Stack<Integer> intStack = new Stack<>();
    intStack.push(5);
    intStack.push(5);

    intStack.removeElement(5);
    
    assertEquals(1, intStack.size());
}

We can also use the removeElementAt() to delete elements under a specified index in the Stack:

我们还可以使用removeElementAt()来删除Stack中指定索引下的元素：。

    @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. Removing Multiple Elements

7.2.删除多个元素

Let’s have a quick look at how to remove multiple elements from a Stack using the removeAll() API – which will take a Collection as an argument and remove all matching elements from the Stack:

让我们快速了解一下如何使用removeAll() API从Stack中移除多个元素–它将把一个Collection作为参数，并从Stack中移除所有匹配元素。

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

It’s also possible to remove all elements from the Stack using the clear() or removeAllElements() methods; both of those methods work the same:

也可以使用clear()或removeAllElements()方法从Stack中删除所有元素；这两种方法的作用是一样的。

@Test
public void whenRemoveAllElementsIsInvoked_thenAllElementsAreRemoved() {
    Stack<Integer> intStack = new Stack<>();
    intStack.push(5);
    intStack.push(7);

    intStack.removeAllElements();

    assertTrue(intStack.isEmpty());
}

7.3. Removing Elements Using Filter

7.3.使用过滤器删除元素

We can also use a condition for removing elements from the Stack. Let’s see how to do this using the removeIf(), with a filter expression as an argument:

我们也可以使用条件从Stack中移除元素。让我们看看如何使用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. Iterate Over a Stack

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:

Stack允许我们同时使用Iterator和ListIterator。主要区别在于，第一个允许我们在一个方向上遍历Stack，第二个允许我们在两个方向上进行遍历。

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

All Iterators returned by Stack are fail-fast.

所有由Stack 返回的Iterators 都是故障快速的。

9. Stream API for the Java Stack

9.Java栈的流API

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:

Stack是一个集合，这意味着我们可以用Java 8 StreamsAPI来使用它。在Stack中使用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. Summary

10.总结

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

本教程是了解Java中这一核心类–Stack的快速实用指南。

Of course, you can explore the full API in the Javadoc.

当然，你可以在Javadoc中探索完整的API。

And, as always, all code samples can be found over on GitHub.

而且，像往常一样，所有的代码样本都可以在GitHub上找到超过。