【数据结构与算法】栈

基本概念

栈（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;
}