工商联网站建设作用,旅游小程序页面设计模板,wordpress老是打不开,网络论坛有些什么平台#x1f339;个人主页#x1f339;#xff1a;喜欢草莓熊的bear #x1f339;专栏#x1f339;#xff1a;数据结构 前言 栈是一种数据结构#xff0c;具有 后进先出 的特点 或者也可见说是 ” 先进后出 “。大家一起加油吧冲冲冲#xff01;#xff01; … 个人主页喜欢草莓熊的bear 专栏数据结构 前言 栈是一种数据结构具有 后进先出 的特点 或者也可见说是 ” 先进后出 “。大家一起加油吧冲冲冲 目录
前言 一、栈
1.1栈的概念和结构
1.2栈的实现 1.2.1栈的结构体定义
1.2.2初始化和销毁
1.2.3入栈
1.2.4出栈
1.2.5获取栈顶元素
1.2.6获取栈中的有效个数
1.2.7判空
1.3 代码测试
1.4 头文件
总结 一、栈
1.1栈的概念和结构 栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除操作的一端 称为栈顶另一端称为栈底。 栈中的数据元素遵守后进先出 LIFO Last In First Out 的原则。 这个栈的数据结构在我们生活中很像羽毛球桶 压栈栈的插入操作叫做进栈 / 压栈 / 入栈 入数据在栈顶 。 出栈栈的删除操作叫做出栈。 出数据也在栈顶 。 除了 先进后出 这个特点还有 入数据和出数据都在栈顶 下面是我画的简易图帮助大家理解栈是一个怎么样的数据结构。 1.2栈的实现 栈的实现一般可以使用 数组或者链表实现 相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。 我们这里实现的是动态栈的结构因为静态栈实际中一般运用不到。
先给大家看一下栈的结构体定义和一些功能。
//静态栈
typedef int STDataType;
#define N 10
typedef struct Stack
{STDataType _a[N];int _top; // 栈顶
}Stack;typedef int STDataType;
//动态栈
typedef struct Stack
{STDataType* a;int top;//这里的top和顺序表的size相似的都是指有效元素的下一个数据。int capacity;
}ST;//栈的实现是通过数组所以只需要传一级指针。//栈的初始化和销毁
void STInit(ST* pst);
void STDestory(ST* pst);//入栈和出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);//获取栈数据
STDataType STTop(ST* pst);//栈的判空
bool STEmpty(ST* pst);//栈的数据个数
int STSize(ST* pst); 1.2.1栈的结构体定义
因为我们这次实现的栈是基于数组实现的我们就可以参考顺序表的结构体定义来改进。 我们了解的栈的定义发现栈顶元素一直有被提及。我们要定义栈顶其次我们定义数组但是为什么我们这边是用指针呢其实这里数组等价于指针的在学习指针的时候我们学习过 a[i] *(pi)所以我们就像理解指针那一样的思路就可以了。还有就是结构体里面定义指针动态内存管理、高效的内存管理、还方便栈的各种操作。这边提到了内存也要定义一个数来计算是否满了。 结构体定义如下一个指针 STDataType *a、一个栈顶元素下标的下一个元素这里的top和顺序表的size相似的都是指有效元素的下一个数据当作顺序表的size来理解这样更容易想通。、一个计入内存大小的 capacity。
typedef int STDataType;typedef struct Stack
{STDataType* a;int top;//这里的top和顺序表的size相似的都是指有效元素的下一个数据。int capacity;
}ST;
1.2.2初始化和销毁
初始化最前面就还是需要判断指针是否为空有指针所以我们要置为NULL其他的都给赋值为0。如果我们把top定义成栈顶元素的下标那么我们就要把top赋值为-1了。这样赋值就会显得很奇怪。
销毁最前面就还是需要判断指针是否为空我们申请了动态空间当然要释放所以free必不可少其他的都给赋值为0。
//栈的初始化和销毁
void STInit(ST* pst)
{assert(pst);pst-a NULL;pst-top pst-capacity 0;
}
void STDestory(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-top pst-capacity;
}
1.2.3入栈
数组没有满时很简单就是把当前栈顶元素往后移动一位在赋值就可以了。
数组满时我们就要重新申请空间了什么时候是数组满了呢就那下面这个图理解top是5刚好capacity也是5。这时就满了所以就要扩容了。就和之前顺序表一样写就可以了。 void STPush(ST* pst, STDataType x)
{assert(pst);//扩容if (pst-top pst-capacity){int Newcapacity pst-capacity 0 ? 4 :pst-capacity * 2;STDataType* tmp (STDataType*)realloc(pst-a, Newcapacity * sizeof(STDataType));if (tmp NULL){perror(ralloc fail);return;}pst-a tmp;pst-capacity Newcapacity;}pst-a[pst-top] x;
}
1.2.4出栈
出栈就更简单了把栈顶指针向前移动一位就可以了。但是除了判别为空指针还要判别数组里面还有数据吗assert(pst-top 0);
void STPop(ST* pst)
{assert(pst);assert(pst-top 0);pst-top--;
}
1.2.5获取栈顶元素
这个功能实现也是非常简单要牢记top是指向栈顶元素的下一个元素。所以我们要top-1。
//获取栈数据
STDataType STTop(ST* pst)
{assert(pst);assert(pst-top 0);return pst-a[pst-top-1];
}
1.2.6获取栈中的有效个数
我们定义的top为0还有计数的作用所以直接返回top就行了。
int STSize(ST* pst)
{assert(pst);return pst-top;
}
1.2.7判空
我们直接使用具有计数作用的top判断是否等于0就可以知道是否为空栈了。
//栈的判空
bool STEmpty(ST* pst)
{assert(pst);return pst-top 0;
}
1.3 代码测试
#define _CRT_SECURE_NO_WARNINGS
#includeStack.h
int main()
{ST sa;STInit(sa);STPush(sa, 1);STPush(sa, 3);STPush(sa, 5);while (!STEmpty(sa)){printf(%d , STTop(sa));STPop(sa);}STDestory(sa);
} 实现了栈先进后出的特点。
1.4 头文件
#pragma once
#includestdio.h
#includestdlib.h
#includestdbool.h//bool 类型的头文件
#includeassert.htypedef int STDataType;typedef struct Stack
{STDataType* a;int top;//这里的top和顺序表的size相似的都是指有效元素的下一个数据。int capacity;
}ST;//栈的实现是通过数组所以只需要传一级指针。//栈的初始化和销毁
void STInit(ST* pst);
void STDestory(ST* pst);//入栈和出栈
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);//获取栈数据
STDataType STTop(ST* pst);//栈的判空
bool STEmpty(ST* pst);//栈的数据个数
int STSize(ST* pst); 总结 好了给大家介绍完了”栈“。下回介绍队列
