文章目录
- 对栈的理解
- 栈的实现 - 基于哪种常见类型演变而来的
- 栈的基本实现
- 栈实现总体代码
对栈的理解
栈的特点:先进后出。
- 入栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
- 出栈:栈的删除操作叫做出栈,出数据也在栈顶。
我们可以看出羽毛球桶,先放进去的羽毛球后拿出来,后放进去的羽毛球先拿出来,为了更好的理解进栈和出栈,笔者这里用简图表示一下
意思就是说,栈你如果要拿出一个,就是先拿出来后放进去的,要拿出来以前放进去的,就必须把后面放进去的全部拿出来才行
栈的实现 - 基于哪种常见类型演变而来的
我们先分析一下可能基于的对象,即
- 顺序表
- 链表
首先,我们可以看看双向链表,
双向链表固然是三者中最方便的,但是却逾越了栈的需求,通过双向链表,可以连接到前一个对象,也可以连接到后一个对象,但是栈仅需要堆最后放入对象,做出改变就行了
虽说,只要不用双向链表链向前者这一功能就行了,但是如果使用这种模式,却又不使用其功能,未免有些画蛇添足,浪费效能
再看看顺序表
首先,顺序表内存是连续的,所以可以随机访问,读取效率很高,O(1)。
物理(内存)上连续,逻辑上也连续:
顺序表的顺序存储结构,采用一组连续的内存来存储数据。
顺序表的线性关系是在内存(物理)上的相邻关系来表示数组的逻辑关系,也就是说,顺序表的连续和线性依靠的是内存的连续和线性。
因此,对于顺序表,我们可以取其精华,去其糟粕
既然这样,这样我们不妨看看两种之间的区别
所以,根据以上数组和链表的区别,我们可以思考在实现栈的时候,那种数据结构更好,因为栈只能在一端插入删除数据,插入删除数据的时候,只是在尾部进行插入删除,就不要去移动数据位置,这样我们就选择数组实现栈。
栈的基本实现
多看看注释哈!
首当其冲的就是栈的定义
//定义栈 typedef int STDataType; //设置栈内元素的类型 typedef struct Stack {STDataType* a; //创建装有指定元素的数组 int top; //标识栈顶,便于后续操作 int capacity; //栈内元素数量 }ST;//重命名结构体为ST
栈定义完后,自然需要对其初始化,以及销毁
// 初始化和销毁 void STInit(ST* pst) {//断言,不多说了 assert(pst); pst->a = NULL; // top指向栈顶数据的下一个位置 pst->top = 0; // top指向栈顶数据 //pst->top = -1; 初始化数量 pst->capacity = 0; } void STDestroy(ST* pst) {assert(pst); //直接释放整个数组 free(pst->a); pst->a = NULL; pst->top = pst->capacity = 0; //初始化时,top=0,表示指向栈顶的下一个元素 }
入栈 和 出栈
// 入栈 出栈 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)); //因为我们在栈的初始化的时候,我们没有申请数组大小,所以我们在插入数据在进行判断是否数据已经存满的时候,我们要去考虑数据个数为0的情况。 if (tmp == NULL) {perror("realloc fail"); 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; }
注意:
- 有的时候我们在使用的时候可能会不使用标准函数,及笔者上面所写的方法,但是这就好比正版有盗版的区分,
- 我们可以直接通过top–,使得栈顶元素消失,
- 也可以通过a[top-1]来获得栈顶元素
- 但是这是在我们知道内部函数运转规律且十分清楚的情况下,但凡有一丝与我们设想的不同,就可能导致运行失败,这样是大家都不想看到的,所以,为了是程序正常运行,大家还是尽量使用已经封装好的函数方法吧
栈实现总体代码
#pragma once #include
#include #include #include typedef int SLDataType; typedef struct Stack{SLDataType* a; int top; int capacity; }Stack; //对栈进行初始化 void StackInit(Stack* ptr); //对栈进行销毁 void StackDestroy(Stack* ptr); //在栈顶插入元素 void StackPush(Stack* ptr, SLDataType x); //获取栈顶元素 SLDataType StackTop(Stack* ptr); //对栈进行判断,如果为空,返回true,否则返回false bool StackEmpty(Stack* ptr); //获取栈里面的元素个数 int StackSize(Stack* ptr); void StackPop(Stack* ptr); //栈的初始化 void StackInit(Stack* ptr) {assert(ptr); ptr->a = NULL; ptr->capacity = ptr->top = 0; } //销毁栈 void StackDestroy(Stack* ptr) {assert(ptr); free(ptr->a); ptr->a = NULL; ptr->capacity = ptr->top = 0; //初始化时,top=0,表示指向栈顶的下一个元素 } //在栈顶插入元素 void StackPush(Stack* ptr, SLDataType x) {assert(ptr); if (ptr->top == ptr->capacity) {int newcapacity = ptr->capacity == 0 ? 4 : ptr->capacity * 2; SLDataType* tmp = (SLDataType*)realloc(ptr->a, newcapacity*sizeof(SLDataType)); if (tmp == NULL) {perror("realloc fail"); return; } ptr->a = tmp; ptr->capacity = newcapacity; } ptr->a[ptr->top++] = x; } //取栈顶元素 SLDataType StackTop(Stack* ptr) {assert(ptr); assert(!StackEmpty(ptr)); return ptr->a[ptr->top - 1]; } //栈判空 bool StackEmpty(Stack* ptr) {assert(ptr); return ptr->top == 0; } //销毁栈顶元素 void StackPop(Stack* ptr) {assert(ptr); assert(!StackEmpty(ptr)); ptr->top--; } //获取栈里面元素个数 int StackSize(Stack* ptr) {assert(ptr); return ptr->top; }