数据结构初阶之栈的介绍与栈的实现

一、概念与结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出 LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈 / 压栈 / 入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。

二、栈的实现

项目创建的时候，要创建一个头文件（.h）Stack.h ，两个源文件（.c）Stack.c ，test.c 。Stack.h 用于定义结构体和声明函数；Stack.c 用于实现函数；test.c 用于测试函数，每实现一个函数要进行相应的测试。编写代码过程中要勤测试，避免写出大量代码后再测试，如果出现问题，问题无从定位。

1、Stack.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

//定义栈的结构
typedef int DataType;
typedef struct Stack
{
    DataType* arr;
    int top;
    int capacity;
}Stack;

//初始化栈
void Init_Stack(Stack* st);

//销毁栈
void Destory_Stack(Stack* st);

//判断栈是否为空
bool Empty_Stack(Stack* st);

//入栈
void Push_Stack(Stack* st, DataType x);

//出栈
void Pop_Stack(Stack* st);

//取栈顶数据
DataType Get_Top_Stack(Stack* st);

//获取栈中的有效元素的个数
int Count_Stack(Stack* st);

2、Stack.c

#include"Stack.h"

//初始化栈
void Init_Stack(Stack* st)
{
    st->arr = NULL;
    st->top = st->capacity = 0;
}

//销毁栈
void Destory_Stack(Stack* st)
{
    if (st->arr)
        free(st->arr);
    st->arr = NULL;
    st->top = st->capacity = 0;
}

//判断栈是否为空
bool Empty_Stack(Stack* st)
{
    assert(st);
    return st->top != 0;
}
//入栈
void Push_Stack(Stack* st, DataType x)
{
    assert(st);
    if (st->top == st->capacity)
    {
        int newcapacity = st->capacity ? 2 * st->capacity : 4;
        DataType* tmp = (DataType*)realloc(st->arr, newcapacity * sizeof(DataType));
        if (!tmp)
        {
            perror("realloc fail!");
            exit(1);
        }
        st->arr = tmp;
        st->capacity = newcapacity;
    }
    st->arr[st->top++] = x;
}

//出栈
void Pop_Stack(Stack* st)
{
    assert(Empty_Stack(st));
    st->top--;
}

//取栈顶数据
DataType Get_Top_Stack(Stack* st)
{
    assert(Empty_Stack(st));
    return st->arr[st->top - 1];

}

//获取栈中的有效元素的个数
int Count_Stack(Stack* st)
{
    assert(st);
    return st->top;
}

test.c自行测试，这里不予提供。