###### tags: `java`

隨手閒聊 ArrayDeque
====

[TOC]

## 前言
在寫leetcode 題目 LRUCache, 想說可以試試看用ArrayDeque.

突然想到 array 如果依照一般操作, `addFirst` 在最開頭插入, 那不是效率很差嗎？ 每次都要把東西往後搬
> Ex:


因此就起了勁trace一下, 應該是有特別的做法

## 核心想法
Deque 主要就是一個讓使用者可以在頭、尾都可以加入元素的 container, 因此主要重點在於 **怎麼加入頭、尾**

我們先專注在 `addFirst`
### addFirst
一樣的例子, 在頭部插入一個 -1.
一般的想法就是:<div style="color:#ff0000;">將元素插入array 的第一個位置</div>

> 1.
> 2.

那現在我想要不移動其他元素的前提, 增加一個元素進來.
就得換個想法:
<div style="color:#ff0000;">
1. 將新的元素視為插入原本array 的左邊<br>
2. 為了不移動原有元素, 當作原本的內容就在右邊<br>
<br>
</div>

> 1.
|0|0|0|0|1|2|
|-|-|-|-|-|-|
> 2.
|0|0|0|-1|1|2|
|-|-|-|-|-|-|

如此一來就辦到所想的了~~~
### addLast
一樣的想法, 不多贅述

### 擴容時機

- addFirst 變成從右到左加入, index_head 每次 -1
- addLast 變成從左到右加入, index_tail 每次 +1

因此當執行 `addFirst` or `addLast` 時, <div style="color:#ff0000;">發現即將添加的地點, 已有元素存在, 那就是額滿需擴容了</div>
也就是

// call `addFirst` or `addLast`
if (index_head == index_tail) {
  // 需要擴容摟~
}

:::info
:bookmark:
實際上`java.util.ArrayDeque` 的index 做法很特別~
這裡因為要讓各位簡單理解, 採用上述敘述方式.
建議各位自己trace 看一下~
是利用餘數的概念去做的~
:::