网站建设英文字体,做一些网站犯法么,中国小康建设网站,网站建设方案书 广东#x1f4af;#x1f4af;#x1f4af; 本篇主要利用数组来实现栈#xff0c;对于栈的各种操作都作详细介绍#xff0c;压栈#xff0c;出栈以及获取栈中元素的操作都是学习栈的必备知识#xff0c;快来学起来吧#xff01;#xff01;#xff01;Ⅰ.栈的概念及… 本篇主要利用数组来实现栈对于栈的各种操作都作详细介绍压栈出栈以及获取栈中元素的操作都是学习栈的必备知识快来学起来吧©Ⅰ.栈的概念及结构©Ⅱ.栈的实现2.1栈的初始化2.2压栈2.3出栈2.4获取栈顶元素2.5获取栈中有效元素的个数2.6销毁栈2.7栈的打印©Ⅰ.栈的概念及结构
栈是一种特殊的线性表其只允许在固定的一端进行插入与删除操作。 进行数据的插入和删除的一端称为栈顶另一端称为栈底。 栈遵循先进后出后进先出的原则。
压栈栈的插入操作叫做压栈/入栈/进栈在栈顶实现 出栈栈的删除操作叫做出栈。也在栈顶实现。 入栈 出栈 ©Ⅱ.栈的实现
栈的实现一般可以使用数组或者链表实现相对而言数组的结构实现更优一些因为数组在尾上插入数据的代价比较小。
//下面是定长的静态栈的结构实际中一般不用因为不能扩大容量所以我们主要实现下面的支持动态增长的栈
#define N 10
typedef int STData;
struct stack1
{int arr[N];//静态数组int top;//栈顶
}ST;//支持动态增长的栈结构
#include stdio.h
#include stdlib.h
#include assert.h
typedef int STData;//重定义栈使用的数据如果栈使用的数据不是int类型那么可以通过修改这里从而修改栈的使用数据类型
typedef struct Stack
{int* a;//指向一个数组的指针int top;//栈顶int capicty;//数组容量
}ST;//重命名为ST
//初始化栈表
void STInit(ST*ps);
//销毁栈表
void STDestroy(ST* ps);
//压栈在栈顶压入一个元素
void STpush(ST* ps,STData x);
//出栈在栈顶弹出一个元素。
void STpop(ST* ps);
//访问栈顶元素
//获取栈有效数据的大小
int STSize(ST* ps);
STData STTop(ST* ps);
//检查栈是否为空如果为空返回值为非0如果是假则返回0
int STSize(ST* ps);2.1栈的初始化
因为该数组是动态数组可以增容一开始我们可以给数组一定的容量当数组元素个数等于容量时再进行扩容即可。
不过要注意的是top值应该初始化为几呢 如果初始化为0那a[top]表示的是有元素还是没有元素呢 如果初始化为0的化那top就表示指向栈顶元素下一个位置的地方。
而如果初始化为-1那才表示的是栈顶元素的位置。一开始没有元素top为-1当有元素压栈进来后top变成0a[top]上就存在元素了。 两中表示方法都可以但 要注意表示一种就要一种按照该逻辑进行。
void STInit(ST* ps)//初始化栈表
{assert(ps);//判断结构体指针不为NULL//一上来可以给栈表初始化容量ps-a (STData*)malloc(sizeof(STData) * 4);if (ps-a NULL)//判断是否开辟成功{perror(malloc);}//初始话容量为4ps-capicty 4;ps-top 0;//top0 表示的是指向栈顶元素的下一个位置//top如果为-1则表示栈顶元素的位置
}2.2压栈
在元素入栈之前我们需要考虑是否栈空间已满而需要进行扩容。 所以一开始我们就需要将扩容操作写下。 每次扩容两倍。容量的大小随之改变。 还要注意的是当入栈后top是要进行然后top就是指向栈顶元素下一个位置的地方了。
void STpush(ST* ps, STData x)//压栈在栈顶压入一个元素--在压入之前也要考虑是否需要增容
{assert(ps);//断言判断if (ps-top ps-capicty)//当数组元素等于容量时{//增容STData* tmp (STData*)realloc(ps-a, sizeof(STData) * ps-capicty * 2);if (tmp NULL){perror(realloc);}ps-a tmp;//将扩容的空间赋给aps-capicty * 2;//数组的容量也随之变大}ps-a[ps-top] x;//将元素压入栈顶一开始top是0当元素进去后再让top指向该栈顶元素后一个位置ps-top;
}2.3出栈
在删除数据之前我们需要考虑栈空间里还有没有数据可以删除当栈空间里没有数据可删那就立刻停止。
所以我们首先需要对栈进行检查是否为空。 当栈为空时返回非0不为空时返回0
int STEmpty(ST* ps)
{assert(ps);return ps-top 0;
}而删除数据的操作我们只要让top–即可不需要释放空间。 void STpop(ST* ps)//出栈在栈顶弹出一个元素。
{assert(ps);//删除元素之前要检查栈表是否还有元素可删assert(!STEmpty(ps));//当栈表为NULL是断言ps-top--;}2.4获取栈顶元素
获取栈顶元素也就是top所指向的元素但要注意每次压入一个数据后top都会所以最后top是多加了一次要想访问最后一个元素也就是栈顶元素需要top-1
STData STTop(ST* ps)//访问栈顶元素
{assert(ps);//断言判断return ps-a[ps-top - 1];//top-1的位置才是栈顶元素
}2.5获取栈中有效元素的个数
其实top的数值大小就是栈中有效元素的个数 一开始top为0表中没有元素当有元素时top就进行有一个加一次有一个加一次所以最后栈中有效元素的个数就是top的数值
int STSize(ST* ps)//计算栈表长度
{assert(ps);//断言判断return ps-top;//top的长度就是栈表的长度
}2.6销毁栈
将栈销毁掉也就是让数据都归还操作系统。 开辟的空间需要释放定义的变量需要置0
void STDestroy(ST* ps)//销毁栈表
{assert(ps);//断言判断free(ps-a);//释放数值空间ps-a NULL;//并手动置NULLps-capicty 0;//置0ps-top 0;}2.7栈的打印
栈是不能进行打印的因为栈要求数据后入的要先出而打印的顺序是先入先出。 想要让栈的数据展现出来那就要按照它的特点我们先打印栈顶元素打印完再将栈顶元素出栈再打印新的栈顶元素再出栈知道栈变成空为止。
void test()
{ST p;STInit(p);STpush(p, 1);STpush(p, 2);STpush(p, 3);STpush(p, 4);STpush(p, 5);printf(%d\n, STSize(p));//获得栈中有效元素的个数while (!STEmpty(p)){printf(%d , STTop(p));//将栈的数据展现出现要求先进后出后进先出STpop(p);}STDestroy(p);
}
