文章目录

• 栈的定义
• 栈的接口
• • 元素定义
  • 初始化
  • 数据入栈
  • 数据出栈
  • 获取栈顶元素
  • 是否为空
  • 销毁栈
  • 完整代码

团风ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景，ssl证书未来市场广阔！成为成都创新互联的ssl证书销售渠道，可以享受市场价格4-6折优惠！如果有意向欢迎电话联系或者加微信：028-86922220（备注：SSL证书合作）期待与您的合作！栈的定义

栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶 (top)，另一端为栈底 (bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。特点是：先进后出，后进先出。

栈的接口

首先我们先来看将使用3个数据{2，3，4}形成栈的示意图：

元素定义

由定义可知，栈是线性表，可以分为顺序存储结构（顺序表）和链式存储结构（链表）来实现，下面我们用数组来实现，即实现它的顺序存储结构，其次我们知道他是可以获取堆顶元素的，所以我们还需要一个top指针记录栈顶的位置（这个不是真正意义上的指针，而是记录栈顶元素的位置），且因为我们是动态开辟实现栈，所以我们还需要一个capacity来记录当前的元素个数（相当于size),以检查是否需要进行扩容
定义如下：

typedef int Datatype;    //此处是为了方便栈存放不同的元素类型

typedef struct Stack {Datatype* a;        //管理数组
	int top;//栈顶元素下标
	int capacity;//记录当前容量大小
}Stack;

初始化

栈的初始化就较为简单了，将a置空（相当于初始化），top和capacity=0,
即可
代码实现如下：

//初始化函数
void InitStack(Stack* st)
{assert(st);

	st->a = NULL;
	st->capacity = 0;
	st->top = -1;   //指向栈顶元素
}

这里的top=-1,表示的状态是数组中没有元素，因为有元素的话，比如说如果数组中有一个元素，top就等于0，即数组第一个元素的下标位置

数据入栈

数据入栈的操作就是，将新值插入到数组末尾，然后更新top和capacity，
代码如下：

//入栈
void Push(Stack* st,Datatype x)
{assert(st);
	if (st->capacity == (st->top + 1))
	{int newcapacity = st->capacity == 0 ? 4 : 2 * st->capacity;
		Datatype* tmp = (Datatype*)realloc(st->a,sizeof(Datatype) * newcapacity);
		if (tmp == NULL)   //开辟失败，tmp会指向空
		{	printf("realloc failed\n");
			exit(-1);//终止程序
		}

		st->a = tmp;
		st->capacity = newcapacity;
	}

		st->a[++st->top] = x;
}

数据出栈

数据出栈实现也很简单，我们直接逻辑删除，就是将capacity–，元素的值其实还在数组中，只是我们假装看不见 😐 ,但简单是简单这里还是有坑点的，就是我们删除数据的时候，如果栈已经空了，我们还进行删除操作，就会影响后续的使用，所以我们每次都要先判断栈是否为空
代码实现如下：

//出栈
void Pop(Stack* st)
{assert(st);
	if (!empty(st))
	{--st->top;
	}

}

获取栈顶元素

这里提一下，我们函数实现时判断一些空指针或者不可进行操作的情况时，例如：下面当栈为空时还去获取栈顶元素。这些情况的判断最好都用assert去判断，因为当我们代码行数多起来时，那个接口出了问题，会马上被显示出来还有行号。
例：
如果栈中没有数据，而我们还去获取栈顶元素，他不仅会报错而且还会告诉我们哪个位置出的错

代码实现：

//拿到栈顶元素
Datatype top(Stack* st)
{assert(st);
	//if (!empty(st))//此处也可用assert
	//{//	return st->a[st->top];
	//}
	assert(!empty(st));
	return st->a[st->top];
}

是否为空

这里注意如果要使用c++中的bool类型，要印=引头文件

//检查是否为空
bool empty(Stack* st)
{assert(st);

	return st->top == -1;//为0即为空 为真true
}

销毁栈

销毁栈的操作其实就是在初始化的基础上，将我们数据入栈时，为我们的数组管家a动态开辟的内存空间释放掉，这里如果单纯置空而不进行释放操作，会造成内存泄漏

//销毁栈
void Destroy(Stack* st)
{assert(st);
	free(st->a);
	st->a = NULL;
	st->capacity = 0;
	st->top = -1;
}

完整代码

//初始化函数
void InitStack(Stack* st)
{assert(st);

	st->a = NULL;
	st->capacity = 0;
	st->top = -1;//指向栈顶元素
}
//入栈
void Push(Stack* st,Datatype x)
{assert(st);
	if (st->capacity == (st->top + 1))
	{int newcapacity = st->capacity == 0 ? 4 : 2 * st->capacity;
		Datatype* tmp = (Datatype*)realloc(st->a,sizeof(Datatype) * newcapacity);
		if (tmp == NULL)
		{	printf("realloc failed\n");
			exit(-1);//终止程序
		}

		st->a = tmp;
		st->capacity = newcapacity;
	}

		st->a[++st->top] = x;
}
//出栈
void Pop(Stack* st)
{assert(st);
	if (!empty(st))
	{--st->top;
	}

}
//检查是否为空
bool empty(Stack* st)
{assert(st);

	return st->top == -1;//为0即为空 为真true
}
//拿到栈顶元素
Datatype top(Stack* st)
{assert(st);
	//if (!empty(st))//此处也可用assert
	//{//	return st->a[st->top];
	//}
	assert(!empty(st));
	return st->a[st->top];
}
//销毁栈
void Destroy(Stack* st)
{assert(st);
	free(st->a);
	st->a = NULL;
	st->capacity = 0;
	st->top = -1;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

分享名称：c语言模拟实现栈（动图演示）-创新互联
链接URL：http://csdahua.cn/article/ccpeps.html