【数据结构与算法】栈

基本概念 栈（Stack）是一种后进先出（LIFO）原则的线性数据结构。核心操作包括： 压栈（Push）：将元素添加到栈顶 出栈（Pop）：移除并返回栈顶元素 查看栈顶（Check）获取但移除栈顶元素 判空（is_empty）检查栈是否为空 结构定义 使用动态数组实现栈，包含三个核心属性： typedef struct Stack { int* data; // 存储元素的数组 int top; // 栈顶指针（当前元素位置） int capacity; // 栈的最大容量 } data：动态分配的数组指针 top：初始值为-1，表示空栈，压栈时递增，出栈时递减 capacity：栈的容量上限 功能实现 初始化 // 初始化栈 void init_stack(Stack *s, int capacity) { // 计算最大容量 s -> data = (int*)malloc(sizeof(int) * capacity) if(!s -> data) { printf("内存分配失败！\n"); exit(1); } // 初始化栈顶为-1，表空 s -> top = -1; // 把当前计算的最大容量赋值给传进来的栈 s -> capacity = capacity; } 这个函数中进行了动态分配内存计算最大容量，初始化赋值和异常处理。 压栈（Push） // 压栈（Push） void push(Stack *s, int value) { if (s -> top = s -> capacity -1) { printf("栈已满！\n"); return; } s -> data[++s->top] = value; } 检查栈是否已满，先递增指针再存入数据 出栈（Pop） // 出栈（Pop） int pop(Stack *s) { if(is_empty(s)) { printf("栈为空！\n"); return -1; } return s->data[s->top--]; } 检查栈是否为空，返回当前栈顶元素后移动指针 辅助功能 // 判空 int is_empty(Stack *s) { return s-> top == -1 } // 查看栈顶元素 int peek(Stack *s) { return is_empty(s) ? -1 : s->data[s->top]; } // 销毁 void destory_stack(Stack *S) { free(s->data); s -> top = -1; s -> capacity = 0; }