数据结构与算法1 — 循环队列

尊重作者劳动成果，转载请注明出处，谢谢！

1. queue.h

#ifndef queue_H
#define queue_H

#include <stddef.h>

//循环队列，内部结构为数组，提供先进先出的数据访问方式，支持多种数据类型，包括：int、struct等
typedef struct
{
    void *data;      //数组
    size_t dataSize; //元素大小（字节）
    size_t front;    //队头
    size_t rear;     //队尾
    size_t capacity; //队列容量
} Queue;

//定义该宏可以直观的看出队列元素的数据类型，比如：Queue(int)
#define Queue(type) Queue

#ifdef __cplusplus
extern "C"
{
#endif
    int queue_init(Queue *queue, size_t dataSize, size_t capacity);
    void queue_free(Queue *queue);
    void queue_clear(Queue *queue);
    int queue_expand(Queue *queue, size_t increment);
    int queue_shrink(Queue *queue);
    size_t queue_length(const Queue *queue);
    int queue_full(const Queue *queue);
    int queue_empty(const Queue *queue);
    int queue_push(Queue *queue, const void *data);
    int queue_pop(Queue *queue, void *data);
    int queue_insert(Queue *queue, const void *data, size_t offset);
    void *queue_front(const Queue *queue);
    void *queue_rear(const Queue *queue);
#ifdef __cplusplus
}
#endif

#endif

2. queue.c

#include "queue.h"
#include <string.h>
#include <stdlib.h>

//初始化
int queue_init(Queue *queue, size_t dataSize, size_t capacity)
{
    if (queue == NULL || dataSize <= 0 || capacity <= 0)
        return -1;

    capacity = capacity + 1; //rear始终指向队尾的下一个元素，即容量要多一个
    queue->data = malloc(capacity * dataSize);
    if (queue->data == NULL)
        return -1;

    memset(queue->data, 0, capacity * dataSize);
    queue->front = 0;
    queue->rear = 0;
    queue->capacity = capacity;
    queue->dataSize = dataSize;
    return 0;
}

//释放内存
void queue_free(Queue *queue)
{
    if (queue == NULL)
        return;

    if (queue->data != NULL)
    {
        free(queue->data);
        queue->data = NULL;
    }

    queue->front = 0;
    queue->rear = 0;
    queue->capacity = 0;
    queue->dataSize = 0;
}

//清空队列
void queue_clear(Queue *queue)
{
    if (queue == NULL)
        return;

    if (queue->data != NULL)
        memset(queue->data, 0, queue->capacity * queue->dataSize);

    queue->front = 0;
    queue->rear = 0;
}

//扩充队列
int queue_expand(Queue *queue, size_t increment)
{
    if (queue == NULL || increment <= 0)
        return -1;

    void *data = realloc(queue->data, (queue->capacity + increment) * queue->dataSize);
    if (data == NULL)
        return -1;

    queue->data = data;

    //移动元素，重新调整队尾
    if (queue->front > queue->rear)
    {
        size_t rear_old = queue->rear;
        queue->rear = queue->capacity;
        queue->capacity += increment;

        size_t i;
        for (i = 0; i < rear_old; i++) //将rear_old个元素移动到新分配的内存上
        {
            memmove((char *)queue->data + queue->rear * queue->dataSize, (char *)queue->data + i * queue->dataSize, queue->dataSize);
            queue->rear = (queue->rear + 1) % queue->capacity;
        }
    }
    else
    {
        queue->capacity += increment;
    }

    return 0;
}

//收缩队列
int queue_shrink(Queue *queue)
{
    if (queue == NULL)
        return -1;

    if (queue_full(queue))
        return -1;

    if (queue->rear < queue->front)
        return -1;

    size_t capacity;
    if (queue_empty(queue)) //queue->rear == queue->front
        capacity = 2;       //如果队列为空，收缩到最小容量2
    else
        capacity = queue->rear + 1; //前提：queue->rear > queue->front

    //队尾大于对头时才可以进行收缩
    void *data = realloc(queue->data, capacity * queue->dataSize);
    if (data == NULL)
        return -1;

    queue->data = data;
    queue->capacity = capacity;
    return 0;
}

//获取队列长度
size_t queue_length(const Queue *queue)
{
    if (queue == NULL || queue->data == NULL)
        return 0;

    return (queue->rear - queue->front + queue->capacity) % queue->capacity;
}

//判断队列是否已满
int queue_full(const Queue *queue)
{
    if (queue == NULL)
        return -1;

    return (queue->rear + 1) % queue->capacity == queue->front;
}

//判断队列是否为空
int queue_empty(const Queue *queue)
{
    if (queue == NULL)
        return 1;

    return queue->rear == queue->front;
}

//入队列
int queue_push(Queue *queue, const void *data)
{
    if (queue == NULL)
        return -1;

    if (queue_full(queue)) //队列满
        return -1;

    memcpy((char *)queue->data + queue->rear * queue->dataSize, data, queue->dataSize);
    queue->rear = (queue->rear + 1) % queue->capacity;
    return 0;
}

//出队列
int queue_pop(Queue *queue, void *data)
{
    if (queue == NULL)
        return -1;

    if (queue_empty(queue)) //队列空
        return -1;

    if (data != NULL)
        memcpy(data, (char *)queue->data + queue->front * queue->dataSize, queue->dataSize);

    queue->front = (queue->front + 1) % queue->capacity;
    return 0;
}

//插队，offset为相对队头的偏移量
int queue_insert(Queue *queue, const void *data, size_t offset)
{
    if (queue == NULL)
        return -1;

    if (queue_full(queue)) //队列满
        return -1;

    size_t pos = (queue->front + offset) % queue->capacity; //插入位置
    //超过队尾，或者队列为空，直接入队列
    if (pos >= queue->rear && (queue->rear >= queue->front || (queue->rear < queue->front && pos < queue->front)))
    {
        memcpy((char *)queue->data + queue->rear * queue->dataSize, data, queue->dataSize);
        queue->rear = (queue->rear + 1) % queue->capacity;
        return 0;
    }

    //元素后移
    size_t rear = queue->rear;
    void *ptr_rear_front; //rear的前一个元素
    while (rear != pos)
    {
        ptr_rear_front = (char *)queue->data + ((rear - 1 + queue->capacity) % queue->capacity) * queue->dataSize;
        memcpy((char *)queue->data + rear * queue->dataSize, ptr_rear_front, queue->dataSize);
        rear = (rear - 1 + queue->capacity) % queue->capacity;
    }

    //插入数据
    memcpy((char *)queue->data + pos * queue->dataSize, data, queue->dataSize);
    queue->rear = (queue->rear + 1) % queue->capacity;
    return 0;
}

//获取队头元素指针
void *queue_front(const Queue *queue)
{
    if (queue == NULL)
        return NULL;

    if (queue_empty(queue)) //队列空
        return NULL;

    return (char *)queue->data + queue->front * queue->dataSize;
}

//获取队尾元素指针
void *queue_rear(const Queue *queue)
{
    if (queue == NULL)
        return NULL;

    if (queue_empty(queue)) //队列空
        return NULL;

    return (char *)queue->data + ((queue->rear - 1 + queue->capacity) % queue->capacity) * queue->dataSize;
}