【C语言】实现栈

---

目录

（一）栈

（二）头文件 

（三）功能实现

（1）初始化栈

（2） 栈的销毁

（3）压栈

（4） 出栈

（5） 取出栈顶元素

（6）判断栈是否为空

（7）得到栈的数据个数

---

正文开始：

（一）栈

        栈是一种常见的数据结构，遵循“后进的数据先出”（Lsat In First Out）的原则。

        栈有两个主要的操作：入栈和出栈。入栈（push）操作将一个元素添加到栈的顶部，而出栈（pop）操作则将栈顶的元素移除。

        栈可以用于解决各种问题，例如实现函数调用栈、表达式求值、回溯算法等。在计算机内存中，栈也常用于存储函数的局部变量、函数调用的上下文信息以及程序的返回地址等。

        栈通常可以使用数组或链表等数据结构来实现。

        使用数组实现的栈称为顺序栈，它具有固定大小的容量；

        而使用链表实现的栈称为链式栈，它可以动态地增长和缩小。

        除了入栈和出栈操作，栈还可以提供其他常见的操作，如获取栈顶元素（top）和判空（isEmpty）。此外，还可以通过计算栈的长度来得知栈中元素的数量。

        

（二）头文件 

         本文根据Cpp的STL来实现栈的相关功能：包括栈的初始化，销毁，压栈，出栈，得到栈顶元素，判断栈是否为空，得到栈内元素个数等共七个功能。

        头文件如下：

        命名：Stack.h

         栈可以用顺序表实现，也可以用链表实现（由于单链表尾插效率低，所以用单链表的头作为栈顶）；

        本文基于顺序表实现栈；

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
//栈数据类型
typedef int StackDatatype;
 
//一个栈
typedef struct Satck
{
	StackDatatype* a;
	int top;
	int capacity;
}SK;
//初始化
void STInit(SK* st);
 
//销毁
void STDestory(SK* st);
 
//压栈
void STPush(SK* st,StackDatatype x);
 
//出栈
void STPop(SK* st);
 
//取出栈顶元素
StackDatatype STTop(SK* st);
 
//栈是否空
bool STEmpty(SK* st);
 
//得到栈的数据个数
int STSize(SK* st);

（三）功能实现

（1）初始化栈

初始化栈

        首先函数接收的指针不为空（否则无法解引用），通过assert断言完成；

        顺序表数组置空，容量（capacity）和栈顶下一个元素的下标（top）都为0（top表示栈顶元素的下一个元素的下标，top==0表示此时栈内没有任何元素）；

 
//初始化
void STInit(SK* st)
{
	assert(st);
 
	st->a = NULL;
	st->capacity = st->top = 0;
}

（2） 栈的销毁

 销毁栈

        首先函数接收的指针不为空（否则无法解引用），通过assert断言完成；

        顺序表动态申请的数组释放掉，并置空；

        容量和栈顶元素都置0；

 
//销毁
void STDestory(SK* st)
{
	assert(st);
	st->capacity = st->top = 0;
	free(st->a);
	st->a = NULL;
}

（3）压栈

         由于栈基于顺序表实现，所以需要判断顺序表是否已经满了，如果栈顶下一个元素的下标等于此时容量，表明栈已满，需要扩容；

        Newcapacity的赋值通过三目操作符实现：如果capacity为初始值0，Newcapacity赋值为4，否则赋值为2*capacity；

        如果realloc申请失败，打印错误信息并返回；

        若申请成功，压入数据；

//压栈
void STPush(SK* st, StackDatatype x)
{
	assert(st);
 
	if (st->capacity == st->top)
	{
		int Newcapacity = st->capacity == 0 ? 4 : st->capacity * 2;
		StackDatatype* tem = (StackDatatype*)realloc(st->a, sizeof(StackDatatype) * Newcapacity);
		if (tem == NULL)
		{
			perror("realloc fail!");
			return;
		}
		st->a = tem;
		st->capacity = Newcapacity;
	}
	st->a[st->top++] = x;
 
}

（4） 出栈

        首先函数接收的指针不为空（否则无法解引用），通过assert断言完成；

        其次，栈不为空；

        只需top--，就实现了出栈操作（不需要抹除数据，因为出栈的数据已经无法通过正常方法访问了）；

 
//出栈
void STPop(SK* st)
{
	assert(st);
	assert(!STEmpty(st));
 
	st->top--;
}

（5） 取出栈顶元素

        首先函数接收的指针不为空（否则无法解引用），通过assert断言完成；

        其次，栈不为空；

        直接返回栈顶元素（top是栈顶元素的下一个元素的下标）；

//取出栈顶元素
StackDatatype STTop(SK* st)
{
	assert(st);
	assert(!STEmpty(st));
 
	return st->a[st->top-1];
}

（6）判断栈是否为空

        首先函数接收的指针不为空（否则无法解引用），通过assert断言完成；

        这里返回判断表达式的值，表达式成立值为真（1），否则值为假（0）；【这是很巧妙的写法】

 
//栈是否空
bool STEmpty(SK* st)
{
	assert(st);
	return st->top == 0;
}

（7）得到栈的数据个数

         首先函数接收的指针不为空（否则无法解引用），通过assert断言完成；

        返回数据个数（下标从0开始，数据个数就是栈顶元素下一个元素的下标）；

 
//得到栈的数据个数
int STSize(SK* st)
{
	assert(st);
	return st->top;
}

 

---

完~

未经作者同意禁止转载