---
abbrlink: 3557841346
categories:
- 往昔
date: "2025-05-11 10:09:21"
tags:
- 数据结构与算法
title: 【数据结构与算法】栈
---

## 基本概念

栈（Stack）是一种后进先出（LIFO）原则的线性数据结构。核心操作包括：

- 压栈（Push）：将元素添加到栈顶
- 出栈（Pop）：移除并返回栈顶元素
- 查看栈顶（Check）获取但移除栈顶元素
- 判空（is_empty）检查栈是否为空

## 结构定义

使用动态数组实现栈，包含三个核心属性：

```c
typedef struct Stack {
    int* data; // 存储元素的数组
    int top;   // 栈顶指针（当前元素位置）
    int capacity; // 栈的最大容量
}
```

- `data`：动态分配的数组指针
- `top`：初始值为-1，表示空栈，压栈时递增，出栈时递减
- `capacity`：栈的容量上限

## 功能实现

### 初始化

```c
// 初始化栈
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）

```c
// 压栈（Push）
void push(Stack *s, int value) {
  if (s -> top = s -> capacity -1) {
    printf("栈已满！\n");
    return;
  }
  s -> data[++s->top] = value;
}
```

检查栈是否已满，先递增指针再存入数据

### 出栈（Pop）

```c
// 出栈（Pop）
int pop(Stack *s) {
  if(is_empty(s)) {
    printf("栈为空！\n");
    return -1;
  }
  return s->data[s->top--];
}
```

检查栈是否为空，返回当前栈顶元素后移动指针

### 辅助功能

```c
// 判空
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;
}
```