栈（Stack）是一种基本的数据结构，它是一种线性表，但只允许在固定的一端进行插入和删除操作，这一端称为栈顶（top）。栈的特点是后进先出（Last In First Out, LIFO），即最后进入栈的元素最先被取出。
栈可以用数组来实现，也可以用链表来实现。用数组实现的栈称为顺序栈，用链表实现的栈称为链式栈。
顺序栈的特点是：
- 存储空间连续。
- 提前分配固定大小的存储空间，可能会造成空间浪费，或者空间不足时需要动态扩容。
- 访问速度快，因为支持随机访问。
链式栈的特点是：
- 存储空间不连续。
- 动态分配空间，不会造成空间浪费，也不会出现空间不足的问题。
- 访问速度相对较慢，因为不支持随机访问。
以下我来讲解一下顺序栈的使用。
1.顺序栈的结构体定义
#define N 5
顺序栈结构定义
#define N 5
typedef struct
{
int a[N];//数据域 存数据
int top;//栈针
}stack_t;
顺序栈操作
1. 创建一个空的栈 === 创建一个空的顺序表 createEmptyStack ()
2. 判断栈是否为满 === 判断顺序表是否为满 isFullStack ()
3. 判断栈是否为空 === 判断顺序表是否为空 isEmptyStack ()
4. 入栈 === 在顺序表的尾巴上插入一个数据 有效元素个数 + 1 inStack ()
5. 出栈 === 删除顺序表的尾巴 尾巴里面的数据返回 有效元素个数 - 1 outStack ()
6. 获取栈顶元素 === 将顺序表的尾巴节点里面的数据域返回 getTopStack ()
7. 清空栈 === 清空顺序表 clearEmptyStack ()
2.创建一个空的栈
stack_t * createEmptyStack ()
{
stack_t * p = malloc ( sizeof ( stack_t ));
if ( p == NULL )
{
printf ( "createEmptyStack malloc failed!!\n" );
return NULL ;
}
p -> top = 0 ; // 因为是空的栈 , 所以有效元素个数为 0
return p ;
}
3. 判断栈是否为满,满返回1,未满返回0
int isFullStack ( stack_t * p )
{
return p -> top == N ? 1 : 0 ;
}
4. 入栈,是插入,在数组尾巴插入一个数据
int pushStack ( stack_t * p , int x )
{
//0.容错判断
if ( isFullStack ( p ))
{
printf ( "isFullStack!!!\n" ); // 栈满 , 入栈失败
return - 1 ;
}
//1.入栈
p -> a [ p -> top ] = x ;
//2.将入栈的元素变为有效 , 有效元素个数 +1
p -> top ++ ;
return 0 ;
}
5.判断是否为空 1 代表空 0代表未空
int isEmptyStack ( stack_t * p )
{
return p -> top == 0 ? 1 : 0 ;
}
6.出栈,将数组的尾巴元素删除,同时将删除的数据值返回
int popStack ( stack_t * p )
{
//0.容错判断
if ( isEmptyStack ( p ))
{
printf ( "isEmptyStack!!!\n" ); // 空栈 , 出栈失败
return - 1 ;
}
//1.出栈 , 将数组的最后一个有效元素删除
p -> top -- ; // 有效元素个数 -1, 相当于将栈顶元素删除
//2.将出栈元素的值返回
//上面的 p->top-- 之后 ,p->top 里面保存的是出栈元素的下标
return p -> a [ p -> top ];
}
7. 获取栈顶元素的值
int getTopValue ( stack_t * p )
{
return p -> a [ p -> top - 1 ]; // p->top-1 得到最后一个有效元素的下标 , 即栈顶元素的下标
}
8. 清空栈
void clearStack ( stack_t * p )
{
p -> top = 0 ; // 有效元素赋值为 0
}
结语
以上就是栈的基本使用，本次代码分享到此结束，后续还会分享数据结构的知识。
最后的最后，还请大家点点赞，点点关注，谢谢大家！
