栈
1 代码位置
[gitee](Stack/Stack · petrichor/2024-summer-c-language - 码云 - 开源中国 (gitee.com))
2 概念与结构
1.1概念
栈：⼀种特殊的线性表，其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作的⼀端称为栈顶，另⼀端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out的原则。
压栈：栈的插⼊操作叫做进栈/压栈/⼊栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
1.2结构
栈的实现⼀般可以使⽤数组或者链表实现，相对⽽⾔数组的结构实现更优⼀些。因为数组在尾上插⼊数据的代价⽐较⼩。
数组尾插时间复杂度：O(1) 链表尾插时间复杂度：O(N)
2 栈的实现
因为栈的底层是数组，所以栈的实现方法和动态顺序表大致相同，且因为栈只能在栈顶出和入数据，所以栈还要更简单一些
Stack.h
#pragma once #include <stdio.h> #include <assert.h> #include <stdlib.h> #include<stdbool.h> typedef int STDataType; typedef struct Stack { STDataType* arr; STDataType capacity; STDataType top; }ST; //初始化和销毁 void STInit(ST*); void STDestroy(ST*); //栈顶---入数据,出数据 void StackPush(ST*, STDataType); void StackPop(ST*); //判空 bool StackEmpty(ST*); //取栈顶元素 STDataType StackTop(ST*); //获取栈中有效元素个数 int STSize(ST*);
test.c
- 用来测试我们写的函数(函数的调用)
- 这一部分就是自己写的时候用的测试用例，随便什么都行
最好是写一个方法测试一次，不然找错误的时候会很痛苦😜
#define _CRT_SECURE_NO_WARNINGS 1 #include "Stack.h" void STTest01() { ST st; STInit(&st); StackPush(&st, 1); StackPush(&st, 2); StackPush(&st, 3); StackPush(&st, 4); StackPush(&st, 5); //StackPop(&st); //StackPop(&st); //StackPop(&st); //StackPop(&st); //StackPop(&st); // printf("size: %d\n", STSize(&st)); while (!StackEmpty(&st)) { STDataType data = StackTop(&st); printf("%d ", data); StackPop(&st); } printf("\n"); printf("size: %d\n", STSize(&st)); } int main() { STTest01(); return 0; }
Stack.c
函数方法的实现，重点重点！！！
在每一个方法的第一排都使用assert宏来判断ps是否为空（避免使用时传入空指针，后续解引用都会报错）
2.1 栈的初始化和销毁
2.1.1 初始化
void STInit(ST* ps) { assert(ps); ps->arr = NULL; ps->capacity = ps->top = 0; }
2.1.2 销毁
void STDestroy(ST*ps) { assert(ps); if (ps->arr) free(ps->arr); ps->arr = NULL; ps->top = ps->capacity = 0; }
注：栈的特性决定了它无法被遍历和随机访问和插入数据，只能在栈顶操作！！！所以打印方法不能和顺序表一样遍历,具体方法会在后面讲到
2.2 栈顶插入和删除数据
2.2.1 栈顶插入数据（压栈）
插入数据的时候一定要判断空间是否足够，不足要增容，一般2倍或3倍增容！！！
养成好习惯，不要用arr直接接收动态开辟空间的地址，否则开辟失败arr变为NULL，连原来的内存块都找不到了，这就造成了内存泄漏！！！
void StackPush(ST* ps, STDataType x) { assert(ps); //空间是否足够 if (ps->top == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; STDataType* tmp = (STDataType*)realloc(ps->arr, newcapacity * sizeof(STDataType)); if (tmp == NULL) { perror("realloc fail!"); exit(1); } ps->arr = tmp; ps->capacity = 2 * newcapacity; } ps->arr[ps->top++] = x; }
2.2.2 栈顶删除数据（出栈）
删除数据的时候一定要判断栈是否为空，即top不能为0！！！
bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; }
void StackPop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); --ps->top; }
- 只要让top–即可，不影响后来的插入(数据会被覆盖)
2.3 返回栈顶数据
STDataType StackTop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->arr[ps->top-1]; }
2.4 返回栈的有效数据个数
int STSize(ST* ps) { return ps->top; }
2.5 打印栈中数据
- 之前说到栈不能通过遍历来打印，所以只有通过循环取栈顶元素后再让其出栈的方式来依次打印，打印完了栈也为空了！
while (!StackEmpty(&st)) { STDataType data = StackTop(&st); printf("%d ", data); StackPop(&st); } printf("\n");
Stack.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "Stack.h" void STInit(ST* ps) { assert(ps); ps->arr = NULL; ps->capacity = ps->top = 0; } void STDestroy(ST*ps) { assert(ps); if (ps->arr) free(ps->arr); ps->arr = NULL; ps->top = ps->capacity = 0; } void StackPush(ST* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; STDataType* tmp = (STDataType*)realloc(ps->arr, newcapacity * sizeof(STDataType)); if (tmp == NULL) { perror("realloc fail!"); exit(1); } ps->arr = tmp; ps->capacity = 2 * newcapacity; } ps->arr[ps->top++] = x; } bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } void StackPop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); --ps->top; } STDataType StackTop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->arr[ps->top-1]; } int STSize(ST* ps) { return ps->top; }
对于栈这一种结构的实现，因为和顺序表差别不大，更细节的内容就没有过多赘述，对以数组作为底层结构的线性表的实现方法有什么疑问的话，推荐先去看这一篇哦->顺序表的实现方法
