1.概念
- 压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
- 出栈:栈的删除操作叫做出栈,出数据也在栈顶。
- 栈的元素遵循后进先出LIFO(Last In First Out)的原则。后面进来的数据先出去
2.栈的实现
- 三种实现方法,数组,单链表,双链表
- 这里我们采用数组,因为数组的缓存利用率高,而且基于结构更加容易访问,异地扩容的时候会消耗时间,但是这个开销对于栈来说很小。
- 双链表虽然很方便,有前后指针但是要多维护一个指针,同时也会增加空间的浪费,那还不然单链表。
- 分为三个部分,Stack.h 和 Stack.c 还有test.c;这里只说Stack.c的核心部分
- 栈的基本结构
typedef struct Stack
{
STDataType* pa;//数组
int top;//栈顶
int capacity;//有效个数
}ST;
2.1初始化,销毁
- 这里的关键问题点在于,初始化为0(下标位置) 的时候你要不要放入数据?,可是初始化本来就不用放数据
- 在top位置放数据的时候,需要 top++指向下一个地方,为下一个准备放数据
//初始化
void STInit(ST* ps)
{
assert(ps);
ps->pa = NULL;
ps->top = ps->capacity = 0;
}
//销毁
void STDestroy(ST* ps)
{
assert(ps);
ps->top = ps->capacity = 0;
free(ps);//删除元素不行销毁,因为数组的空间是一次性开辟的
ps = NULL;
}
2.2压栈(push),删除(pop)
- 压栈就是插入到数组后面,再插入之前需要看看有没有空间,就在结构体里面的ps->size插入就行,假如是2,刚好放到数组下标2位置处
- 防止数据丢失不要直接空间给ps->pa,而是先拿个tmp的临时空间来装着。
- 如果还是不太熟悉,看看我的单链表这篇文章更加详细
//压栈
void STPush(ST* ps,STDataType x)
{
assert(ps);//为NULL,你插入个屁
if (ps->top == ps->capacity)//相等说明没空间
{
int new = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->pa,sizeof(STDataType) * new);//假如pa 为NULL则 和malloc一样
if (tmp == NULL)
{
perror("STPush()::realloc()");
return;
}
//不要让ps->pa 直接去接收新空间的地址
ps->pa = tmp;
ps->capacity = new;
}
ps->pa[ps->top] = x;
ps->top++;
}
- pop,只有一行可不可不调用函数,删除数据呢?不行;因为没有断言检查了
- 这里直接有效个数,top-- 就行
- 入栈顺序不代表出栈顺寻,可以边进变出,或者入3个在途中出两个
- 进栈顺序只有一种,出栈顺序有很多种
//删除
void STPop(ST* ps)
{
assert(ps);
assert(ps->top);//为0 不能删了
ps->top--;
}
2.3有效个数(size),栈顶数据(top),栈是否为NULL(empty)
//有效个数
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}
//取栈顶元素
STDataType STTop(ST* ps)
{
assert(ps);
assert(ps->top > 0);//不大于0,你还怎么取栈顶元素
return ps->pa[ps->top - 1];//因为是有效元素的前一个
}
bool STEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;//表达式为真返回1,假返回0
}
2.4完整代码
2.4.1Stack.h
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
//可任意更换类型
typedef int STDataType;
typedef struct Stack
{
STDataType* pa;//数组
int top;//栈顶
int capacity;//有效个数
}ST;
//初始化和销毁
void STInit(ST* ps);
void STDestroy(ST* ps);
//压栈和出栈
void STPush(ST* ps, STDataType x);
void STPop(ST* ps);
//栈顶元素
STDataType STTop(ST* ps);
//有效个数
int STSize(ST* ps);
//判断是否为NULL
bool STEmpty(ST* ps);
2.4.2Stack.c
#include "Stack.h"
//初始化
void STInit(ST* ps)
{
assert(ps);
ps->pa = NULL;
ps->top = ps->capacity = 0;
}
//压栈
void STPush(ST* ps,STDataType x)
{
assert(ps);//为NULL,你插入个屁
if (ps->top == ps->capacity)//相等说明没空间
{
int new = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->pa,sizeof(STDataType) * new);//假如pa 为NULL则 和malloc一样
if (tmp == NULL)
{
perror("STPush()::realloc()");
return;
}
//不要让ps->pa 直接去接收新空间的地址
ps->pa = tmp;
ps->capacity = new;
}
ps->pa[ps->top] = x;
ps->top++;
}
//删除
void STPop(ST* ps)
{
assert(ps);
assert(ps->top);//为0 不能删了
ps->top--;
}
//取栈顶元素
STDataType STTop(ST* ps)
{
assert(ps);
assert(ps->top > 0);//不大于0,你还怎么取栈顶元素
return ps->pa[ps->top - 1];//因为是有效元素的后一个
}
//销毁
void STDestroy(ST* ps)
{
assert(ps);
ps->top = ps->capacity = 0;
free(ps);//删除元素不行销毁,因为数组的空间是一次性开辟的
ps = NULL;
}
//有效个数
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}
//判空
bool STEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;//表达式为真返回1,假返回0
}
2.4.3test.c
#include "Stack.h"
void STTest()
{
ST s;
STInit(&s);
//压栈
STPush(&s, 1);
STPush(&s, 2);
STPop(&s);//边进边出
STPush(&s, 3);
STPush(&s, 4);
//printf("%d\n", STTop(&s));
//STPop(&s);
//printf("%d\n", STTop(&s));
//STPop(&s);
//STPop(&s);
//printf("%d\n", STTop(&s));
//STPop(&s);
//STPop(&s);
while (!STEmpty(&s))//返回假(0),返回的结果为假 就运行
{
printf("%d ", STTop(&s));
STPop(&s);
}
}
int main()
{
STTest();
return 0;
}
总结:
- 栈的整体不算难,学会理解后要独立完成联系
- 栈也是有应用场景的,至于为什么有这些结构体,都是前人发明出来的,学习知识有延后性;意思就是说从小到大不是学习的所有知识都是有用的,但是也要学
- 这个时候就体现了,笔记和博客的重要性;方便后续复习,知识多了肯定记不住