栈的介绍

栈（stack）是限定仅在表尾进行插入和删除操作的线性表。
我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈。栈又被称为后进先出（LastIn First Out）的线性表，简称LIOF结构。
首先它是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系。只不过它是一种特殊的线性表而已。

代码实现

栈一般的实现都是用顺序存储结构进行实现的，上次我们在栈的顺序存储结构及实现（一）采用的数组进行实现，但是数组有个瓶颈就是固定了栈的长度，这次我们才采用动态获取内存空间，当压栈时如果栈满进行动态的扩充容量，进行栈的实现。

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define STACK_INIT_SIZE 5
#define STACK_INCREMENT 5
typedef int Status;
typedef int EleType;
typedef struct SeqStack
{
    EleType* top;//栈顶指针
    EleType* base;//栈底指针
    int stackSize;//栈容量
}SeqStack;
//初始化栈
Status InitStack(SeqStack* stack)
{
    //开辟空间
    stack->base = stack->top = (EleType*)malloc(STACK_INIT_SIZE*sizeof(EleType));
    if (!stack->base)
    {
        exit(0);
    }
    return OK;
}
/*
清空栈
*/
Status ClearStack(SeqStack* stack) {
    if (NULL == stack) {
        return ERROR;
    }
    //清空栈 实质上是忽略栈中数据，可以再次使用内存单元
    stack->top = stack->base;
    return OK;
}
/*
销毁栈
*/
Status DestroyStack(SeqStack* stack)
{
    if (NULL == stack) {
        return ERROR;
    }
    //销毁栈 是释放栈在内存中占用的空间资源
    if (!stack->base)
    {
        free(stack->base);
    }
    stack->top = stack->base = NULL;
    stack->stackSize = 0;
    return OK;
}
//获取栈长度（栈中元素个数）
int LengthStack(SeqStack stack)
{
    return stack.top - stack.base;
}
//压栈
Status push(SeqStack* stack,EleType e)
{
    if (stack == NULL)
    {
        return ERROR;
    }
    //压栈之前检测容量是否足够
    if (stack->top - stack->base == stack->stackSize)
    {
        //超出容量 进行扩容，使用realloc函数，会拷贝原内存内容
        stack->base = (SeqStack*)realloc(stack->base, stack->stackSize+STACK_INCREMENT);
        if (!stack->base)
        {
            exit(0);
        }
        stack->top = stack->base + stack->stackSize;
        stack->stackSize += STACK_INCREMENT;
    }
    *stack->top = e;
    stack->top++;
    return OK;
}
//弹栈
Status pop(SeqStack* stack, EleType *e)
{
    if (stack == NULL || e == NULL)
    {
        return ERROR;
    }
    //空栈
    if (stack->top == stack->base)
    {
        return ERROR;
    }
    *stack->top--;
    *e = *stack->top;
    return OK;
}
/*
判断栈是否为空
*/
int IsEmptyStack(SeqStack* stack) {
    if (NULL == stack) {
        return ERROR;
    }
    if (stack->top == stack->base) {
        return TRUE;
    }
    return FALSE;
}
/*
获取栈顶元素
*/
Status GetTop(SeqStack* stack, EleType *e) {
    if (NULL == stack) {
        return ERROR;
    }
    *e = *(stack->top - 1);
    return OK;
}
/*
从栈顶向下展示元素值
*/
Status ShowStack(SeqStack* stack) {
    if (NULL == stack || stack->top == stack->base) {
        return ERROR;
    }
    EleType *top = stack->top;
    while (top != stack->base)
    {
        top--;
        printf("%d\n", *top);
    }
    return OK;
}
int main(int argc, char *argv[])
{
    SeqStack stack;//创建顺序栈
    InitStack(&stack);//初始化
    printf("压入元素5,4,3,2,1\n");
    push(&stack, 5);
    push(&stack, 4);
    push(&stack, 3);
    push(&stack, 2);
    push(&stack, 1);
    puts("栈元素展示：");
    ShowStack(&stack);
    puts("弹出2个元素后");
    puts("栈元素展示：");
    EleType e1, e2,e3;
    pop(&stack, &e1);
    pop(&stack, &e2);
    ShowStack(&stack);
    printf("弹出元素为:%d,%d\n", e1, e2);
    //测试是否动态扩充容量
    push(&stack,8);
    push(&stack,9);
    push(&stack,10);
    printf("压入元素8,9,10\n");
    puts("栈元素展示：");
    ShowStack(&stack);
    GetTop(&stack, &e3);
    printf("栈顶元素为:%d\n", e3);
    DestroyStack(&stack);
    return 0;
}