模拟一个顺序栈

1、简介

栈作为一种常用的抽象数据类型，在平常的运用是十分常见的。它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
这篇文章带领大家一起模拟一个顺序栈的实现。并且封装一些常用的栈操作。相信用过STL中stack容器的同学经常会调用一些stack容器中打包的函数（如size（）、empty（）等），透过这篇博客亦可以看出一点stack常用API的源码的影子。当然，想深入剖析STL的源码，推荐大家看《STL源码剖析》这本书！

2、栈的结构体

由于栈是一种抽象的数据类型，我们首先来定义下其结构体。

#define MAXSIZE 1024

struct SStack
{   
    //将数组头作为栈尾，因为如果作为栈顶的话来回出入元素时间开销比较大
    void *data[MAXSIZE]; //数组
    int size;
};

typedef void * sstack;

结构体封装了数据和栈的大小

栈的结构体中之所以封装的是一个 void * 数组，是因为我们不知道要用该栈存储的是何种类型的数据，所以我们使用了万能指针数组，它可以指向任意类型的内存。这样做的好处是让我们的代码具有通用性。（cpp泛型编程yyds！）

3、初始化栈

好了，我们定义好了栈的结构体后，要想模拟一个栈，我们当然要有栈了。所以接下来进行栈的初始化操作。

//初始化栈
sstack init_stack(){
    struct SStack * myStack = malloc(sizeof(struct SStack));
    if (myStack==NULL) //申请内存后判空，这是避免野指针产生的一种方法哦
    {
        return NULL;
    }
    memset(myStack->data,0,sizeof(void *)*MAXSIZE); //给数组赋初值0
    myStack->size=0; //初试化栈的大小
    return myStack;
}

好的，我们现在已经初始化好了一个栈了。其指针数组中暂时没有数据，大小为0。

4、入栈

初始化栈后，我们就可以往这个栈内塞数据了！塞数据前要看看这个栈是否已经初始化好了哦。接下来我们实现入栈操作。

//入栈
void push_stack(sstack stack,void *data ){
    if (stack==NULL) //判断栈是否初始化成功
    {
        return;
    }
    if (data==NULL)
    {
        return;
    }
    struct SStack *myStack=stack; //把用户传过来的指针转换成栈结构体指针

    //判断栈满
    if (myStack->size==MAXSIZE)
    {
        return;
    }
    
    //入栈就是尾插数组
    myStack->data[myStack->size]=data;
    myStack->size++; //栈大小+1
}

该过程很容易理解，就是不要忘了指针的转换。

5、出栈

出栈的逻辑很简单，我们传过来一个栈。判断栈是否已经初始化好了并且不为空。然后让栈顶元素出栈，栈长度-1就可以了。

//出栈
void pop_stack(sstack stack){
    if (stack==NULL)
    {
        return;
    }
    struct SStack *myStack=stack;

    //判断栈空
    if (myStack->size==0)
    {
        return;
    }
    
    //出栈其实就是尾删
    myStack->data[myStack->size-1]=NULL;
    myStack->size--;
}

6、返回栈顶元素

//返回栈顶
void * top_stack(sstack stack)
{
	if (stack == NULL)
	{
		return NULL;
	}

	struct SStack * mystack = stack;

	if (mystack->size == 0)
	{
		return NULL;
	}
	return mystack->data[mystack->size - 1];
}

7、判断栈是否为空

//判断栈是否为空
int isempty_stack(sstack stack){
    if (stack==NULL)
    {
        return -1; //返回-1代表栈空
    }
    struct SStack *myStack=stack;
    if (myStack->size==0)
    {
        return -1;
    }
    return 0;
}

8、返回栈大小

//返回栈大小
int size_stack(sstack stack){
    if (stack==NULL)
    {
        return -1;
    }
    struct SStack *myStack=stack;
    return myStack->size;
}

9、销毁栈

最好，我们要销毁栈，来释放内存空间。

//销毁栈
void destroy_stack(sstack stack){
    if (stack==NULL)
    {
        return;
    }    
    free(stack);
    stack=NULL;
}

10、测试

为了不失一般性的测试我们的代码，我们使用结构体元素来对我们的栈进行操作。首先定义一个结构体：

struct Person
{
	char name[64];
	int age;
};

结构体中包含人的姓名和年龄。
测试：

void test01(){
    //初始化栈
    sstack myStack=init_stack();
    //创建数据
	struct Person p1 = {  "aaa", 10 };
	struct Person p2 = {  "bbb", 20 };
	struct Person p3 = {  "ccc", 30 };
	struct Person p4 = {  "ddd", 40 };
	struct Person p5 = {  "eee", 50 };
    //入栈
	push_stack(myStack, &p1);
	push_stack(myStack, &p2);
	push_stack(myStack, &p3);
	push_stack(myStack, &p4);
	push_stack(myStack, &p5);
    
    printf("栈的元素个数为：%d\n", size_stack(myStack));

    while (isempty_stack(myStack)==0) //当栈不空时，元素依次出栈
    {
        struct Person *p=top_stack(myStack);
        printf("姓名：%s，年龄：%d\n",p->name,p->age);

        //元素出栈
        pop_stack(myStack);
    }
    
    //销毁栈
    destroy_stack(myStack);

}

运行结果：
alt