目录
- 1. 栈
- 1.1 栈的概念及结构
- 1.2 栈的实现方式
- 1.3 栈的应用场景
- 2. 栈的实现
- 2.1 结构体
- 2.2 初始化
- 2.3 销毁
- 2.4 入栈
- 2.5 出栈
- 2.6 获取栈顶元素
- 2.7 判空
- 2.8 获取个数
- 3. test主函数
- 4. Stack.c文件
- 5. Stack.h文件
- 6. 运行展示
1. 栈
1.1 栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
1.2 栈的实现方式
栈可以通过多种方式实现，包括数组和链表等。使用数组实现的栈具有连续的内存空间，操作效率较高；而使用链表实现的栈则更加灵活，可以在动态环境中调整栈的大小。
实现用的是数据栈。
1.3 栈的应用场景
函数调用：在计算机程序中，函数调用和返回的过程可以用栈来实现。当调用一个函数时，会将函数的返回地址和参数压入栈中；当函数返回时，会从栈中弹出这些信息，并返回到调用点继续执行。
浏览器的前进与后退：在浏览器中，可以使用两个栈来实现前进和后退功能。一个栈记录新访问的页面，另一个栈记录后退弹出的页面。当用户点击前进按钮时，从记录新访问页面的栈中弹出页面；当用户点击后退按钮时，从记录后退页面的栈中弹出页面。
表达式求值：在编译器中，可以使用栈来进行表达式的求值。将运算符和操作数压入栈中，并根据运算符的优先级和结合性进行出栈和计算操作，最终得到表达式的值。
2. 栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
2.1 结构体
首先要先把结构体定义出来，一个是数组栈，一个是指向栈顶元素的下一个，还有一个是增容。
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;//指向栈顶元素的下一个int capaicty;
}ST;
2.2 初始化
top等于0指向栈顶元素的下一个位置，top等于-1指向栈顶元素
//初始化
void STInit(ST* pst)
{assert(pst);pst->a = NULL;//pst->top = -1;//指向栈顶元素pst->top = 0;//指向栈顶元素的下一个位置pst->capaicty = 0;
}
2.3 销毁
防止造成野指针的错误
//销毁
void STDestroy(ST* pst)
{assert(pst);pst->a = NULL;pst->top = 0;pst->capaicty = 0;free(pst->a);
}
2.4 入栈
先判断容量是否够，再实现动态增容。
//入栈
void STPush(ST* pst, STDataType x)
{//扩容if (pst->top == pst->capaicty){int newCapaicty = pst->capaicty = 0 ? 4 : pst->capaicty * 2;STDataType* tmp = (STDataType*)realloc(pst->a, newCapaicty * sizeof(STDataType));if (tmp == NULL){perror("STPush");return;}pst->a = tmp;pst->capaicty = newCapaicty;}pst->a[pst->top] = x;pst->top++;
}
2.5 出栈
看栈是否空，不是空就不能删，再top减减就行
//出栈
void STPpo(ST* pst)
{assert(pst);assert(!STEmpty(pst));pst->top--;
}
2.6 获取栈顶元素
因为top指向栈顶元素的下一个，所以top要减1，当然空的时候也要判断一下
//获取栈顶元素
STDataType STTop(ST* pst)
{assert(pst);assert(!STEmpty(pst));return pst->a[pst->top - 1];
}
2.7 判空
//判空
bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}
2.8 获取个数
打印之前可以看还有多少个在栈中
//获取个数
int STsize(ST* pst)
{assert(pst);return pst->top;
}
3. test主函数
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include "Stack.h"void TestStack1()
{ST st;STInit(&st);STPush(&st, 1);STPush(&st, 2);printf("%d ", STTop(&st));STPpo(&st);STPush(&st, 3);STPush(&st, 4);printf("size: %d\n", STsize(&st));//打印while (!STEmpty(&st)){printf("%d ", STTop(&st));STPpo(&st);}STDestroy(&st);
}int main()
{TestStack1();return 0;
}
4. Stack.c文件
#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"//初始化
void STInit(ST* pst)
{assert(pst);pst->a = NULL;//pst->top = -1;//指向栈顶元素pst->top = 0;//指向栈顶元素的下一个位置pst->capaicty = 0;
}//销毁
void STDestroy(ST* pst)
{assert(pst);pst->a = NULL;pst->top = 0;pst->capaicty = 0;free(pst->a);
}//入栈
void STPush(ST* pst, STDataType x)
{//扩容if (pst->top == pst->capaicty){int newCapaicty = pst->capaicty = 0 ? 4 : pst->capaicty * 2;STDataType* tmp = (STDataType*)realloc(pst->a, newCapaicty * sizeof(STDataType));if (tmp == NULL){perror("STPush");return;}pst->a = tmp;pst->capaicty = newCapaicty;}pst->a[pst->top] = x;pst->top++;
}//出栈
void STPpo(ST* pst)
{assert(pst);assert(!STEmpty(pst));pst->top--;
}//获取栈顶元素
STDataType STTop(ST* pst)
{assert(pst);assert(!STEmpty(pst));return pst->a[pst->top - 1];
}//判空
bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}//获取个数
int STsize(ST* pst)
{assert(pst);return pst->top;
}
5. Stack.h文件
#pragma once
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;//指向栈顶元素的下一个int capaicty;
}ST;//初始化
void STInit(ST* pst);//销毁
void STDestroy(ST* pst);//入栈
void STPush(ST* pst, STDataType x);//出栈
void STPpo(ST* pst);//获取栈顶元素
STDataType STTop(ST* pst);//判空
bool STEmpty(ST* pst);//获取个数
int STsize(ST* pst);
6. 运行展示
