Java Deque與Stack
- java
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合同創建堆棧接口的方法。