目录
- 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. 运行展示
