Java ArrayDeque簡介

1.概述

在本教程中,我們將展示如何使用Java的ArrayDeque類-這是Deque接口的實現。

ArrayDeque (也稱為“ Array Double Ended Queue”,發音為“ ArrayDeck”)是一種特殊的可增長數組,允許我們從兩側添加或刪除元素。

ArrayDeque實現可以用作堆棧(先進先出)或隊列(先進先出)。

2. API概覽

對於每個操作,我們基本上都有兩個選擇。

第一組由操作失敗時引發異常的方法組成。另一個組返回狀態或值:

運作方式方法方法拋出異常
從頭插入offerFirst(e)addFirst(e)
從頭部移除pollFirst()removeFirst()
從頭取回peekFirst()getFirst()
從尾插入offerLast(e)addLast(e)
從尾巴中移出pollLast()removeLast()
從尾巴取回peekLast()getLast()

3.使用方法

讓我們看一下如何使用ArrayDeque的幾個簡單示例。

3.1。使用ArrayDeque作為堆棧

我們將從一個如何將類視為堆棧的示例開始,然後推送一個元素:

@Test

 public void whenPush_addsAtFirst() {

 Deque<String> stack = new ArrayDeque<>();

 stack.push("first");

 stack.push("second");



 assertEquals("second", stack.getFirst());

 }

我們還看看如何將ArrayDeque中的元素用作堆棧:

@Test

 public void whenPop_removesLast() {

 Deque<String> stack = new ArrayDeque<>();

 stack.push("first");

 stack.push("second");



 assertEquals("second", stack.pop());

 }

當堆棧為空時, pop方法將引發NoSuchElementException

3.2。使用ArrayDeque作為隊列

現在讓我們從一個簡單的示例開始,該示例演示如何在ArrayDeque中提供元素(當用作簡單Queue時)

@Test

 public void whenOffer_addsAtLast() {

 Deque<String> queue = new ArrayDeque<>();

 queue.offer("first");

 queue.offer("second");



 assertEquals("second", queue.getLast());

 }

讓我們看看我們如何從ArrayDeque輪詢元素,當用作Queue時

@Test

 public void whenPoll_removesFirst() {

 Deque<String> queue = new ArrayDeque<>();

 queue.offer("first");

 queue.offer("second");



 assertEquals("first", queue.poll());

 }

如果隊列為空,則poll方法返回null值。

4. ArrayDeque如何實現

Java ArrayDeque簡介
在*幕後***, *ArrayDeque*由數組支持,當數組被填充時,數組的大小加倍。**

最初,數組以16的大小初始化。它被實現為雙端隊列,在該隊列中它維護兩個指針,即頭和尾。

讓我們從高層次上觀察這種邏輯的作用。

4.1。 ArrayDeque作為堆棧

Java ArrayDeque簡介
可以看出,當用戶使用push方法添加元素時,它會將頭指針移動一個。

當我們彈出一個元素時,它會將元素在頭部的位置設置為null,以便可以對元素進行垃圾回收,然後將其向後移動一個指針。

4.2。 ArrayDeque作為隊列

Java ArrayDeque簡介
當我們使用offer方法添加元素時,它會將尾部指針移動一個。

當用戶輪詢元素時,它會將元素在頭部的位置設置為null,以便可以對元素進行垃圾回收,然後移動其頭部指針。

4.3。關於ArrayDeque的注意事項

最後,還有一些有關此特定實現的註釋值得我們理解和記住:

  • 它不是線程安全的
  • 空元素不被接受
  • 比同步堆棧快得多的工作速度
  • 由於引用的位置更好,因此隊列比LinkedList更快
  • 大多數操作均攤銷了恆定的時間複雜度
  • ArrayDeque返回的迭代器是快速失敗的
  • 當添加一個元素的頭和尾指針相遇時, ArrayDeque自動將數組的大小加倍

5.結論

在這篇簡短的文章中,我們說明了ArrayDeque中方法的用法

所有這些示例的實現都可以在GitHub項目中找到;這是一個基於Maven的項目,因此應該易於導入和運行。