做实体店打折信息网站,如何做视频网站的会员代理,如何提高网站的点击率,室内设计公司图片前言#xff1a; 在学习完数据结构顺序表和链表之后#xff0c;其实我们就可以做很多事情了#xff0c;后面的栈和队列#xff0c;其实就是对前面的顺序表和链表的灵活运用#xff0c;今天我们就来学习一下栈的原理和应用。 准备工作#xff1a;本人习惯将文件放在test.c…前言 在学习完数据结构顺序表和链表之后其实我们就可以做很多事情了后面的栈和队列其实就是对前面的顺序表和链表的灵活运用今天我们就来学习一下栈的原理和应用。 准备工作本人习惯将文件放在test.c、SeqList.c、SeqList.h三个文件中来实现其中test.c用来放主函数SeqList.c用来放调用的函数SeqList.h用来放头文件和函数声明
目录
什么是队列
栈的节点结构
栈的基本操作
1、初始化
2、销毁
3、插入元素
4、判断栈顶元素是否为空
5、删除元素
6、返回栈顶元素
7、栈中元素个数
完整的栈实例
总结 什么是队列
队列中的数据是按照先进后出的顺序的也就是说先进去的数字后出来 因为栈的这种性质所以栈我们用顺序表来实现比链表方便很多顺序表就可以实现尾插尾出所以我们一般就采用顺序表来实现 栈的节点结构
队列采用的顺序表的结构所以与顺序表差异不大
typedef int STDataType;
typedef struct stack
{STDataType* a;int top; //指向栈元素下一位int capacity;
}ST;栈的结构很简单定义一个整形指针一个表示容量和一个表示尾部元素的整形变量即可 栈的基本操作
//初始化
void STInit(ST* pst);
//销毁
void STDestroy(ST* pst);
//插入元素
void STPush(ST* pst, STDataType x);
//删除元素
void STPop(ST* pst);
//判断栈顶元素是否为空
bool STEmpty(ST* pst);
//找栈顶元素
STDataType STTop(ST* pst);
//栈中元素个数
STDataType STSize(ST* pst);
看上面的函数声明部分我们就可以看到我们每一步要实现的内容接下来我们就来一步一步进行实现
1、初始化
//初始化
void STInit(ST* pst)
{pst-a NULL;pst-capacity 0;pst-top 0;
}2、销毁
//销毁
void STDestroy(ST* pst)
{assert(pst);free(pst-a);pst-capacity pst-top 0;
}3、插入元素 插入元素时要先检查空间是否够用如果不够用要先进行扩容 //插入元素
void STPush(ST* pst, STDataType x)
{if (pst-top pst-capacity){int newcapacity pst-capacity 0 ? 4 : pst-capacity * 2;STDataType* newnode (STDataType*)realloc(pst-a, sizeof(STDataType) * newcapacity);if (newnode NULL){perror(STPush);return;}pst-a newnode;pst-capacity newcapacity;}pst-a[pst-top] x;pst-top;
}4、判断栈顶元素是否为空
这一步在下面有用到例如当删除栈顶元素时如果栈顶元素为空就无法操作所以需要判断栈顶元素是否为空
//判断栈顶元素是否为空
bool STEmpty(ST* pst)
{assert(pst);return pst-top 0;
}5、删除元素 这里删除元素是删除栈顶元素因为栈的特性是即出即删 //删除元素
void STPop(ST* pst)
{assert(pst);assert(!STEmpty(pst));pst-top--;
}6、返回栈顶元素
//找栈顶元素
STDataType STTop(ST* pst)
{assert(pst);assert(!STEmpty(pst));return pst-a[pst-top - 1];
}7、栈中元素个数
//栈中元素个数
STDataType STSize(ST* pst)
{assert(pst);return pst-capacity;
}
完整的栈实例
SeqList.h
//实现栈
typedef int STDataType;
typedef struct stack
{STDataType* a;int top; //指向栈元素下一位int capacity;
}ST;//初始化
void STInit(ST* pst);
//销毁
void STDestroy(ST* pst);
//插入元素
void STPush(ST* pst, STDataType x);
//删除元素
void STPop(ST* pst);
//判断栈顶元素是否为空
bool STEmpty(ST* pst);
//找栈顶元素
STDataType STTop(ST* pst);
//栈中元素个数
STDataType STSize(ST* pst);
test.c
//实现栈
void test()
{ST st;STInit(st);STPush(st,1);STPush(st, 2);STPush(st, 3);STPush(st, 4);while (!STEmpty(st)){printf(%d , STTop(st));STPop(st);}STDestroy(st);
}
int main()
{test();return 0;
}
SeqList.c
//实现栈
//初始化
void STInit(ST* pst)
{pst-a NULL;pst-capacity 0;pst-top 0;
}
//销毁
void STDestroy(ST* pst)
{assert(pst);free(pst-a);pst-capacity pst-top 0;
}
//插入元素
void STPush(ST* pst, STDataType x)
{if (pst-top pst-capacity){int newcapacity pst-capacity 0 ? 4 : pst-capacity * 2;STDataType* newnode (STDataType*)realloc(pst-a, sizeof(STDataType) * newcapacity);if (newnode NULL){perror(STPush);return;}pst-a newnode;pst-capacity newcapacity;}pst-a[pst-top] x;pst-top;
}
//判断栈顶元素是否为空
bool STEmpty(ST* pst)
{assert(pst);return pst-top 0;
}
//删除元素
void STPop(ST* pst)
{assert(pst);assert(!STEmpty(pst));pst-top--;
}
//找栈顶元素
STDataType STTop(ST* pst)
{assert(pst);assert(!STEmpty(pst));return pst-a[pst-top - 1];
}
//栈中元素个数
STDataType STSize(ST* pst)
{assert(pst);return pst-capacity;
}
总结 总之其实栈就是对顺序表的应用熟练栈和队列对我们巩固顺序表和链表帮助很大当然栈在一些场景下很实用后面我会出一个专门的习题讲解篇章讲数据结构的一些经典题型感兴趣的可以点赞关注一下 创作不易还请各位大佬点赞支持一下
