C语言数据结构 - 栈

比眉伴天荒 2023-10-12 14:56 44阅读 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; // 存入底层数组的元素个数
    } Stack; // 使用动态数组模拟栈
    
    // 动态数组最低容量，设置最低容量的目的是避免容量设置过小，导致频繁的内存重新申请
    #define MIN_CAPACITY 16
    
    /*!
     * 初始化动态数组
     * @return 动态数组指针
     */
    Stack* init() {
        Stack* stack = (Stack*) malloc(sizeof(Stack));
    
        // 申请动态数组结构体内存失败
        if(stack == NULL) {
            return NULL;
        }
    
        // 申请动态内存给底层数组
        stack->array = (E *) malloc(sizeof(E) * MIN_CAPACITY);
    
        // 申请底层容器内存失败
        if (stack->array == NULL) {
            // 同时释放掉已经申请到的动态数组结构体的内存
            free(stack);
            return NULL;
        }
    
        // 初始化动态数组结构体成员
        stack->capacity = MIN_CAPACITY;
        stack->size = 0;
    
        return stack;
    }
    
    /*!
     * 释放动态数组
     * @param stack 动态数组
     */
    void destroy(Stack* stack) {
        // 释放底层容器内存
        free(stack->array);
        // 释放动态数组结构体内存
        free(stack);
    }
    
    /*!
     * 重置动态数组的容量
     * @param stack 动态数组
     * @param newCap 新容量
     * @return 重置结果
     */
    bool resize(Stack *stack, int newCap) {
        // 如果新容量 小于 最小容量，则无需重置（避免频繁的扩容和缩容）
        if (newCap <= MIN_CAPACITY) {
            return TRUE;
        }
    
        // 重新申请动态数组底层容量的内存
        void *p = realloc(stack->array, sizeof(E) * newCap);
    
        // 申请内存失败
        if (p == NULL) {
            return FALSE;
        }
    
        // 更新动态数组结构体成员信息
        stack->array = (E *) p;
        stack->capacity = newCap;
    
        return TRUE;
    }
    
    /*!
     * 压栈
     * @param stack 栈
     * @param ele 压栈元素
     * @return 操作结果
     */
    bool push(Stack* stack, E ele) {
        // 容量不足，则需要扩容
        if (stack->size == stack->capacity) {
            if (!resize(stack, stack->capacity << 1)) {
                // 重置容量失败，则无法插入
                return FALSE;
            }
        }
    
        // 尾插
        stack->array[stack->size] = ele;
        // 存入动态数组的元素个数+1
        stack->size++;
    
        return TRUE;
    }
    
    /*!
     * 弹栈
     * @param stack 栈
     * @return 被弹栈的栈顶元素（注意：返回值特地申请了一块内存存储，因此使用完需要释放内存，避免内存泄露）
     */
    E* pop(Stack* stack) {
        // 空栈无法弹栈
        if(stack->size == 0) {
            return NULL;
        }
    
        // 申请新内存，缓存将被删除的栈顶元素
        E* p = (E*) malloc(sizeof(E));
        *p = stack->array[stack->size - 1];
    
        // 删除元素后，动态数组存储的元素个数-1
        stack->size--;
    
        // 动态数组存储的元素个数 少于 容量一半时，可以进行缩容（缩容为之前容量的一半）
        int newCap = stack->capacity >> 1;
        if (stack->size < newCap) {
            // 这里缩容失败不影响删除操作，前面已完成了删除操作
            resize(stack, newCap);
        }
    
        // 返回被删除的元素的地址（缓存地址）
        return p;
    }
    
    /*!
     * 获取栈顶元素
     * @param stack
     * @return 返回栈顶元素的地址
     */
    E* peek(Stack* stack) {
        // 空栈无法弹栈
        if(stack->size == 0) {
            return NULL;
        }
    
        // 返回栈顶元素的地址
        return &stack->array[stack->size - 1];
    }

#### 基于链表实现栈 ####

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