顾名思义DoubleEndedQueue是一个队列，是一个双端队列。
双端队列是一种抽象数据类型，它概括了一个队列，其中的元素可以从前(头) 或后(尾) 添加或删除。 因此也经常被称为首尾链表。
用Solidity语言如何来实现一个双端队列呢？
分析源码可知，定义了一个结构体Bytes32Deque。其中声明了一个mapping(int128 => byte32)类型的变量_data；还声明了两个int128类型的变量_begin和_end。_begin和_end作为mapping的key使用。
mapping类型中的byte32可以理解，因为值类型的数据都可以经过类型转换得到byte32类型的数据。
为什么_begin和_end要定义成int128类型呢？
// 查询首尾元素时，队列为空抛出该错误
error Empty();
// 通过元素在队列中的位置查询元素时，检查越界问题
error OutOfBounds();
// _begin队列头，_end队列位，作为mapping的key使用。
// mapping 存储数据
struct Bytes32Deque {
int128 _begin;
int128 _end;
mapping(int128 => bytes32) _data;
}
通过_begin和_end的类型可以分析出，对列的最大长度是uint256。
因为_begin到_end的长度就是两个int128，所以最大长度则是uint256。
这里要注意int128包含正数和负数，也就意味着mapping的key可以为负数和正数。
双端队列的特性是支持头尾插入、删除。下面我们分析下如何实现头尾插入和删除。
头尾插入元素
/** 队列尾插入元素
* @dev Inserts an item at the end of the queue.
*/
function pushBack(Bytes32Deque storage deque, bytes32 value) internal {
// 获取当前队列尾的位置，再直接存储值
int128 backIndex = deque._end;
deque._data[backIndex] = value;
unchecked {
// 加1，更新队列尾的位置
deque._end = backIndex + 1;
}
}
/** 队列头插入元素
* @dev Inserts an item at the beginning of the queue.
*/
function pushFront(Bytes32Deque storage deque, bytes32 value) internal {
int128 frontIndex;
unchecked {
// 头插入，找到当前头的位置，在减去 1
frontIndex = deque._begin - 1;
}
// 存储值
deque._data[frontIndex] = value;
// 更新队列头的位置
deque._begin = frontIndex;
}
pushBack函数是从队列末尾插入元素。先获取当前队列尾的位置，再直接存储值，最后加1更新_end。
pushFront函数是从队列头部插入元素。先找到当前头的位置，减去 1，再存储值，最后更新_begin。
由于_begin和_end都是int128类型，所以默认值都是0。pushBack函数在进行尾插入是从0开始，依次递增，占用正数段；而pushFront头插入是从-1开始，依次递减，占用负数段。
头尾删除元素
/** 检查队列是否为空，只对首尾位置进行判断，并未操作mapping
* @dev Returns true if the queue is empty.
*/
function empty(Bytes32Deque storage deque) internal view returns (bool) {
return deque._end <= deque._begin;
}
/** 队列尾删除元素
* @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，因为 每次队列尾插入后，会先加1再更新_end的值，意味着在有效范围内，队列最后一个位置没有元素。
// 这里需要先减去1，获取到最后一个元素的位置
backIndex = deque._end - 1;
}
// 从mapping中取值，并返回
value = deque._data[backIndex];
// 删除mapping中的该值
delete deque._data[backIndex];
// 更新末尾位置
deque._end = backIndex;
}
/** 队列头删除元素
* @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();
// 队列头插入时，更新begin时，存在元素，这里不需要加减 1
int128 frontIndex = deque._begin;
// 从mapping获取元素，并返回
value = deque._data[frontIndex];
// 删除mapping中该元素
delete deque._data[frontIndex];
unchecked {
// 更新头部的位置，因为删除了队列的第一个元素，又因头插入占用的是负数段，所以头部位置需要加 1。
deque._begin = frontIndex + 1;
}
}
popBack函数是从队列末尾删除元素。先校验空队列，再进行删除，最后更新末尾位置。可以看到backIndex的 值是由_end减去1得来，这里减1，因为每次队列尾插入后，会先加1再更新_end的值，意味着在有效范围内，队列最后一个位置没有元素。
popFront函数是从队列头部删除元素。同样是先校验空队列，在获取frontIndex的值时，没有进行减1操作。最后在更新_begin时，做了加1操作，因为删除了队列的第一个元素，又因头插入占用的是负数段，所以头部位置需要加 1。例如，队列头部_begin的值是 -10，删除一个元素后，_begin的值应更新为 -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函数是获取队列头第一个元素。
back函数是获取队列最后一个元素。backIndex = deque._end - 1; 这里还是那个原理，队列尾插入后，更新_end时做了加1操作。
根据队列位置查询元素
/**
* @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
// 入参类型是 uint256，必须先转换成 int256
// _begin要与index求和，所以_begin的类型是int128，也必须向上转换成 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函数不太好理解，里面用到了一个类型转换工具SafeCast。我们先看at函数的传参，传递的是uint256，这里为什么需要传uint256类型呢？
前面我们已经提到过，队列的最大长度是uint256，这里的index取值范围就是 0 到 type(uint256).max。
index表示，要查询队列中哪一个位置的元素。
index = 0，要查询队列第一个元素
index = 1，要查询队列第二个元素
index = 2，要查询队列第三个元素
.....
.....
所以，index只能是uint类型，不可能是int类型。队列最大长度是两个int128，所以参数只能是uint256。
在计算idx时，指定的类型是int128，idx也就是_begin到_end的取值范围。最后做了一个越界的验证。
SafeCast.toInt128(int256(deque._begin) + SafeCast.toInt256(index)); 将 _begin 由 int128 转换成 int256，将 index 由 uint256 转换成 int256；二者求和，最后再将和由 int256 转换成 int128 类型。
这里为什么要进行这么多的类型转换？
原因还得从函数的入参类型和最终需要的类型是什么说起，入参是 uint256，最终需要的是 int128。所以，入参index必须要进行类型转换将uint类型转换成int类型，所以就有了SafeCast.toInt256(index)。
_begin本身就是int128类型,为什么也需要进行转换呢？
因为要讲_begin 与 index求和，类型必须要统一。index的类型现在是 int256 ，所以 _begin也必须由 int128 类型向上转换成 int256 类型。
最后SafeCast.toInt128就是再将和的类型转换成需要的int128类型。
为什么要对_begin和index求和？
因为_begin是队列的开始位置。例如要_begin = -2，index传入的值是1，查询队列第一个位置的元素，mapping的key也就是 -1，_begin 与 index 之和就是 -1。
清空队列
function clear(Bytes32Deque storage deque) internal {
deque._begin = 0;
deque._end = 0;
}
清空队列很简单，将开始位置和结束位置设置为默认值0，并没有对mapping内部的元素进行删除操作。
队列长度
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));
}
}
队列长度就是_end减去_begin。这里类型转换是因为长度是uint256类型，_end和_begin都是int128类型，所以需要进行类型转换。
总结
- 只能从头或者尾依次添加或删除元素，无法从中间某个位置删除或添加。
- 可以方便快速地获取头尾位置的元素。
- 遵循FIFO原则。
- 使用时应使用storage，不能使用memery。
思考：
- 前面我们分析_begin的值是负数段，那队列的头部位置_begin的值可以是大于0的数吗？
创建Bytes32Deque对象时，设置_begin的默认值大于0。 - 清空队列为什么不删除元素？
gas费用问题。
网友评论