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

 }

 ...

 }

如ArrayLifoStack類所示，它僅支持在LifoStack接口和java.util.Collection接口中定義的操作。

這樣，它不會違反LIFO規則。

六，結論

從Java 1.6開始， java.util.Stack和java.util.Deque都可以用作LIFO堆棧。本文介紹了這兩種類型之間的區別。

我們還分析了為什麼我們應該在Stack Deque接口來處理LIFO堆棧。

此外，正如我們通過示例所討論的， Stack和Deque都或多或少地違反了LIFO規則。

最後，我們展示了一種遵循LIFO合同創建堆棧接口的方法。