HW_Lib/lib/list/queue.cpp

#include <cstdlib>
#include <cassert>
#include <cstring>
#include <cstdio>
#include "queue.h"


static Queue_Node_t *newQueue_Node_t(void *data, unsigned char size) {
    Queue_Node_t *node = (Queue_Node_t *) malloc(sizeof(Queue_Node_t));
    node->val = malloc(size);
    node->next = NULL;
    node->prev = NULL;
    if (node->val == NULL) {
        printf("Error allocating memory");
        return NULL;
    }
    memcpy(node->val, data, size);
    return node;
}

/* 析构函数 */
static void delQueue_Node_t(Queue_Node_t *node) {
    free(node->val);
    free(node);
}


/* 构造函数 */
Queue_List_t *newQueue_List(unsigned char size) {
    Queue_List_t *deque = (Queue_List_t *) malloc(sizeof(Queue_List_t));
    deque->front = NULL;
    deque->rear = NULL;
    deque->queSize = 0;
    deque->typeSize = size;
    return deque;
}

/* 析构函数 */
void delQueue_List(Queue_List_t *deque) {
    // 释放所有节点
    for (int i = 0; i < deque->queSize && deque->front != NULL; i++) {
        Queue_Node_t *tmp = deque->front;
        deque->front = deque->front->next;
        delQueue_Node_t(tmp);
    }
    // 释放 deque 结构体
    free(deque);
}

/* 获取队列的长度 */
int queue_size(Queue_List_t *deque) {
    return deque->queSize;
}

/* 判断队列是否为空 */
bool queue_is_empty(Queue_List_t *deque) {
    return (queue_size(deque) == 0);
}

/* 入队 */
static void push(Queue_List_t *deque, void *data, bool isFront) {
    Queue_Node_t *node = newQueue_Node_t(data, deque->typeSize);
    if (node == NULL) {
        printf("Error creating new node");
        return;
    }
    if (queue_is_empty(deque)) {
        deque->front = deque->rear = node;
    } else if (isFront) {
        deque->front->prev = node;
        node->next = deque->front;
        deque->front = node;
    } else {
        deque->rear->next = node;
        node->prev = deque->rear;
        deque->rear = node;
    }
    deque->queSize++;
}

/* 队首入队 */
void pushFirst(Queue_List_t *deque, void *data) {
    push(deque, data, true);
}

/* 队尾入队 */
void pushLast(Queue_List_t *deque, void *data) {
    push(deque, data, false);
}

/* 访问队首元素 */
void *peekFirst(Queue_List_t *deque) {
    assert(queue_size(deque) && deque->front);
    return deque->front->val;
}

/* 访问队尾元素 */
void *peekLast(Queue_List_t *deque) {
    assert(queue_size(deque) && deque->rear);
    return deque->rear->val;
}

/* 出队 */
static void *pop(Queue_List_t *deque, bool isFront) {
    if (queue_is_empty(deque))
        return NULL;

    void *val = malloc(deque->typeSize);
    if (val == nullptr) {
        printf("Error allocating memory");
        return NULL;
    }

    if (isFront) {
        memcpy(val, deque->front->val, deque->typeSize);
        Queue_Node_t *fNext = deque->front->next;
        if (fNext) {
            fNext->prev = NULL;
            deque->front->next = NULL;
        }
        delQueue_Node_t(deque->front);
        deque->front = fNext;
    } else {
        memcpy(val, deque->rear->val, deque->typeSize);
        Queue_Node_t *rPrev = deque->rear->prev;
        if (rPrev) {
            rPrev->next = NULL;
            deque->rear->prev = NULL;
        }
        delQueue_Node_t(deque->rear);
        deque->rear = rPrev;
    }
    deque->queSize--;
    return val;
}

/* 队首出队 */
void *popFirst(Queue_List_t *deque) {
    return pop(deque, true);
}

/* 队尾出队 */
void *popLast(Queue_List_t *deque) {
    return pop(deque, false);
}