Java Deque与Stack-编程知识-白鹭情

1.概述

Java Stack类实现了堆栈数据结构。 Java 1.6引入了[Deque](https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html)接口，该接口用于实现“双端队列”，该两端都支持元素的插入和删除。

现在，我们也可以将Deque接口用作LIFO（后进先出）堆栈。此外，如果我们查看Stack类的Javadoc ，我们将看到：

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

在本教程中，我们将比较Java Stack类和Deque接口。此外，我们将讨论为什么应该对LIFO stack Deque over Stack 。

2.类与接口

Java的Stack是一个Class ：

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

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

**由于Java不支持多重继承，如果我们的类已经是另一种类型的子类Stack**类：

public class UserActivityStack extends ActivityCollection { ... }

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

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

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

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

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

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

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

3. `synchronized`方法和性能

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

作为其子类， Stack类也被synchronized 。

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

因此，如果不需要线程安全，那么Deque **Stack .**可以为我们带来更好的性能**Stack** .

4.迭代顺序

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

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

让我们通过示例仔细研究它们。

首先，让我们将一些元素推入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.");

 }

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

接下来，让我们对Deque实例进行相同的测试。在测试中，我们将ArrayDeque类作为Deque

另外，我们将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.");

 }

如果我们进行测试，此测试也将通过。

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

当我们谈论LIFO堆栈数据结构时，对堆栈中的元素进行迭代的正确顺序应该是从上到下。

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

5.无效的LIFO堆栈操作

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

但是，不允许使用LIFO堆栈中的索引访问或操作元素，因为它违反了LIFO规则。

在本节中，让我们看看是否可以使用Stack和Deque.

5.1。 `java.util.Stack`类

由于其父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.");

 }

如果我们运行测试，则该测试将通过。

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

按照LIFO规则，我们必须弹出上方的所有元素才能访问底部的元素。

但是，在这里，使用Stack对象，我们只能通过其index访问元素。

此外，使用Stack对象，我们甚至可以通过index插入和删除元素。让我们创建一个测试方法来证明这一点：

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

 }

如果我们进行测试，该测试也将通过。

因此，使用Stack类，我们可以像处理数组一样操作其中的元素。这违反了LIFO合同。

5.2。 `java.util.Deque`接口

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

但是，由于Deque是“双端队列”，因此我们可以从两端插入或删除元素。

换句话说，当我们使用Deque作为LIFO堆栈时，我们可以直接将元素插入到堆栈底部或从堆栈底部移除。

让我们建立一个测试方法，看看这是如何发生的。同样，我们将继续在测试中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.");

 }

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

如果我们执行测试，则测试通过。

因此， Deque也没有遵守LIFO合同。

5.3。一个实施`LifoStack`基于上`Deque`

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

public interface LifoStack<E> extends Collection<E> {

 E peek();

 E pop();

 void push(E item);

 }

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

让我们创建一个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();

 }

 ...

 }