一. 双端队列

双端队列是指允许两端都可以进行入队和出队操作的队列

双端队列

typedef struct{
    int capacity;
    int cur_size;
    int *data;

    int front;
    int rear;
}Dqueue;

初始化双端队列

int initDqueue(Dqueue *dqueue, int capacity){
    if(dqueue == NULL){
        printf("initDqueue error !!!\n");
        return -1;
    }
    dqueue->data = (int*)malloc(sizeof(int) * capacity);
    dqueue->capacity = capacity;
    dqueue->cur_size = 0;
    dqueue->front = 0;
    dqueue->rear = 0;
    return 0;
}

销毁双端队列

int destoryDqueue(Dqueue *dqueue){
    if(dqueue == NULL || dqueue->data == NULL){
        printf("destoryDqueue error !!!\n");
        return -1;
    }
    free(dqueue->data);
    return 0;
}

判断双端队列是否为空

int empty(Dqueue *dqueue){
    if(dqueue->cur_size == 0)
        return 1;
    return 0;
}

前端插入

int inFront(Dqueue *dqueue, int val){
    if(dqueue == NULL || dqueue->data == NULL || dqueue->cur_size == dqueue->capacity){
        printf("inFront error !!!\n");
        return -1;
    }
    dqueue->front = (dqueue->front - 1 + dqueue->capacity) % dqueue->capacity;
    dqueue->data[dqueue->front] = val;
    ++dqueue->cur_size;
    return 0;
}

前端删除

int outFront(Dqueue *dqueue){
    if(dqueue == NULL || dqueue->data == NULL || dqueue->cur_size == 0){
        printf("outFront error !!!\n");
        return -1;
    }
    dqueue->front = (dqueue->front + 1) % dqueue->capacity;
    --dqueue->cur_size;
    return 0;
}

后端插入

int inRear(Dqueue *dqueue, int val){
    if(dqueue == NULL || dqueue->data == NULL || dqueue->cur_size == dqueue->capacity){
        printf("inRear error !!!\n");
        return -1;
    }
    dqueue->data[dqueue->rear] = val;
    dqueue->rear = (dqueue->rear + 1) % dqueue->capacity;
    ++dqueue->cur_size;
    return 0;
}

后端删除

int outRear(Dqueue *dqueue){
    if(dqueue == NULL || dqueue->data == NULL || dqueue->cur_size == 0){
        printf("outRear error !!!\n");
        return -1;
    }
    dqueue->rear = (dqueue->rear - 1 + dqueue->capacity) % dqueue->capacity;
    --dqueue->cur_size;
    return 0;
}

获取前端元素

int getFront(Dqueue *dqueue, int *val){
    if(dqueue == NULL || dqueue->data == NULL || dqueue->cur_size == 0){
        printf("getFront error !!!\n");
        return -1;
    }
    *val = dqueue->data[dqueue->front];
    return 0;
}

获取后端元素

int getRear(Dqueue *dqueue, int *val){
    if(dqueue == NULL || dqueue->data == NULL || dqueue->cur_size == 0){
        printf("getRear error !!!\n");
        return -1;
    }
    *val = dqueue->data[(dqueue->rear - 1 + dqueue->capacity) % dqueue->capacity];
    return 0;
}