blob: b41b715544d0bec7016977a2a7bd50a1554cb41d (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
|
---
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;
}
```
|
