目录

一.创建栈

二.栈的初始化

三.入栈

四.判空

五.出栈

六.取栈顶元素

七.栈的长度

八.销毁

---

一.创建栈

        栈成员的结构体应该包括:存放数据的数组arr,栈顶元素下标top,栈容量capacity.因此创建Stack结构体类型时应由一个数组及两个整型组成.

        typedef方便后续在使用栈时对存储的数据类型做更改，可以修改为char,double,longlong.......等类型，一步到位。

代码如下：

//定义栈的结构
typedef int STDataType;
typedef struct Stack
{
	STDataType* arr;
	int top;     //指向栈顶的位置
	int capacity;//栈的容量
}ST;

---

二.栈的初始化

        初始化栈的逻辑和初始化顺序表相同。起初不知道arr数组的地址，初始化为NULL，top和capacity初始化为0即可。

代码如下：

//初始化
void StackInit(ST* ps)
{
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

---

三.入栈

        在入栈时,需要和顺序表的尾插头插等插入操作一样先判断一下栈内元素是否已满,如果满了则需要给栈扩容。不过由于栈的特点是后进先出，先进后出。只能在栈顶入栈和出栈，所以不存在尾插头插任意位置的插入，所以不需要再将增容步骤封装为函数了。

        如果没满则将新元素赋值给栈顶指针top,再将top++,使其始终指向栈顶的下一个元素位置。

代码如下：

//入栈---栈顶
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		//增容
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
	ps->arr[ps->top++] = x;
}

---

四.判空

        判空的代码需要断言，如果栈不存在就无法判空。如果top值为0返回true，否则返回false。

代码如下：

//栈是否为空
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

---

五.出栈

        出栈相当于顺序表的尾删。由于栈只能在栈顶出栈，所以不存在尾删头删任意位置的删除等操作，相比于顺序表代码更加简单。

        在出栈前要注意栈内元素是否为空，空的话无法出栈

代码如下：

//出栈——栈顶
void StackPop(ST* ps)
{
	assert(!StackEmpty(ps));
	--ps->top;
}

---

六.取栈顶元素

        栈顶就是top-1，取栈顶元素即是取 ps->arr[ps->top-1] 位置的元素。

        同样要注意，这里只是取元素，并没有出栈顶元素哦。

代码如下：
 

//取栈顶元素
STDataType StackTop(ST* ps)
{
	assert(!StackEmpty(ps));
	return ps->arr[ps->top - 1];
}

---

七.栈的长度

        因为top指向的是栈顶元素的下一个位置,因此top的大小正好是栈的长度,所以求栈长直接对ps断言后可以直接返回top.

代码如下：

//获取栈中有效元素个数
int StackSize(ST* ps)
{
    assert(ps);
	return ps->top;
}

---

八.销毁

        使用完栈想要退出函数时,就应该将之前动态开辟的内存释放掉,还给操作系统，即销毁栈。我们使用free()函数释放掉之前动态开辟的数组arr,然后将arr置为空指针,最后将top,capacity的值置为0即可。

代码如下：

/销毁
void StackDestroy(ST* ps)
{
	if (ps->arr)
		free(ps->arr);
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

---

        希望对大家有帮助，共勉！