用数组实现队列

#include <malloc.h>
template <class T>
class ArrayQueue{
private:
    int head=0;
    int tail=0;
    int size=0;
    T* array=NULL;


public:
    ArrayQueue();
    ArrayQueue(int size);

    void push(T t);

    T pop();

    T peek();

    bool isEmpty();

    ~ArrayQueue();

    void growArray();
};

template<class T>
ArrayQueue<T>::ArrayQueue() {
    //默认size=8，只要是2的幂次方都可以 这里设为8
    this->size=8;
    array=(T*)malloc(sizeof(T)*size);
}

template<class T>
ArrayQueue<T>::ArrayQueue(int init_size) {
    this->size=8;
    if(init_size>8){
        this->size=init_size;
        this->size|=this->size>>2;
        this->size|=this->size>>4;
        this->size|=this->size>>8;
        this->size|=this->size>>16;

        this->size+=1;

    }

    array=(T*)malloc(sizeof(T)*size);


}

template<class T>
void ArrayQueue<T>::push(T t) {
    head=(head-1)&(size-1);
    array[head]=t;
    if(head==tail){
        growArray();
    }
}

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

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

template<class T>
bool ArrayQueue<T>::isEmpty() {
    return tail==head;
}

template<class T>
ArrayQueue<T>::~ArrayQueue() {
    if(array){
        free(array);
        array=NULL;
    }



}

template<class T>
void ArrayQueue<T>::growArray() {
    int new_size=size<<1;

    T* new_array=(T*)malloc(sizeof(T)*new_size);

    int count=size-head;

    for(int i=0;i<count;i++){

        new_array[0+i]=array[head+i];
    }

    for(int i=0;i<head;i++){

        new_array[count+i]=array[0+i];
    }

    free(array);
    this->array=new_array;

    this->head=0;
    this->tail=size;
    this->size=new_size;
}

整体思路：

数组的队列.png

注意点
队列的size必须要设置成2的幂次方，是为了在push和pop的时候，head和tail的下标始终能够在size-1到0之间进行循环。
比如size=8，（head-1）&(size-1)的情况有如下几种
head=0； -1&7=7；
head=7；6&7=6;
head=6；5&7=5;
head=5；4&7=4;
head=4；3&7=3;
head=3；2&7=2;
head=2；1&7=1;
head=1; 0&7=0;

0？？？（小于7，二进制的表示）

0 1 1 1（7的二进制表示）
所以两者进行&运算 结果都为0 ？ ？？