目录
一、栈的概念
栈,是一种后进先出（Last In First Out，简称LIFO）的数据结构,是限制在一端进行插入操作和删除操作的线性表（俗称堆栈）,在栈中，允许进行操作的一端称为“栈顶”，另一固定端称为“栈底”。
二、栈的相关操作
初始化栈（Init）：
创建一个新的空栈的过程。
销毁栈（Destroy）：
释放栈使用的资源并使栈不再可用的过程。
入栈（Push）：
将一个元素添加到栈。
出栈（Pop）：
弹出栈顶元素。
查看栈顶（Top）：
返回栈顶元素，但不移除它。
判断栈是否为空（isEmpty）：
检查栈内是否有元素。
获取栈的大小（Size）：
返回栈中元素的数量。
三、栈的实现
栈通常可以用数组和链表两种方式实现。由于栈只使用一端进行操作，因此数组结构更好一些。令数组头部为栈底，数组尾部为栈顶。
栈又分为静态栈和动态栈。
静态栈：
- 使用固定大小的数组实现。
- 大小在初始化时设定，之后不能改变。
- 优点是实现简单，存取速度快。
- 缺点是大小固定，可能会有空间浪费或容量不足的问题。
动态栈：
- 优点是灵活，可以根据实际需求调整容量，避免空间浪费。
- 缺点是相比静态栈，可能在存取速度上略慢，且实现复杂度高。
为了能够灵活使用栈，不浪费空间 ，因此使用动态栈更好。入栈和出栈操作类似于静态数组实现，但在数组容量不足时会自动进行扩展。
我们将栈的全部代码分在三个文件内完成：
一个头文件：Stack.h（定义栈）
两个源文件：Stack.c(实现栈中的操作）
test.c（测试栈）
定义栈的结构
STDataType *a：
这是一个指向 STDataType 类型的指针，即它指向栈中存储元素的数组。
这里 STDataType 被定义为 int 类型，意味着栈中存储的是整数。如果需要在栈中存储其他类型的数据，只需要更改语句typedef int STDataType;中的int即可。
int top：
这是一个整数索引用于跟踪栈顶的位置，top 通常用来表示栈中最后一个已存储元素的索引位置。栈的插入（push）和删除（pop）操作主要通过改变 top 的值来进行。
int capacity：
这是一个整数，表示栈的容量，即栈可以存储的元素的数量。这个值在初始化栈的时候设定为0，可以用来检测栈是否已满是否需要扩容，以避免越界。
typedef int STDataType;
typedef struct Stack
{
STDataType *a;
int top;
int capacity;
}ST; 初始化栈
这一部分的主要内容就是如何初始化指向顶部的整数索引， 有top设置为0和top设置为-1两种方式，top=0，意味着top指向栈顶元素的下一个位置，top=-1意味着top指向栈顶元素。
- 当将top置为0时，表示栈为空。这与数组的习惯索引方式一致。
- 可以更直观地表示栈的空状态，这使得实现简单，不需要额外的计算或者特殊情况的处理。
所以将top置为0。
void STInit(ST* st)
{
assert(st);
st->a = NULL;
//top指向栈顶元素的下一个位置
st->top = 0;
st->capacity = 0;
}入栈
入栈（Push）是栈的一个基本操作，它将一个新元素添加到栈的顶部。由于栈是一种后进先出的数据结构，因此最后被推入栈的元素将会是第一个被取出的。
我们需要以下步骤：
- 检查栈是否已满：如果栈已经满了则需要扩容。
- 将元素放在栈顶位置：如果栈未满，将新元素放置在栈顶的当前位置上。
- 更新栈顶指针：增加栈顶的索引，指向下一个可用的存储位置。
void STPush(ST* st, STDataType x)
{
//检查栈是否满
if (st->top == st->capacity)
{
//如果栈满了则需要扩容
int newCapacity = st->capacity == 0 ? 4 : st->capacity * 2;
STDataType* tmp = (STDataType*)realloc(st->a, sizeof(STDataType) * newCapacity);
//判断是否扩容成功
if (tmp == NULL)
{
perror("realloc");
exit(-1);
}
st->a = tmp;
st->capacity = newCapacity;
}
//将元素放在栈顶位置
st->a[st->top] = x;
//更新栈顶指针
st->top++;
}出栈
出栈（Pop）是栈的一个基本操作，它将弹出栈顶的元素。
我们需要以下步骤：
- 断言栈是否为空：首先检查栈是否有元素可以移除。如果栈为空，这个操作可能会引发错误。
- 移动栈顶指针：将栈顶指针向下移动，以指向上一个元素，从而从栈中移除当前的栈顶元素。
void STPop(ST* st)
{
assert(st);
assert(st->top>0);
--st->top;
}assert(st)： 用于确保参数 st 是一个非空指针，因为在函数中后续的代码中，st 被用来访问栈结构体的成员。如果 st 是一个空指针，那么后续的代码可能会导致未定义行为或者崩溃，为了避免这种情况，使用 assert(st)进行了检查。
查看栈顶元素
查看栈顶，它允许访问栈顶的元素但不从栈中移除这个元素。这个操作是非常有用的，因为它允许你查看栈的最新状态而不改变栈的内容。
我们需要以下步骤：
- 检查栈是否为空：首先确认栈中是否有元素。如果栈为空，这个操作可能会返回错误。
- 返回栈顶元素：如果栈不为空，直接返回栈顶元素，而不改变栈的结构或元素的位置。由于top指向栈顶元素的下一个位置。所以要将top-1返回。
STDataType STtop(ST* st)
{
assert(st);
assert(st->top > 0);
return st->a[st->top-1];
}判断栈是否为空
判断栈是否为空这个操作用于检查栈中是否有元素。如果栈为空，表示没有任何元素可以进行出栈或查看栈顶的操作。
我们需要以下步骤：
返回栈顶指针是否为0：由于我们初始化top为0，因此如果top为0，则栈为空，返回
true；如果栈不为空，返回false。
bool isEmpty(ST* st)
{
assert(st);
return st->top == 0;
}返回栈中元素的个数
获取栈的大小是指查询当前栈中有多少元素的操作。这个操作对于管理栈的容量和监控栈的使用情况非常有用。
我们需要以下步骤：
1.返回top：因为top初始化为0，每当添加了一个元素后，top+，因此直接返回top即可得到栈中元素的个数。
int STsize(ST* st)
{
assert(st);
return st->top;
}销毁栈
这是在栈的生命周期结束时进行的，确保不会造成内存泄漏或其他资源管理问题。
我们需要以下步骤：
- 释放内存：通过 free(st->a);释放动态分配的内存，以免造成内存泄漏。
- 清空指针：将 st->a 设置为 NULL，以避免在函数外部误用已经释放的内存地址。
- 重置栈状态：将栈的 capacity、top 设置为0，这是为了确保在销毁之后，栈处于一个空的状态。
void STDestroy(ST* st)
{
assert(st);
free(st->a);
st->a = NULL;
st->capacity = st->top = 0;
} 在某些编程环境中，如使用自动内存管理的语言（例如 Java 或 Python），销毁栈可能仅需简单地将栈对象的引用设为null或None，让垃圾收集器自动清理。然而，在手动内存管理的环境（如 C 或 C++），开发者需要明确地编写代码来释放内存和资源，避免内存泄漏。
至此，栈的全部操作实现完毕。
四、完整代码：
Stack.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{
STDataType *a;
int top;
int capacity;
}ST;
//初始化栈
void STInit(ST* st);
//销毁栈
void STPop(ST* st);
//入栈
void STPush(ST* st, STDataType x);
//出栈
void STDestroy(ST* st);
//返回栈中元素的个数
int STsize(ST* st);
//判断栈是否为空
bool isEmpty(ST* st);
//返回栈顶元素
STDataType STtop(ST* st);Stack.c
#include"Stack.h"
//初始化栈
void STInit(ST* st)
{
assert(st);
st->a = NULL;
//top指向栈顶元素的下一个位置
st->top = 0;
st->capacity = 0;
}
//入栈
void STPush(ST* st, STDataType x)
{
if (st->top == st->capacity)
{
int newCapacity = st->capacity == 0 ? 4 : st->capacity * 2;
STDataType* tmp = (STDataType*)realloc(st->a, sizeof(STDataType) * newCapacity);
if (tmp == NULL)
{
perror("realloc");
exit(-1);
}
st->a = tmp;
st->capacity = newCapacity;
}
st->a[st->top] = x;
st->top++;
}
//销毁栈
void STDestroy(ST* st)
{
assert(st);
free(st->a);
st->a = NULL;
st->capacity = st->top = 0;
}
//出栈
void STPop(ST* st)
{
assert(st);
assert(st->top>0);
--st->top;
}
//返回栈中元素的个数
int STsize(ST* st)
{
assert(st);
return st->top;
}
//判断栈是否为空
bool isEmpty(ST* st)
{
assert(st);
return st->top == 0;
}
//返回栈顶元素
STDataType STtop(ST* st)
{
assert(st);
assert(st->top > 0);
return st->a[st->top-1];
}test.c
#include"Stack.h"
void test()
{
ST st;
STInit(&st);
STPush(&st, 1);
STPush(&st, 2);
STPush(&st, 3);
STPush(&st, 4);
while (!isEmpty(&st))
{
printf("%d\n",STtop(&st));
STPop(&st);
}
STDestroy(&st);
}
int main()
{
test();
return 0;
}
