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.迭代順序

由於StackDeque 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規則。

在本節中,讓我們看看是否可以使用StackDeque.

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.Stackjava.util.Deque都可以用作LIFO堆棧。本文介紹了這兩種類型之間的區別。

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

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

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

相關推薦
返回主文件夾所需的最少操作數

返回主文件夾所需的最少操作數, 在文件系統上執行的文件夾的操作的變化(Unix風格),最佳算法

2020年11月1日閱讀 105

Java警告“未經檢查的轉換”

當我們編譯Java源代碼時,編譯器可能會顯示警告消息`“unchecked conversion”`或“ `The expression of type List needs unchecked conversion` 。

2021年1月29日閱讀 104

Java的字符串常量池位於哪裡,堆或堆棧在哪裡?

在這篇簡短的文章中,我們了解了`String`常量池的存儲區域。堆棧和堆具有不同的特性來存儲和訪問數據。從內存分配到其訪問和可用性,堆是最適合存儲String常量池的區域。

2021年2月26日閱讀 82

用Java創建泛型通用數組

鬆散的Java泛型類型很難強制轉換為強類型的Java數組。我們探討了該問題以及一些常見的解決方案。

2021年3月6日閱讀 127

在Docker中設置內存和CPU限制

在Docker中設置內存/ CPU限制的快速實用指南。 我們探索了限制docker訪問主機資源的方法。我們研究了`docker run`和`docker-compose`命令的用法。最後,我們使用`docker stats`控制資源消耗。

2021年3月8日閱讀 134

Java VM可以支持多少個線程?

在本文中,我們研究了可能影響Java虛擬機中可以創建的最大線程數的最重要方面。但是,在大多數情況下,增加限制不太可能永久解決可伸縮性問題。我們將需要考慮重新考慮應用程序的實現,甚至考慮應用水平縮放。

2021年3月14日閱讀 92