Java Deque vs. Stack – Java Deque与堆栈

最后修改: 2021年 2月 26日

中文/混合/英文(键盘快捷键：t)

1. Overview

1.概述

The Java Stack class implements the stack data structure. Java 1.6 introduced the Deque interface, which is for implementing a “double-ended queue” that supports element insertion and removal at both ends.

Java Stack类实现了stack数据结构。Java 1.6引入了Deque接口，用于实现一个 “双端队列”，支持两端的元素插入和移除。

Now, we can use the Deque interface as a LIFO (Last-In-First-Out) stack as well. Moreover, if we have a look at the Javadoc of the Stack class, we’ll see:

现在，我们也可以将Deque接口作为LIFO（Last-In-First-Out）栈使用。此外，如果我们看一下Stack类的Javadoc，我们会发现。

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.

Deque接口及其实现提供了一套更完整和一致的LIFO堆栈操作，应该优先于这个类使用。

In this tutorial, we’re going to compare the Java Stack class and the Deque interface. Further, we’ll discuss why we should use Deque over Stack for LIFO stacks.

在本教程中，我们将比较Java的Stack类和Deque接口。此外，我们将讨论为什么我们应该使用Deque而不是Stack来处理LIFO堆栈。

2. Class vs. Interface

2.类与界面

Java’s Stack is a Class:

Java的Stack是一个类。

public class Stack<E> extends Vector<E> { ... }

That is to say, if we want to create our own Stack type, we have to inherit the java.util.Stack class.

也就是说，如果我们想创建自己的Stack类型，我们必须继承java.util.Stack类。

Since Java doesn’t support multiple-inheritance, it can sometimes be hard to extend the Stack class if our class is already a subclass of another type:

由于Java不支持多重继承，如果我们的类已经是另一种类型的子类，有时很难扩展Stack类。

public class UserActivityStack extends ActivityCollection { ... }

In the example above, the UserActivityStack class is a sub-class of an ActivityCollection class. Therefore, it cannot also extend the java.util.Stack class. To use the Java Stack class, we may need to redesign our data models.

在上面的例子中，UserActivityStack类是ActivityCollection类的一个子类。因此，它不能同时扩展java.util.Stack类。为了使用 Java Stack 类，我们可能需要重新设计我们的数据模型。

On the other hand, Java’s Deque is an interface:

另一方面，Java的Deque是一个接口。

public interface Deque<E> extends Queue<E> { ... }

We know a class can implement multiple interfaces in Java. Therefore, implementing an interface is more flexible than extending a class for inheritance.

我们知道在Java中一个类可以实现多个接口。因此，实现一个接口比扩展一个类来继承更灵活。

For example, we can easily make our UserActivityStack implement the Deque interface:

例如，我们可以轻松地使我们的UserActivityStack实现Deque接口。

public class UserActivityStack extends ActivityCollection implements Deque<UserActivity> { ... }

Therefore, from the object-oriented design point-of-view, the Deque interface brings us more flexibility than the Stack class.

因此，从面向对象的设计角度来看，Deque接口比Stack类带给我们更多的灵活性。

3. synchronized Methods and Performance

3.同步的方法和性能

We’ve seen that the Stack class is a subclass of java.util.Vector. The Vector class is synchronized. It uses the traditional way to achieve thread-safety: making its methods “synchronized.”

我们已经看到，Stack类是java.util.Vector的一个子类。Vector类是同步的。它使用传统的方式来实现线程安全：使其方法”同步化。“

As its subclass, the Stack class is synchronized as well.

作为其子类，Stack类也是同步的。

On the other hand, the Deque interface is not thread-safe.

另一方面，Deque接口不是线程安全的。

So, if thread-safety is not a requirement, a Deque can bring us better performance than a Stack.

因此，如果线程安全不是一个要求，Deque可以为我们带来比Stack更好的性能。

4. Iteration Orders

4.迭代顺序

Since both Stack and Deque are subtypes of the java.util.Collection interface, they are also Iterable.

由于Stack和Deque都是java.util.Collection接口的子类型，它们也是Iterable。

However, what’s interesting is that if we push the same elements in the same order into a Stack object and a Deque instance, their iteration orders are different.

然而，有趣的是，如果我们将相同的元素以相同的顺序推入Stack对象和Deque实例，它们的迭代顺序是不同的。

Let’s take a closer look at them through examples.

让我们通过例子仔细看看它们。

First, let’s push some elements into a Stack object and check what its iteration order is:

首先，让我们把一些元素推入Stack对象，并检查它的迭代顺序是什么。

@Test
void givenAStack_whenIterate_thenFromBottomToTop() {
    Stack<String> myStack = new Stack<>();
    myStack.push("I am at the bottom.");
    myStack.push("I am in the middle.");
    myStack.push("I am at the top.");

    Iterator<String> it = myStack.iterator();

    assertThat(it).toIterable().containsExactly(
      "I am at the bottom.",
      "I am in the middle.",
      "I am at the top.");
}

