队列
队列(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];
}
网友评论