13518219792
栈的接口栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶 (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元起，快前往官网查看详情吧
