顧名思義DoubleEndedQueue是一個隊(duì)列题造，是一個雙端隊(duì)列择份。
雙端隊(duì)列是一種抽象數(shù)據(jù)類型飒炎，它概括了一個隊(duì)列秆吵，其中的元素可以從前(頭) 或后(尾) 添加或刪除岭皂。 因此也經(jīng)常被稱為首尾鏈表牵寺。
用Solidity語言如何來實(shí)現(xiàn)一個雙端隊(duì)列呢叫胁？
分析源碼可知亡问，定義了一個結(jié)構(gòu)體Bytes32Deque枉侧。其中聲明了一個mapping(int128 => byte32)類型的變量_data引瀑；還聲明了兩個int128類型的變量_begin和_end。_begin和_end作為mapping的key使用榨馁。
mapping類型中的byte32可以理解憨栽，因?yàn)橹殿愋偷臄?shù)據(jù)都可以經(jīng)過類型轉(zhuǎn)換得到byte32類型的數(shù)據(jù)。
為什么_begin和_end要定義成int128類型呢翼虫？
// 查詢首尾元素時屑柔，隊(duì)列為空拋出該錯誤
error Empty();
// 通過元素在隊(duì)列中的位置查詢元素時，檢查越界問題
error OutOfBounds();
// _begin隊(duì)列頭珍剑，_end隊(duì)列位掸宛，作為mapping的key使用。
// mapping 存儲數(shù)據(jù)
struct Bytes32Deque {
int128 _begin;
int128 _end;
mapping(int128 => bytes32) _data;
}
通過_begin和_end的類型可以分析出招拙，對列的最大長度是uint256唧瘾。
因?yàn)開begin到_end的長度就是兩個int128，所以最大長度則是uint256别凤。
這里要注意int128包含正數(shù)和負(fù)數(shù)饰序，也就意味著mapping的key可以為負(fù)數(shù)和正數(shù)。
雙端隊(duì)列的特性是支持頭尾插入规哪、刪除求豫。下面我們分析下如何實(shí)現(xiàn)頭尾插入和刪除。
頭尾插入元素
/** 隊(duì)列尾插入元素
* @dev Inserts an item at the end of the queue.
*/
function pushBack(Bytes32Deque storage deque, bytes32 value) internal {
// 獲取當(dāng)前隊(duì)列尾的位置诉稍，再直接存儲值
int128 backIndex = deque._end;
deque._data[backIndex] = value;
unchecked {
// 加1蝠嘉，更新隊(duì)列尾的位置
deque._end = backIndex + 1;
}
}
/** 隊(duì)列頭插入元素
* @dev Inserts an item at the beginning of the queue.
*/
function pushFront(Bytes32Deque storage deque, bytes32 value) internal {
int128 frontIndex;
unchecked {
// 頭插入，找到當(dāng)前頭的位置杯巨，在減去 1
frontIndex = deque._begin - 1;
}
// 存儲值
deque._data[frontIndex] = value;
// 更新隊(duì)列頭的位置
deque._begin = frontIndex;
}
pushBack函數(shù)是從隊(duì)列末尾插入元素蚤告。先獲取當(dāng)前隊(duì)列尾的位置，再直接存儲值舔箭，最后加1更新_end罩缴。
pushFront函數(shù)是從隊(duì)列頭部插入元素蚊逢。先找到當(dāng)前頭的位置，減去 1箫章，再存儲值烙荷，最后更新_begin。
由于_begin和_end都是int128類型檬寂，所以默認(rèn)值都是0终抽。pushBack函數(shù)在進(jìn)行尾插入是從0開始，依次遞增桶至，占用正數(shù)段昼伴；而pushFront頭插入是從-1開始，依次遞減镣屹，占用負(fù)數(shù)段圃郊。
頭尾刪除元素
/** 檢查隊(duì)列是否為空，只對首尾位置進(jìn)行判斷女蜈，并未操作mapping
* @dev Returns true if the queue is empty.
*/
function empty(Bytes32Deque storage deque) internal view returns (bool) {
return deque._end <= deque._begin;
}
/** 隊(duì)列尾刪除元素
* @dev Removes the item at the end of the queue and returns it.
*
* Reverts with `Empty` if the queue is empty.
*/
function popBack(Bytes32Deque storage deque) internal returns (bytes32 value) {
if (empty(deque)) revert Empty();
int128 backIndex;
unchecked {
// 這里減1持舆，因?yàn)?每次隊(duì)列尾插入后，會先加1再更新_end的值伪窖，意味著在有效范圍內(nèi)逸寓，隊(duì)列最后一個位置沒有元素。
// 這里需要先減去1覆山，獲取到最后一個元素的位置
backIndex = deque._end - 1;
}
// 從mapping中取值竹伸，并返回
value = deque._data[backIndex];
// 刪除mapping中的該值
delete deque._data[backIndex];
// 更新末尾位置
deque._end = backIndex;
}
/** 隊(duì)列頭刪除元素
* @dev Removes the item at the beginning of the queue and returns it.
*
* Reverts with `Empty` if the queue is empty.
*/
function popFront(Bytes32Deque storage deque) internal returns (bytes32 value) {
if (empty(deque)) revert Empty();
// 隊(duì)列頭插入時，更新begin時簇宽，存在元素勋篓，這里不需要加減 1
int128 frontIndex = deque._begin;
// 從mapping獲取元素，并返回
value = deque._data[frontIndex];
// 刪除mapping中該元素
delete deque._data[frontIndex];
unchecked {
// 更新頭部的位置晦毙，因?yàn)閯h除了隊(duì)列的第一個元素生巡，又因頭插入占用的是負(fù)數(shù)段耙蔑，所以頭部位置需要加 1见妒。
deque._begin = frontIndex + 1;
}
}
popBack函數(shù)是從隊(duì)列末尾刪除元素。先校驗(yàn)空隊(duì)列甸陌，再進(jìn)行刪除须揣，最后更新末尾位置∏恚可以看到backIndex的 值是由_end減去1得來耻卡，這里減1，因?yàn)槊看侮?duì)列尾插入后牲尺，會先加1再更新_end的值卵酪，意味著在有效范圍內(nèi)幌蚊，隊(duì)列最后一個位置沒有元素。
popFront函數(shù)是從隊(duì)列頭部刪除元素溃卡。同樣是先校驗(yàn)空隊(duì)列溢豆，在獲取frontIndex的值時，沒有進(jìn)行減1操作瘸羡。最后在更新_begin時漩仙，做了加1操作，因?yàn)閯h除了隊(duì)列的第一個元素犹赖，又因頭插入占用的是負(fù)數(shù)段队他，所以頭部位置需要加 1。例如峻村，隊(duì)列頭部_begin的值是 -10麸折，刪除一個元素后，_begin的值應(yīng)更新為 -9粘昨。
查詢首尾元素
/**
* @dev Returns the item at the beginning of the queue.
*
* Reverts with `Empty` if the queue is empty.
*/
function front(Bytes32Deque storage deque) internal view returns (bytes32 value) {
if (empty(deque)) revert Empty();
int128 frontIndex = deque._begin;
return deque._data[frontIndex];
}
/**
* @dev Returns the item at the end of the queue.
*
* Reverts with `Empty` if the queue is empty.
*/
function back(Bytes32Deque storage deque) internal view returns (bytes32 value) {
if (empty(deque)) revert Empty();
int128 backIndex;
unchecked {
backIndex = deque._end - 1;
}
return deque._data[backIndex];
}
front函數(shù)是獲取隊(duì)列頭第一個元素磕谅。
back函數(shù)是獲取隊(duì)列最后一個元素。backIndex = deque._end - 1; 這里還是那個原理雾棺，隊(duì)列尾插入后膊夹，更新_end時做了加1操作。
根據(jù)隊(duì)列位置查詢元素
/**
* @dev Return the item at a position in the queue given by `index`, with the first item at 0 and last item at
* `length(deque) - 1`.
*
* Reverts with `OutOfBounds` if the index is out of bounds.
*/
function at(Bytes32Deque storage deque, uint256 index) internal view returns (bytes32 value) {
// int256(deque._begin) is a safe upcast
// 入?yún)㈩愋褪?uint256捌浩，必須先轉(zhuǎn)換成 int256
// _begin要與index求和放刨，所以_begin的類型是int128，也必須向上轉(zhuǎn)換成 int256
// idx是 _begin到_end之間的值
int128 idx = SafeCast.toInt128(int256(deque._begin) + SafeCast.toInt256(index));
if (idx >= deque._end) revert OutOfBounds();
return deque._data[idx];
}
// SafeCast.sol
function toInt128(int256 value) internal pure returns (int128 downcasted) {
downcasted = int128(value);
require(downcasted == value, "SafeCast: value doesn't fit in 128 bits");
}
function toInt256(uint256 value) internal pure returns (int256) {
// Note: Unsafe cast below is okay because `type(int256).max` is guaranteed to be positive
require(value <= uint256(type(int256).max), "SafeCast: value doesn't fit in an int256");
return int256(value);
}
at函數(shù)不太好理解尸饺，里面用到了一個類型轉(zhuǎn)換工具SafeCast进统。我們先看at函數(shù)的傳參，傳遞的是uint256浪听，這里為什么需要傳uint256類型呢螟碎？
前面我們已經(jīng)提到過，隊(duì)列的最大長度是uint256迹栓，這里的index取值范圍就是 0 到 type(uint256).max掉分。
index表示，要查詢隊(duì)列中哪一個位置的元素克伊。
index = 0酥郭，要查詢隊(duì)列第一個元素
index = 1，要查詢隊(duì)列第二個元素
index = 2愿吹，要查詢隊(duì)列第三個元素
.....
.....
所以不从，index只能是uint類型，不可能是int類型犁跪。隊(duì)列最大長度是兩個int128椿息，所以參數(shù)只能是uint256歹袁。
在計(jì)算idx時，指定的類型是int128寝优，idx也就是_begin到_end的取值范圍宇攻。最后做了一個越界的驗(yàn)證。
SafeCast.toInt128(int256(deque._begin) + SafeCast.toInt256(index)); 將 _begin 由 int128 轉(zhuǎn)換成 int256倡勇，將 index 由 uint256 轉(zhuǎn)換成 int256逞刷；二者求和，最后再將和由 int256 轉(zhuǎn)換成 int128 類型妻熊。
這里為什么要進(jìn)行這么多的類型轉(zhuǎn)換夸浅？
原因還得從函數(shù)的入?yún)㈩愋秃妥罱K需要的類型是什么說起，入?yún)⑹?uint256扔役，最終需要的是 int128帆喇。所以，入?yún)ndex必須要進(jìn)行類型轉(zhuǎn)換將uint類型轉(zhuǎn)換成int類型亿胸，所以就有了SafeCast.toInt256(index)坯钦。
_begin本身就是int128類型,為什么也需要進(jìn)行轉(zhuǎn)換呢？
因?yàn)橐v_begin 與 index求和侈玄，類型必須要統(tǒng)一婉刀。index的類型現(xiàn)在是 int256 ，所以 _begin也必須由 int128 類型向上轉(zhuǎn)換成 int256 類型序仙。
最后SafeCast.toInt128就是再將和的類型轉(zhuǎn)換成需要的int128類型突颊。
為什么要對_begin和index求和？
因?yàn)開begin是隊(duì)列的開始位置潘悼。例如要_begin = -2律秃，index傳入的值是1，查詢隊(duì)列第一個位置的元素治唤，mapping的key也就是 -1棒动，_begin 與 index 之和就是 -1。
清空隊(duì)列
function clear(Bytes32Deque storage deque) internal {
deque._begin = 0;
deque._end = 0;
}
清空隊(duì)列很簡單宾添，將開始位置和結(jié)束位置設(shè)置為默認(rèn)值0船惨，并沒有對mapping內(nèi)部的元素進(jìn)行刪除操作。
隊(duì)列長度
function length(Bytes32Deque storage deque) internal view returns (uint256) {
// The interface preserves the invariant that begin <= end so we assume this will not overflow.
// We also assume there are at most int256.max items in the queue.
unchecked {
return uint256(int256(deque._end) - int256(deque._begin));
}
}
隊(duì)列長度就是_end減去_begin辞槐。這里類型轉(zhuǎn)換是因?yàn)殚L度是uint256類型掷漱，_end和_begin都是int128類型粘室，所以需要進(jìn)行類型轉(zhuǎn)換榄檬。
總結(jié)
- 只能從頭或者尾依次添加或刪除元素，無法從中間某個位置刪除或添加衔统。
- 可以方便快速地獲取頭尾位置的元素鹿榜。
- 遵循FIFO原則海雪。
- 使用時應(yīng)使用storage，不能使用memery舱殿。
思考：
- 前面我們分析_begin的值是負(fù)數(shù)段奥裸，那隊(duì)列的頭部位置_begin的值可以是大于0的數(shù)嗎？
創(chuàng)建Bytes32Deque對象時沪袭，設(shè)置_begin的默認(rèn)值大于0湾宙。 - 清空隊(duì)列為什么不刪除元素？
gas費(fèi)用問題冈绊。
