1.实现stack

思路：使用动态数组存储元素，维护栈顶指针（top）和容量（capacity），当栈满时自动扩容

typedef void (*FreeFunction)(void*);        //提供一种通用的内存释放机制


typedef struct{
    void **data;        //数据
    int top;            //栈顶指针
    int capacity;        //容量
    FreeFunction freeFn;
}Stack;

Stack* stack_create(int capacity,FreeFunction freeFn){
    Stack *stack=(Stack*)malloc(sizeof(Stack));
    stack->data=(void**)malloc(sizeof(void*)* capacity);
    stack->top=-1;
    stack->capacity=capacity;
    stack->freeFn=freeFn;
    return stack;
}

void stack_push(Stack* stack, void* element) {
    if (stack->top == stack->capacity - 1) {
        stack->capacity *= 2;
        stack->data = (void**)realloc(stack->data, sizeof(void*) * stack->capacity);
    }
    stack->data[++stack->top] = element;
}

void* stack_pop(Stack* stack) {
    if (stack->top == -1) return NULL;
    return stack->data[stack->top--];
}

void* stack_top(Stack* stack) {
    if (stack->top == -1) return NULL;
    return stack->data[stack->top];
}

int stack_empty(Stack* stack) {
    return stack->top == -1;
}

void stack_destroy(Stack* stack) {
    if (stack->freeFn) {
        for (int i = 0; i <= stack->top; i++) {
            stack->freeFn(stack->data[i]);
        }
    }
    free(stack->data);
    free(stack);
}

2.实现queue队列

实现思路：使用数组实现，维护队首front和队尾rear指针，队列满时自动扩容

typedef struct {
    void** data;
    int front;
    int rear;
    int capacity;
    int size;
    FreeFunction freeFn;
} Queue;

Queue* queue_create(int capacity, FreeFunction freeFn) {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->data = (void**)malloc(sizeof(void*) * capacity);
    queue->front = 0;
    queue->rear = -1;
    queue->size = 0;
    queue->capacity = capacity;
    queue->freeFn = freeFn;
    return queue;
}

void queue_enqueue(Queue* queue, void* element) {
    if (queue->size == queue->capacity) {
        queue->capacity *= 2;
        queue->data = (void**)realloc(queue->data, sizeof(void*) * queue->capacity);
    }
    queue->rear = (queue->rear + 1) % queue->capacity;
    queue->data[queue->rear] = element;
    queue->size++;
}

void* queue_dequeue(Queue* queue) {
    if (queue->size == 0) return NULL;
    void* element = queue->data[queue->front];
    queue->front = (queue->front + 1) % queue->capacity;
    queue->size--;
    return element;
}

void* queue_front(Queue* queue) {
    if (queue->size == 0) return NULL;
    return queue->data[queue->front];
}

int queue_empty(Queue* queue) {
    return queue->size == 0;
}

void queue_destroy(Queue* queue) {
    if (queue->freeFn) {
        while (!queue_empty(queue)) {
            void* element = queue_dequeue(queue);
            queue->freeFn(element);
        }
    }
    free(queue->data);
    free(queue);
}

3.实现vector

思路：使用动态数组存储元素，维护当前大小size和容量capacity，容量不足时自动扩容

typedef struct {
    void** data;
    int size;
    int capacity;
    FreeFunction freeFn;
} Vector;

Vector* vector_create(int capacity, FreeFunction freeFn) {
    Vector* vec = (Vector*)malloc(sizeof(Vector));
    vec->data = (void**)malloc(sizeof(void*) * capacity);
    vec->size = 0;
    vec->capacity = capacity;
    vec->freeFn = freeFn;
    return vec;
}

void vector_push_back(Vector* vec, void* element) {
    if (vec->size == vec->capacity) {
        vec->capacity *= 2;
        vec->data = (void**)realloc(vec->data, sizeof(void*) * vec->capacity);
    }
    vec->data[vec->size++] = element;
}


void vector_erase(Vector* vec, int index) {
    if (index < 0 || index >= vec->size) return;
    
    if (vec->freeFn) {
        vec->freeFn(vec->data[index]);
    }
    
    for (int i = index; i < vec->size - 1; i++) {
        vec->data[i] = vec->data[i + 1];
    }
    vec->size--;
}

int vector_size(Vector* vec) {
    return vec->size;
}

void vector_destroy(Vector* vec) {
    if (vec->freeFn) {
        for (int i = 0; i < vec->size; i++) {
            vec->freeFn(vec->data[i]);
        }
    }
    free(vec->data);
    free(vec);
}

4.实现list

思路：使用双向链表，每个节点包含指向前后节点的指针，维护头指针和尾指针以便快速访问两端

typedef struct ListNode {
    void* data;
    struct ListNode* next;
    struct ListNode* prev;
} ListNode;

typedef struct {
    ListNode* head;
    ListNode* tail;
    int size;
    FreeFunction freeFn;
} List;

List* list_create(FreeFunction freeFn) {
    List* list = (List*)malloc(sizeof(List));
    list->head = NULL;
    list->tail = NULL;
    list->size = 0;
    list->freeFn = freeFn;
    return list;
}

void list_push_back(List* list, void* element) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->data = element;
    newNode->next = NULL;
    newNode->prev = list->tail;
    
    if (list->tail) {
        list->tail->next = newNode;
    } else {
        list->head = newNode;
    }
    list->tail = newNode;
    list->size++;
}

void list_push_front(List* list, void* element) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->data = element;
    newNode->prev = NULL;
    newNode->next = list->head;
    
    if (list->head) {
        list->head->prev = newNode;
    } else {
        list->tail = newNode;
    }
    list->head = newNode;
    list->size++;
}

void* list_front(List* list) {
    if (!list->head) return NULL;
    return list->head->data;
}

void* list_back(List* list) {
    if (!list->tail) return NULL;
    return list->tail->data;
}

void list_erase(List* list, ListNode* node) {
    if (!node) return;
    
    if (node->prev) {
        node->prev->next = node->next;
    } else {
        list->head = node->next;
    }
    
    if (node->next) {
        node->next->prev = node->prev;
    } else {
        list->tail = node->prev;
    }
    
    if (list->freeFn) {
        list->freeFn(node->data);
    }
    free(node);
    list->size--;
}

void list_destroy(List* list) {
    ListNode* current = list->head;
    while (current) {
        ListNode* next = current->next;
        if (list->freeFn) {
            list->freeFn(current->data);
        }
        free(current);
        current = next;
    }
    free(list);
}