C语言数据结构 - 队列

曾经终败给现在 2023-10-07 21:49 21阅读 0赞

#### 基于动态数组实现队列 ####

#include <stdlib.h>
    
    typedef int bool;
    #define TRUE 1
    #define FALSE 0
    
    // 动态数组元素类型E, 这里默认给int，后期可以将int换成其他类型
    typedef int E;
    
    // 动态数组结构体
    typedef struct List {
        E *array; // 底层容器：数组
        int capacity; // 底层数组容量的长度
        int size; // 存入底层数组的元素个数
    } Queue; // 使用动态数组模拟队列
    
    // 动态数组最低容量，设置最低容量的目的是避免容量设置过小，导致频繁的内存重新申请
    #define MIN_CAPACITY 16
    
    /*!
     * 初始化队列
     * @return 队列指针
     */
    Queue* init() {
        Queue* queue = (Queue*) malloc(sizeof(Queue));
    
        // 申请动态数组结构体内存失败
        if(queue == NULL) {
            return NULL;
        }
    
        // 申请动态内存给底层数组
        queue->array = (E *) malloc(sizeof(E) * MIN_CAPACITY);
    
        // 申请底层容器内存失败
        if (queue->array == NULL) {
            // 同时释放掉已经申请到的动态数组结构体的内存
            free(queue);
            return NULL;
        }
    
        // 初始化动态数组结构体成员
        queue->capacity = MIN_CAPACITY;
        queue->size = 0;
    
        return queue;
    }
    
    /*!
     * 释放队列
     * @param queue 队列
     */
    void destroy(Queue* queue) {
        // 释放底层数组容器内存
        free(queue->array);
        // 释放队列结构体内存
        free(queue);
    }
    
    /*!
     * 重置动态数组的容量
     * @param queue 动态数组
     * @param newCap 新容量
     * @return 重置结果
     */
    bool resize(Queue *queue, int newCap) {
        // 如果新容量 小于 最小容量，则无需重置（避免频繁的扩容和缩容）
        if (newCap <= MIN_CAPACITY) {
            return TRUE;
        }
    
        // 重新申请动态数组底层容量的内存
        void *p = realloc(queue->array, sizeof(E) * newCap);
    
        // 申请内存失败
        if (p == NULL) {
            return FALSE;
        }
    
        // 更新动态数组结构体成员信息
        queue->array = (E *) p;
        queue->capacity = newCap;
    
        return TRUE;
    }
    
    /*!
     * 入队
     * @param queue 队列
     * @param ele 入队元素
     * @return 操作结果
     */
    bool enqueue(Queue* queue, E ele) {
        // 容量不足，则需要扩容
        if (queue->size == queue->capacity) {
            if (!resize(queue, queue->capacity << 1)) {
                // 重置容量失败，则无法插入
                return FALSE;
            }
        }
    
        // 尾插
        queue->array[queue->size] = ele;
        // 存入动态数组的元素个数+1
        queue->size++;
    
        return TRUE;
    }
    
    /*!
     * 出队
     * @param queue 队列
     * @return 出队元素的地址（注意：返回值是特地申请一块内存存储的，因此使用完需要记得释放，避免内存泄露）
     */
    E* dequeue(Queue* queue) {
        // 空队列不能出队
        if(queue->size == 0) {
            return NULL;
        }
    
        // 申请新内存，缓存将被删除的元素值
        E* p = (E*) malloc(sizeof(E));
        *p = queue->array[0];
    
        // 删除index位置的元素
        for (int i = 0; i < queue->size; i++) {
            queue->array[i] = queue->array[i + 1];
        }
    
        // 删除元素后，动态数组存储的元素个数-1
        queue->size--;
    
        // 动态数组存储的元素个数 少于 容量一半时，可以进行缩容（缩容为之前容量的一半）
        int newCap = queue->capacity >> 1;
        if (queue->size < newCap) {
            // 这里缩容失败不影响删除操作，前面已完成了删除操作
            resize(queue, newCap);
        }
    
        // 返回被删除的元素的地址（缓存地址）
        return p;
    }

#### 基于（单向）链表实现队列 ####

#include <stdlib.h>
    
    typedef int bool;
    #define TRUE 1
    #define FALSE 0
    
    // 队列元素类型（初始默认为int，后期可以改为需要的类型）
    typedef int E;
    
    // 单向链表节点结构体
    typedef struct ListNode {
        E ele; // 节点值
        struct ListNode *next; // 后继节点
    } Node;
    
    // 链表结构体
    typedef struct LinkedList {
        Node *head; // 头节点
        Node *tail; // 尾节点
        int size; // 队列长度
    } Queue; // 使用链表模拟队列
    
    /*!
     * 初始化队列
     * @return 队列指针
     */
    Queue *init() {
        // 申请内存
        Queue *queue = (Queue *) malloc(sizeof(Queue));
    
        // 申请内存失败
        if (queue == NULL) {
            return NULL;
        }
    
        // 初始化队列成员
        queue->head = NULL;
        queue->tail = NULL;
        queue->size = 0;
    
        return queue;
    }
    
    /*!
     * 释放队列
     * @param queue 队列
     */
    void destroy(Queue* queue) {
        Node* cur = queue->head;
    
        // 释放队列各个节点的内存
        while(cur != NULL) {
            Node* tmp = cur->next;
            free(cur);
            cur = tmp;
        }
    
        // 释放队列结构体内存
        free(queue);
    }
    
    /*!
     * 入队
     * @param queue 队列
     * @param ele 入队元素
     * @return 操作结果
     */
    bool enqueue(Queue* queue, E ele) {
        // 申请内存，创建一个新节点
        Node *node = (Node *) malloc(sizeof(Node));
    
        // 申请内存失败
        if (node == NULL) {
            return FALSE;
        }
    
        // 初始化节点
        node->ele = ele;
        node->next = NULL;
    
        if (queue->size == 0) {
            // 空队列插入
            queue->head = node;
            queue->tail = node;
        } else {
            // 尾插
            queue->tail->next = node;
            queue->tail = node;
        }
    
        // 节点数+1
        queue->size++;
    
        return TRUE;
    }
    
    /*!
     * 出队
     * @param queue 队列
     * @return 出队元素的地址（注意：返回值特地申请了一块内存来存储，因此使用完后，需要释放返回值占用的内存）
     */
    E* dequeue(Queue* queue) {
        // 指向将被删除节点
        Node *removeNode;
    
        if (queue->size == 1) {
            // 单节点队列删除唯一节点
            removeNode = queue->head;
            queue->head = NULL;
            queue->tail = NULL;
        } else {
            // 头删
            removeNode = queue->head;
            queue->head = queue->head->next;
        }
    
        // 队列节点个数-1
        queue->size--;
    
        // 申请一块内存用于存放被删除节点的值
        E *p = (E *) malloc(sizeof(E));
        *p = removeNode->ele;
    
        // 释放被删除节点的空间
        free(removeNode);
    
        return p;
    }