If we execute the test method above, it’ll pass. It means, when we iterate over the elements in a Stack object, the order is from stack bottom to stack top.

如果我们执行上面的测试方法，它将会通过。这意味着，当我们遍历Stack对象中的元素时，其顺序是从栈底到栈顶。

Next, let’s do the same test on a Deque instance. We’ll take the ArrayDeque class as the Deque implementation in our test.

接下来，让我们在一个Deque实例上做同样的测试。我们将把ArrayDeque类作为我们测试中的Deque实现。

Also, we’ll use the ArrayDeque as a LIFO stack:

另外，我们将使用ArrayDeque作为LIFO栈。

@Test
void givenADeque_whenIterate_thenFromTopToBottom() {
    Deque<String> myStack = new ArrayDeque<>();
    myStack.push("I am at the bottom.");
    myStack.push("I am in the middle.");
    myStack.push("I am at the top.");

    Iterator<String> it = myStack.iterator();

    assertThat(it).toIterable().containsExactly(
      "I am at the top.",
      "I am in the middle.",
      "I am at the bottom.");
}

This test will pass as well if we give it a run.

如果我们让它运行一下，这个测试也会通过。

Therefore, the iteration order of Deque is from top to bottom.

因此，Deque的迭代顺序是从上到下。

When we’re talking about a LIFO stack data structure, the proper sequence of iterating over elements in the stack should be from top to bottom.

当我们谈论一个后进先出的堆栈数据结构时，在堆栈中迭代元素的正确顺序应该是从上到下。

That is, Deque‘s iterator works the way we expect for a stack.

也就是说，Deque的迭代器以我们对堆栈的期望方式工作。

5. Invalid LIFO Stack Operations

5.无效的LIFO堆栈操作

A classic LIFO stack data structure supports only push(), pop(), and peek() operations. Both the Stack class and the Deque interface support them. So far, so good.

一个经典的LIFO堆栈数据结构只支持push()、pop()和peek()操作。Stack类和Deque接口都支持它们。到目前为止，一切都很好。

However, it’s not allowed to access or manipulate elements by indexes in a LIFO stack since it breaks the LIFO rule.

然而，不允许在后进先出的堆栈中通过索引访问或操作元素，因为它破坏了后进先出的规则。

In this section, let’s see if we can call invalid stack operations with Stack and Deque.

在本节中，让我们看看是否可以用Stack和Deque.调用无效的栈操作。

5.1. The java.util.Stack Class

5.1.java.util.Stack类

Since its parent Vector is an array-based data structure, the Stack class has the ability to access elements by indexes:

由于其父辈Vector是一个基于数组的数据结构，Stack类有能力通过索引访问元素。

@Test
void givenAStack_whenAccessByIndex_thenElementCanBeRead() {
    Stack<String> myStack = new Stack<>();
    myStack.push("I am the 1st element."); //index 0
    myStack.push("I am the 2nd element."); //index 1
    myStack.push("I am the 3rd element."); //index 2
 
    assertThat(myStack.get(0)).isEqualTo("I am the 1st element.");
}

The test will pass if we run it.

如果我们运行该测试，就会通过。

In the test, we push three elements into a Stack object. After that, we want to access the element sitting at the bottom of the stack.

在测试中，我们将三个元素推入一个Stack对象。之后，我们要访问位于堆栈底部的元素。

Following the LIFO rule, we have to pop all elements above to access the bottom element.

按照后进先出的规则，我们必须弹出上面的所有元素来访问底部元素。

However, here, with the Stack object, we can just access an element by its index.

然而，在这里，有了Stack对象，我们就可以通过其索引访问一个元素。

Moreover, with a Stack object, we can even insert and remove an element by its index. Let’s create a test method to prove it:

此外，通过一个Stack对象，我们甚至可以通过其索引插入和删除一个元素。让我们创建一个测试方法来证明它。

@Test
void givenAStack_whenAddOrRemoveByIndex_thenElementCanBeAddedOrRemoved() {
    Stack<String> myStack = new Stack<>();
    myStack.push("I am the 1st element.");
    myStack.push("I am the 3rd element.");

    assertThat(myStack.size()).isEqualTo(2);

    myStack.add(1, "I am the 2nd element.");
    assertThat(myStack.size()).isEqualTo(3);
    assertThat(myStack.get(1)).isEqualTo("I am the 2nd element.");

    myStack.remove(1);
    assertThat(myStack.size()).isEqualTo(2);
}

The test will also pass if we give it a run.

如果我们让它运行一下，测试也会通过。

