数据结构算法之队列和双向队列

队列

队列(Queue)是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。允许插入的端是队尾，允许删除的端是队头(先进先出)。
那么我们会发现，插入的时间复杂度是O(1)级别的，但是删除是O(n)级别的，因为删除对头之后，其它数据需要向前移动。那么怎么让删除的时间复杂度也变成O(1)级别呢，这就引出双向队列

双向队列

image.png

思路：我们首先会有个head和tail，分别代表队头和对尾，很明显当head==tail的时候代表该队列已经满了，这时候就需要扩容。
扩容前我们首先做几件事情
一、构造函数中数组的大小是2的幂次方，主要目的就是保证数据的分布均匀,具体原因可以继续往下看

template<class E>
ArrayQueue<E>::ArrayQueue(int size) {// 3 -> 4  6 ->8  17 ->32
    // 保证是 2 的幂次
    int init_size = size;
    if (init_size >= 4) {
        init_size |= init_size >> 1;
        init_size |= init_size >> 2;
        init_size |= init_size >> 4;
        init_size |= init_size >> 8;
        init_size |= init_size >> 16;
        // 比如你传入的是4，上面步骤结束后的大小是7所以需要+1
        init_size += 1;

    }
    this->size = init_size;
    array = (E *) malloc(sizeof(E) * size);
}

二、既然是扩容，肯定要是在添加数据的时候进行扩容

template<class E>
void ArrayQueue<E>::push(E e) {
    //实际大小就是size-1
    head = (head - 1) & (size - 1);// -1
    //直接赋值就可以了
    array[head] = e;
    if (tail == head) {
        // 扩容
        growArray();
    }
}
template<class E>
void ArrayQueue<E>::growArray() {
    // 大小扩大两倍
    int new_size = size << 1;

    // 重新开辟一块内存
    E *new_array = (E *) malloc(sizeof(E) * new_size);

    // 对数据进行 copy ,将 tail 后面的拷贝到前面，将tail前面的拷贝到后面
    int r = size - tail;
    copyElement(array, tail, new_array, 0, r);
    copyElement(array, 0, new_array, r, tail);

    free(array);
    head = 0;
    tail = size;
    size = new_size;
    array = new_array;
}
/**
 * 赋值
 * @param src 原数组
 * @param sPo  原数组开始的位置
 * @param dest  目标数组
 * @param dPo  目标数组开始的位置
 * @param len  原数组结束的位置
 */
template<class E>
void ArrayQueue<E>::copyElement(E *src, int sPo, E *dest, int dPo, int len) {
    for (int i = 0; i < len; ++i) {
        dest[dPo + i] = src[sPo + i];
    }
}

上面代码解释下：

• head = (head - 1) & (size - 1);
  为什么说它的大小实际就是size-1呢，假设我们数组的大小通过构造函数传入的是4经过构造函数处理后我们的大小是8，具体构造函数中有解释，所以size-1的大小是7，二进制最后四位是0111，而head默认是0，也即是0-1=-1，二进制最后四位是1111，所以&运算结果是7，继续轮推我们会发现大小依次是6，5，4，3，2，1，0。

• growArray扩容数组,直接看图会更清晰
  假设我们添加1-10的数

  
  image.png
  

  添加数据是从从右向左添加数据，那么tail默认是在0这个位置，也就是当head==tail==0的时候代表队列满了，这时候进行第一次扩容

  
  image.png
  新建一个数组，将之前数组拷贝到新数组，这时候我们需要将head设置为0，tail为队列的大小，此时继续添加数据，仍然是从右向左添加数据
  image.png
  此时tail和head相等，那么证明此时又需要进行扩容,如何扩容呢，实际还是开辟一个新数组，但是这里我们需要注意一点，我们在复制数据的时候，不能打乱原来的数据，处理的方式，将 tail 后面的拷贝到前面，将tail前面的拷贝到后面

三、判断队列是否满了和释放内存

template<class E>
bool ArrayQueue<E>::isEmpty() {
    return tail == head;
}
template<class E>
ArrayQueue<E>::~ArrayQueue() {
    free(array);
}

四、获取队首的位置，但是不移除

template<class E>
E ArrayQueue<E>::peek() {
    return array[(tail - 1) & (size - 1)];
}

实际我们的队首是head所指向的位置，那么如何获得队首head的下标呢

image.png

假设是上述这种情况，实际队首是这个队列的大小

image.png
上述这种情况下，队首实际也是这个队列的大小，可是怎么获得这个队列的大小呢,我们在默认数组大小是4的情况下，第一次扩容后，tail由0→8，而size由8→16，所以下标实际就是7,由此得出

(tail - 1) & (size - 1)

五、移除队首的元素

template<class E>
E ArrayQueue<E>::pop() {
    tail = (tail - 1) & (size - 1);
    return array[tail];
}