Java 中的 Stack 类快速入门指南

baeldung 2019-12-21

1. 概述

在本篇简短的文章中，我们将介绍 java.util.Stack 类，并初步了解如何使用它。

栈（Stack）是一种通用的数据结构，代表一个 LIFO（后进先出）的对象集合，支持以常数时间复杂度进行元素的入栈（push）和出栈（pop）操作。

对于新的实现，我们应优先使用 Deque 接口及其具体实现类。Deque 提供了一套更完整、一致的 LIFO 操作方法。然而，在处理遗留代码时，我们仍可能需要使用 Stack 类，因此深入理解它仍然非常重要。

2. 创建 Stack

首先，我们使用默认的无参构造函数创建一个空的 Stack 实例：

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

这将创建一个初始容量为 10 的 Stack。如果添加的元素数量超过当前容量，容量会自动翻倍。但需要注意的是，即使移除了元素，Stack 的底层容量也不会缩小。

3. Stack 的同步性

Stack 是 Vector 的直接子类，这意味着它与其父类一样，是一个线程安全（同步）的实现。

然而，并非所有场景都需要同步。在不需要线程安全的情况下，建议使用 ArrayDeque。

4. 向 Stack 中添加元素

我们可以使用 push() 方法将元素添加到栈顶，该方法还会返回被添加的元素：

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

使用 push() 方法的效果与调用 addElement() 相同，唯一的区别是：addElement() 返回操作是否成功（boolean），而 push() 返回被添加的元素本身。

我们也可以一次性添加多个元素：

@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, intStack.size()); // 注意：原文此处误写为 intList.size()
}

注意：原文中 assertEquals(7, intList.size()); 应为 intStack.size()，此处已修正。

5. 从 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());
}

我们也可以仅查看栈顶元素而不移除它，使用 peek() 方法：

@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. 在 Stack 中搜索元素

6.1 使用 `search()` 方法

Stack 允许我们搜索某个元素，并返回其距离栈顶的位置（从 1 开始计数）：

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

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

如果存在多个相同元素，返回最靠近栈顶的那个元素的距离。
栈顶元素的位置为 1。
若未找到元素，则返回 -1。

6.2 获取元素的索引

我们也可以使用 indexOf() 和 lastIndexOf() 方法来获取元素在 Stack 中的索引（从 0 开始）：

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

lastIndexOf() 总是返回最靠近栈顶的匹配元素的索引。它与 search() 功能类似，但返回的是基于 0 的索引，而非距离：

@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. 从 Stack 中删除元素

除了用于移除并获取元素的 pop() 操作外，Stack 还继承了 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(index) 删除指定位置的元素：

@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 批量删除元素

使用 removeAll(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));
}

还可以使用 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(Predicate) 根据条件删除元素：

@Test
public void whenRemoveIfIsInvoked_thenAllElementsSatisfyingConditionAreRemoved() {
    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

Stack 支持使用 Iterator 和 ListIterator 进行遍历：

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

注意：Stack 返回的所有迭代器都是 fail-fast（快速失败）的。

9. 使用 Stream API 操作 Stack

由于 Stack 是 Collection 的子类，因此可以与 Java 8 的 Stream API 无缝集成：

@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 核心类 Stack 的快速实用指南。

当然，你也可以查阅官方 Javadoc 以深入了解其完整 API。

最佳实践提示：尽管 Stack 仍在使用，但在新项目中推荐使用 Deque（如 ArrayDeque）来实现栈功能，因其设计更合理、性能更优且 API 更清晰。