ps做图哪个网站好,注册科技公司需要什么条件,简单大气网站源码,优秀平面广告设计赏析提示#xff1a;文章写完后#xff0c;目录可以自动生成#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、栈是什么#xff1f;二、栈的实现思路1.顺序表实现2.单链表实现3.双向链表实现 三、接口函数的实现1.栈的定义2.栈的初始化3.栈的销毁4.入栈5.出栈6.返回栈… 提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档 文章目录 前言一、栈是什么二、栈的实现思路1.顺序表实现2.单链表实现3.双向链表实现 三、接口函数的实现1.栈的定义2.栈的初始化3.栈的销毁4.入栈5.出栈6.返回栈顶元素7.判空8.返回栈中数据个数 四、文件总览1.头文件2.功能函数3.测试文件 总结 前言
栈是一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。在数据结构中栈是比较简单的一种结构。 一、栈是什么
堆栈又名栈stack它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶相对地把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈它是把新元素放到栈顶元素的上面使之成为新的栈顶元素从一个栈删除元素又称作出栈或退栈它是把栈顶元素删除掉使其相邻的元素成为新的栈顶元素。
二、栈的实现思路
1.顺序表实现
代码如下示例
typedef struct StackList
{STDataType* a; //指向动态开辟的空间int top; //栈顶所在下标的下一位也可以指向栈顶int capacity;//栈容量
}ST;2.单链表实现
代码如下示例
typedef struct StackNode
{STDataType x;//数据StackNode* next;//指针域指向下一结点
}ST;
struct Stack
{ST* phead;//指向第一个结点ST* ptail;//指向尾结点
}3.双向链表实现
typedef struct StackNode
{STDataType x;//数据StackNode* next;//指向下一结点StackNode* prev;//指向上一结点
}ST;
struct Stack
{ST* phead;//指向第一个结点ST* ptail;//指向尾结点
}在这里我们推荐采用顺序表来实现对栈的操作原因如下
栈的特性利用了顺序表尾插尾删效率高的特性虽然有时需要扩容但是链表创建结点也同样需要成本而顺序表扩容频率不像链表一样如此频繁。链表频繁开辟节点也是很耗时的。我们知道CPU与主存速度上存在巨大差距为了提高效率CPU和主存之间还存在着高速缓存。 CPU访问缓存的速度是快于主存。每次CPU取数据时会访问缓存看看存不存在所需的数据如果不存在才会访问主存然后将数据所在的内存块加载到缓存中。由于顺序表空间是连续的根据缓存的空间局部性原理采用顺序表命中率会高于链表所以效率高。
三、接口函数的实现
1.栈的定义
typedef int STDataType;
typedef struct Stack
{STDataType* a;//动态开辟内存int top;//栈顶的下一位int capacity;栈的容量
}ST;这里top定义为栈顶下一位是为了下面下表访问方便也可以定义为指向栈顶的top可以根据个人需要决定。
2.栈的初始化
void STInit(ST* pst)
{assert(pst);pst-a NULL;pst-capacity 0;pst-top 0;
}初始化时空间a先置空指针capacity和top置零这是栈没有数据top指向0也确实是栈顶的下一位。
3.栈的销毁
void STDestroy(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-capacity pst-top 0;
}先对pst进行assert断言再对开辟的空间进行释放将指针置零capacity和top置零即可。
4.入栈
void STPush(ST* pst, STDataType x)
{assert(pst);if (pst-capacity pst-top){int newcapacity pst-capacity 0 ? 4 : 2 * pst-capacity;STDataType*tmp(STDataType*)realloc(pst-a, newcapacity*sizeof(STDataType));if (tmp NULL){perror(realloc);return;}pst-a tmp;pst-capacity newcapacity;}pst-a[pst-top] x;pst-top;
}入栈需要注意的点是判断是否容量够用当capacity和top相等时存满需要扩充。在扩充时需要判断原容量是不是0这里进行一个三目操作符判断。之后就是realloc扩容最后将相应的capacity和top修改就行。
5.出栈
void STPop(ST* pst)
{assert(pst);assert(pst-top 0);pst-top--;
}出栈时应判断栈是否为空所以这里除了判断pst的有效性还要判断top的位置。最后让top向前移一位就进行了出栈。
6.返回栈顶元素
STDataType STTop(ST* pst)
{assert(pst);assert(pst-top 0);return pst-a[pst-top-1];
}判断pst有效性和栈是否为空再将栈顶的元素返回即可。
7.判空
bool STEmpty(ST* pst)
{assert(pst);return pst-top 0;
}这里需要返回bool类型需要加stdbool.h头文件。当top为零时栈为空返回true否则返回false。
8.返回栈中数据个数
int STSize(ST* pst)
{assert(pst);return pst-top;
}这里因为我们的top指向栈顶数据的下一位所以top即为数据个数。返回即可。
四、文件总览
1.头文件
#pragma once
#includestdio.h
#includestdbool.h
#includeassert.h
#includestdlib.htypedef 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);// 取栈顶数据
STDataType STTop(ST* pst);// 判空
bool STEmpty(ST* pst);
// 获取数据个数
int STSize(ST* pst);2.功能函数
#includeStack.hvoid STInit(ST* pst)
{assert(pst);pst-a NULL;pst-capacity 0;pst-top 0;
}void STDestroy(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-capacity pst-top 0;
}void STPush(ST* pst, STDataType x)
{assert(pst);if (pst-capacity pst-top){int newcapacity pst-capacity 0 ? 4 : 2 * pst-capacity;STDataType*tmp(STDataType*)realloc(pst-a, newcapacity*sizeof(STDataType));if (tmp NULL){perror(realloc);return;}pst-a tmp;pst-capacity newcapacity;}pst-a[pst-top] x;pst-top;
}void STPop(ST* pst)
{assert(pst);assert(pst-top 0);pst-top--;
}STDataType STTop(ST* pst)
{assert(pst);assert(pst-top 0);return pst-a[pst-top-1];
}bool STEmpty(ST* pst)
{assert(pst);return pst-top 0;
}int STSize(ST* pst)
{assert(pst);return pst-top;
}
3.测试文件
int main()
{// 入栈1 2 3 4// 出栈4 3 2 1 / 2 4 3 1ST s;STInit(s);STPush(s, 1);STPush(s, 2);printf(%d , STTop(s));STPop(s);STPush(s, 3);STPush(s, 4);while (!STEmpty(s)){printf(%d , STTop(s));STPop(s);}STDestroy(s);
}总结
这就是本期文章的全部内容期待你的一键三连和评论。
