数据结构之双端队列

双端队列的特性

大致思路是两端都可以进出队列

Deque的实现API

API效果图

注意的地方

是双端队列的头部的进队和出队，因为这个一般的队列复杂度可能是O（n），由于队列的尾部iOS的数组实现有一部分预留的空间所以尾部进队出队是O（1）。
如果尾部空间不够重新resize是O（n）但是这个不会频繁发生，后面我们头部预留一部分空白的空间也是这个原理。

在头部进队画一个图解释下：

头部进队效果图

思路解释
图的第一行：如果当前容器容量满了，那么需要resize这个容器
图的第二行：然后把A B C 在内存向后移动
图的第三行：最后把新的元素copy进去

在头部出队画一个图解释下：

在头部出队效果图

思路解释
图的第一行：删除队列的第一个元素
图的第二行：队列的头部空白一个位置
图的第三行：队列后面的元素在内存前移

怎么实现一个高效的双端队列呢？

高效双端队列效果图

如上图所示：我们需要在队列的首尾两端预留一部分空间来避免频繁的resize。
还有一点是如果头部我们预留的空间太多没有用会浪费空间，所以我们会有一个机制来定时清理，如果所有元素大于预定的多少个并且空白空间占的比例大于百分之75或者一个阀值，清理一波。看效果图：

清理机制效果图

主要代码实现

头部进队优化

- (void)enqueueFront:(id)object
{
    //如果头部没有更多的空间
    if (self.headIndex == 0)
    {
        //创建之前大小容量的空白的元素 就是容量翻倍 注意由于iOS的数组不能插入nil 所以我们用NSNull占位
        for (int i=0; i<self.capacity;i++)
        {
            [self.dequeArray insertObject:[NSNull null] atIndex:0];
            
        }
        self.capacity *=2;
        //然后头部的索引移动到容器最后面
        self.headIndex = self.capacity;
    }
    //如果头部还有很多的空间 然后索引前移
    self.headIndex -= 1;
    self.dequeArray[self.headIndex] = object;
    
}

出队的优化

- (id)dequeue
{
    //正常的出队列 当前容器null占位 索引后移
    id object;
    if (self.headIndex < self.countOfQueue)
    {
        object = self.dequeArray[self.headIndex];
    }
    else
    {
        return nil;
    }
    self.dequeArray[self.headIndex] = [NSNull null];
    self.headIndex += 1;
    //清理机制
    double percentage = (double)self.headIndex/(double)(self.dequeArray.count);
    if (self.capacity > kDequeCapacity && percentage>kSpaceCapacity) {
        NSInteger amountToRemove = self.capacity*kSpaceCapacity;
        [self.dequeArray removeObjectsInRange:NSMakeRange(0, amountToRemove)];
        //注意清理了数组前面的空白元素指向头部元素的索引移动
        self.headIndex -= amountToRemove;
        self.capacity = self.dequeArray.count;
    }
    return object;
    
}