栈：
1.存取数据遵循LIFO(先进后出)原则的线性存储结构
2.在线性表的一端插入、删除、访问节点

栈的实现

1.顺序表形式

将顺序表的有效长度作为栈顶指针，在顺序表的末尾删除和插入节点

1.1 定义结构

• 定义数据类型 Datatype
• 定义顺序表类型的栈
  存放的数据地址：data
  存放的数据个数：size

// 数据类型
typedef int Datatype;
// 栈：顺序表形式
typedef struct Stack{
    Datatype* data;
    size_t size;
} Stack;

1.2 创建栈

// 函数：创建栈
Stack* Create_stack(){
    Stack* stack = malloc(sizeof(Stack));
    stack->data = NULL;
    stack->size = 0;
    return stack;
}

1.3 获取栈中元素个数

// 函数：获取栈中元素个数
size_t GetSize_stack(Stack* stack){
    return stack->size;
}

1.4 获取栈顶指针

// 函数：获取栈顶元素
Datatype* GetTop_stack(Stack* stack){
    if(NULL == stack) return NULL;
    if(0 == stack->size) return NULL;
    return stack->data+stack->size-1;
}

1.5 入栈

// 函数：进栈
// 尾添加
bool Push_stack(Stack* stack,Datatype push_data){
    if(NULL == stack) return false;
    stack->size++;
    stack->data = realloc(stack->data,stack->size*sizeof(Datatype));
    stack->data[stack->size-1] = push_data;
    return true;
}

1.6 出栈

// 函数：出栈
bool Pop_stack(Stack* stack){
    if(NULL == stack) return false;
    if(0 == stack->size) return false;
    stack->size--;
    stack->data = realloc(stack->data,stack->size*sizeof(Datatype));
}

1.7 销毁栈

// 函数：销毁栈
void Destory_stack(Stack** stack){
    if(NULL == stack) return;
    if(NULL == *stack) return;
    free((*stack)->data);
    (*stack)->data = NULL;
    free(*stack);
    *stack = NULL;
}

2.链表形式

将链表的头节点作为栈顶指针，入栈采用头添加的方式，出栈采用头删除的方式

2.1 定义结构

• 定义数据类型 Datatype
• 定义节点
  存放的数据data
  指向下一个节点的地址next
• 定义链表形式栈
  栈顶指针header
  栈内元素个数size

// 数据类型
typedef int Datatype;
// 定义节点
typedef struct Node{
    Datatype data;
    struct Node* next;
} Node;
// 定义链表形式的栈
typedef struct Stack{
    Node* header;
    size_t size;
} Stack;

2.2 创建栈

// 函数：创建栈
Stack* Create_stack(){
    Stack* stack = malloc(sizeof(Stack));
    stack->header == NULL;
    stack->size = 0;
    return stack;
}

2.3 获取栈中元素个数

// 函数：获取栈中元素个数
size_t GetSize_stack(Stack* stack){
    return stack->size;
}

2.4 获取栈顶指针

// 函数：获取栈顶元素
Datatype* GetData_stack(Stack* stack){
    return &(stack->header->data);
}

2.5 入栈

• 首添加

// 函数：入栈
bool Push_stack(Stack* stack,Datatype push_data){
    if(NULL == stack) return false;
    // 创建新的节点（栈元素）
    Node* new_node = malloc(sizeof(Node));
    new_node->data = push_data;
    
    new_node->next = stack->header;
    stack->header = new_node;
    stack->size++;
    return true;
}

2.6 出栈

• 首删除

// 函数：出栈
bool Pop_stack(Stack* stack){
    if(NULL == stack) return false;
    if(NULL == stack->header) return false;
    Node* del_node = stack->header;
    stack->header = del_node->next;
    free(del_node);
    del_node = NULL;
    stack->size--;
    return true;
}

2.7 销毁栈

// 函数：销毁栈
void Destory_stack(Stack** stack){
    if(NULL == stack) return;
    if(NULL == *stack) return;

    Node* p = (*stack)->header;
    while(NULL != p){
        Node* free_node = p;
        p = p->next;
        free(free_node);
        free_node = NULL;
    }
    free(*stack);
    *stack = NULL;
}