幾句話證明你看過ArrayDeque的源碼
Deque: double ended queue耘子，雙端隊(duì)列，它既可以當(dāng)作棧使用，也可以當(dāng)作隊(duì)列
推薦棧和隊(duì)列（即對(duì)兩端進(jìn)行操作）使用AarryDeque，根據(jù)索引位置增刪使用LinkedList
不允許存儲(chǔ)null，非線程安全挂绰，不允許放 null 元素，無索引位置概念，默認(rèn)容量是16且默認(rèn)容量必須是 2 的冪次葵蒂，不足2的冪次會(huì)自動(dòng)向上調(diào)整為2的冪次
1.動(dòng)態(tài)循環(huán)數(shù)組
ArrayList底層是一個(gè)動(dòng)態(tài)數(shù)組transient Object[] elementData
size 則是動(dòng)態(tài)數(shù)組的實(shí)際大小
transient int head頭索引
transient int tail尾索引
循環(huán)數(shù)組.png
2.構(gòu)造方法
ArrayDeque中的數(shù)組的容量總是2的冪交播，在取余的時(shí)候可以直接用位運(yùn)算(&)來替代原本的取余操作(%)
只有容量為 2 的冪次時(shí) ((tail + 1) & (elements.length - 1)) 操作中的 (elements.length - 1) 二進(jìn)制最高位永遠(yuǎn)為 0，當(dāng) (tail + 1) 與其按位與操作時(shí)才能保證循環(huán)歸零置位
/**
* 默認(rèn)數(shù)組長度16
*/
public ArrayDeque() {
elements = new Object[16];
}
/**
* 指定長度
*/
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
private void allocateElements(int numElements) {
elements = new Object[calculateSize(numElements)];
}
/**
* 數(shù)組長度為2的冪
* 在取余的時(shí)候可以直接用位運(yùn)算(&)來替代原本的取余操作(%)
*/
private static int calculateSize(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;
// Find the best power of two to hold elements.
// Tests "<=" because arrays aren't kept full.
// 指定長度大于等于默認(rèn)長度践付，改為合適的2的n次冪秦士，否則默認(rèn)長度
if (numElements >= initialCapacity) {
initialCapacity = numElements;
initialCapacity |= (initialCapacity >>> 1);
initialCapacity |= (initialCapacity >>> 2);
initialCapacity |= (initialCapacity >>> 4);
initialCapacity |= (initialCapacity >>> 8);
initialCapacity |= (initialCapacity >>> 16);
initialCapacity++;
if (initialCapacity < 0) // Too many elements, must back off
initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
}
return initialCapacity;
}
3.push方法
/**
* 用作stack，則是棧頂插入元素
*/
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
//由于數(shù)組長度必須為2的冪永高，在取余的時(shí)候可以直接用位運(yùn)算(&)來替代原本的取余操作(%)
//循環(huán)數(shù)組 防下標(biāo)越界+head循環(huán) (head - 1) % (elements.length)
//head新角標(biāo)隧土，將元素存到head角標(biāo)
elements[head = (head - 1) & (elements.length - 1)] = e;
//頭尾在同一角標(biāo)，說明循環(huán)數(shù)組被填滿命爬，觸發(fā)擴(kuò)容條件
if (head == tail)
doubleCapacity();
}
/**
* 用作queue曹傀，則是隊(duì)尾插入元素
*/
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
//將元素存到tail角標(biāo) tail指向下一個(gè)可以插入的空位
elements[tail] = e;
//由于數(shù)組長度必須為2的冪，在取余的時(shí)候可以直接用位運(yùn)算(&)來替代原本的取余操作(%)
//循環(huán)數(shù)組 防下標(biāo)越界+tail循環(huán) (tail + 1) % (elements.length)
//tail新角標(biāo) 頭尾在同一角標(biāo)饲宛，說明循環(huán)數(shù)組被填滿皆愉，觸發(fā)擴(kuò)容條件
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
/**
* 擴(kuò)容
*/
private void doubleCapacity() {
assert head == tail;
int p = head;
int n = elements.length;
//head右邊元素的個(gè)數(shù)
int r = n - p; // number of elements to the right of p
//原空間的2倍
int newCapacity = n << 1;
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];
//復(fù)制右半部分到新數(shù)組，新數(shù)組從0開始
System.arraycopy(elements, p, a, 0, r);
//復(fù)制左半部分
System.arraycopy(elements, 0, a, r, p);
elements = a;
//更新頭尾節(jié)點(diǎn)艇抠，tail指向的是下一個(gè)可插入的位置
head = 0;
tail = n;
}
4.pop方法
/**
* 用作queue幕庐，獲取并刪除隊(duì)首元素
* 用作stack，獲取并刪除棧頂元素
*/
public E pollFirst() {
int h = head;
@SuppressWarnings("unchecked")
E result = (E) elements[h];
// Element is null if deque empty
if (result == null)
return null;
//賦值空家淤，GC
elements[h] = null; // Must null out slot
//循環(huán)數(shù)組 防下標(biāo)越界+head循環(huán) (h + 1) % (elements.length)
head = (h + 1) & (elements.length - 1);
return result;
}
5.fast-fail機(jī)制
與ArrayList類似
6.自定義ArrayDeque練習(xí)
public class MyArrayDeque<E> implements MyDeque<E> {
private static final int DEAULT_CAPACITY = 5;
private E[] data;
private int size;
/**
* 隊(duì)列：先進(jìn)先出异剥，記錄頭尾
*/
private int first;
private int last;
public MyArrayDeque(int capacity) {
this.first = -1;
this.last = -1;
data = (E[]) new Object[capacity];
}
public MyArrayDeque() {
this(DEAULT_CAPACITY);
}
@Override
public void push(E e) {
final int minCapacity = size + 1;
if (minCapacity == data.length) {
grow(minCapacity);
}
if (size == 0) {
first = 0;
}
//如果元素彈出隊(duì)列，由于從頭開始彈出元素會(huì)導(dǎo)致數(shù)組靠前角標(biāo)的元素彈出后媒鼓，產(chǎn)生大量占用角標(biāo)，數(shù)據(jù)卻為空的情況
//所以采用循環(huán)數(shù)組错妖，當(dāng)插入元素時(shí)绿鸣，實(shí)際長度沒有達(dá)到數(shù)組長度時(shí)，通過對(duì)數(shù)組長度取余暂氯，實(shí)現(xiàn)將尾部角標(biāo)移動(dòng)到前方的空角標(biāo)
//相當(dāng)于first在前潮模，last在后
last = (last + 1) % data.length;//last循環(huán)
data[last] = e;
size++;
}
private void grow(int minCapacity) {
int newCapacity = data.length + (data.length >> 1);
if (newCapacity < minCapacity) {
newCapacity = minCapacity;
}
E[] newData = (E[]) new Object[newCapacity];
//從原數(shù)組的頭角標(biāo)開始，復(fù)制整個(gè)數(shù)組到一個(gè)新數(shù)組上
//新數(shù)組頭角標(biāo)為0痴施，尾角標(biāo)為實(shí)際長度-1
System.arraycopy(data, first, newData, 0, size);
data = newData;
first = 0;
last = size - 1;
}
@Override
public E pop() {
final E e = data[this.first];
data[this.first] = null;
size--;
//彈出元素擎厢，頭角標(biāo)+1 因采用循環(huán)數(shù)組，通過取余數(shù)確認(rèn)頭角標(biāo)
this.first = (first + 1) % data.length;//first循環(huán)
return e;
}
@Override
public E peek() {
return data[this.first];
}
@Override
public boolean empty() {
return size == 0;
}
@Override
public int size() {
return size;
}
public static void main(String[] args) {
MyDeque<Integer> deque = new MyArrayDeque<>();
for (int i = 0; i < 20; i++) {
deque.push(i + 1);
}
System.out.println(deque.peek());
System.out.println(deque.pop());
int size = deque.size();
for (int i = 0; i < size; i++) {
Integer pop = deque.pop();
System.out.println(pop);
}
}
}
7.自定義LinkedDeque練習(xí)
public class MyLinkedDeque<E> implements MyDeque<E> {
private int size;
private Node<E> first;
private Node<E> last;
@Override
public void push(E e) {
//前隊(duì)尾結(jié)點(diǎn)
Node<E> prev = this.last;
//新的隊(duì)尾結(jié)點(diǎn)
last = new Node<>(e, null);
//無數(shù)據(jù)時(shí)更新頭結(jié)點(diǎn)
if (size == 0) {
first = last;
}else{
//前隊(duì)尾結(jié)點(diǎn)的下一個(gè)元素指向新的隊(duì)尾結(jié)點(diǎn)
prev.next = last;
}
size++;
}
/**
* 先進(jìn)先出pop first
*
* @return
*/
@Override
public E pop() {
//新隊(duì)頭結(jié)點(diǎn)
Node<E> newFirstNode = first.next;
E item = first.item;
//更新隊(duì)頭結(jié)點(diǎn)
first = newFirstNode;
size--;
//無數(shù)據(jù)時(shí)更新尾結(jié)點(diǎn)
if (size == 0) {
last = null;
}
return item;
}
@Override
public E peek() {
return first.item;
}
@Override
public boolean empty() {
return size == 0;
}
@Override
public int size() {
return size;
}
private static class Node<E> {
E item;
Node<E> next;
public Node(E item, Node<E> next) {
this.item = item;
this.next = next;
}
}
public static void main(String[] args) {
MyDeque<Integer> deque = new MyLinkedDeque<>();
for (int i = 0; i < 20; i++) {
deque.push(i + 1);
}
System.out.println(deque.peek());
System.out.println(deque.pop());
int size = deque.size();
for (int i = 0; i < size; i++) {
Integer pop = deque.pop();
System.out.println(pop);
}
}
}
參考：https://www.cnblogs.com/CarpenterLee/p/5468803.html
https://www.rabbitwfly.com/