Therefore, using the Stack class, we can manipulate elements in it just like working with an array. This has broken the LIFO contract.

因此，使用Stack类，我们可以像处理一个数组一样来操作其中的元素。这已经打破了后进先出的契约。

5.2. The java.util.Deque Interface

5.2.java.util.Deque接口

Deque doesn’t allow us to access, insert, or remove an element by its index. It sounds better than the Stack class.

Deque不允许我们通过索引访问、插入或删除一个元素。它听起来比Stack类好。

However, since Deque is a “double-ended queue,” we can insert or remove an element from both ends.

然而，由于Deque是一个 “双端队列”，我们可以从两端插入或删除一个元素。

In other words, when we use Deque as a LIFO stack, we can insert/remove an element to/from the bottom of the stack directly.

换句话说，当我们使用Deque作为LIFO栈时，我们可以直接在栈底插入/移除一个元素。

Let’s build a test method to see how this happens. Again, we’ll continue using the ArrayDeque class in our test:

让我们建立一个测试方法来看看这是如何发生的。同样，我们将在测试中继续使用ArrayDeque类。

@Test
void givenADeque_whenAddOrRemoveLastElement_thenTheLastElementCanBeAddedOrRemoved() {
    Deque<String> myStack = new ArrayDeque<>();
    myStack.push("I am the 1st element.");
    myStack.push("I am the 2nd element.");
    myStack.push("I am the 3rd element.");

    assertThat(myStack.size()).isEqualTo(3);

    //insert element to the bottom of the stack
    myStack.addLast("I am the NEW element.");
    assertThat(myStack.size()).isEqualTo(4);
    assertThat(myStack.peek()).isEqualTo("I am the 3rd element.");

    //remove element from the bottom of the stack
    String removedStr = myStack.removeLast();
    assertThat(myStack.size()).isEqualTo(3);
    assertThat(removedStr).isEqualTo("I am the NEW element.");
}

In the test, first, we insert a new element to the bottom of a stack using the addLast() method. If the insertion succeeds, we attempt to remove it with the removeLast() method.

在测试中，首先，我们使用addLast()方法将一个新元素插入到堆栈的底部。如果插入成功，我们试图用removeLast()方法将其删除。

If we execute the test, it passes.

如果我们执行这个测试，它就会通过。

Therefore, Deque doesn’t obey the LIFO contract either.

因此，Deque也不遵守后进先出合约。

5.3. Implementing a LifoStack Based on Deque

5.3.实现基于Deque的LifoStack

We can create a simple LifoStack interface to obey the LIFO contract:

我们可以创建一个简单的LifoStack接口来遵守LIFO合约。

public interface LifoStack<E> extends Collection<E> {
    E peek();
    E pop();
    void push(E item);
}

When we create implementations of our LifoStack interface, we can wrap Java standard Deque implementations.

当我们创建LifoStack接口的实现时，我们可以包裹Java标准Deque实现。

Let’s create an ArrayLifoStack class as an example to understand it quickly:

让我们创建一个ArrayLifoStack类作为例子来快速了解它。

public class ArrayLifoStack<E> implements LifoStack<E> {
    private final Deque<E> deque = new ArrayDeque<>();

    @Override
    public void push(E item) {
        deque.addFirst(item);
    }

    @Override
    public E pop() {
        return deque.removeFirst();
    }

    @Override
    public E peek() {
        return deque.peekFirst();
    }

    // forward methods in Collection interface
    // to the deque object

    @Override
    public int size() {
        return deque.size();
    }
...
}

As the ArrayLifoStack class shows, it only supports the operations defined in our LifoStack interface and the java.util.Collection interface.

正如ArrayLifoStack类所示，它只支持我们的LifoStack接口和java.util.Collection接口中定义的操作。

In this way, it won’t break the LIFO rule.

这样一来，就不会违反后进先出的规则。

6. Conclusion

6.结语

Since Java 1.6, both java.util.Stack and java.util.Deque can be used as LIFO stacks. This article addressed the difference between these two types.

从Java 1.6开始，java.util.Stack和java.util.Deque都可以作为LIFO堆栈使用。这篇文章讨论了这两种类型的区别。

We’ve also analyzed why we should use the Deque interface over the Stack class to work with LIFO stacks.

我们还分析了为什么我们应该使用Deque接口而不是Stack类来处理LIFO堆栈。

Additionally, as we’ve discussed through examples, both Stack and Deque break the LIFO rule, more or less.

此外，正如我们通过例子所讨论的，Stack和Deque都或多或少地违反了后进先出规则。

Finally, we’ve shown one way to create a stack interface obeying the LIFO contract.

最后，我们展示了一种创建遵守后进先出契约的堆栈接口的方法。

As always, the complete source code is available over on GitHub.

一如既往，完整的源代码可在GitHub上获得，。