书签

Java栈的快速指南

评论 0 浏览 0 2019-12-21

1.概述

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

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

对于新的实现，我们应该支持 Deque接口及其实现。 Deque 定义了一组更完整和一致的 LIFO 操作.但是，我们可能仍然需要处理堆栈类，尤其是在遗留代码中，因此理解它很重要。

2.创建一个堆栈

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

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

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

3.堆栈的同步

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() 返回操作的结果，而不是添加的元素。

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

@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.从堆栈中取回

接下来，让我们来看看如何获取和删除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());
}

我们也可以得到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.在堆栈中搜索一个元素

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

@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.获取元素的索引

为了获得一个元素在Stack上的索引，我们也可以使用 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()来删除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.删除多个元素

让我们快速看看如何使用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));
}

也可以使用 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.使用过滤器去除元素

我们也可以使用条件从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.迭代一个堆栈

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

所有迭代器由Stack返回的迭代器都是快速失败的。

9.Java栈的Stream API

Stack是一个集合，这意味着我们可以用Java 8 Streams API来使用它。使用Stream与Stack类似于使用任何其他Collection:

@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。

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

最后更新2023-03-17
0 个评论
标签
Data Structures