栈的前置知识

1.什么是栈？

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

总的来说，栈就是一个线性表，只不过只能从栈顶入栈，也只能从栈顶出栈，因此栈有一个非常重要的特性——后进先出(First In Last Out)。

2.生活中哪些地方有栈的影子？

让我们来看看下面这段代码：

void f()
{printf("666\n");
}
int main()
{printf("777\n");f();return 0;
}

程序的入口是main函数，然后执行了printf函数，printf函数结束，然后执行f()函数，在f()函数中执行了第二个printf函数，然后第二个printf函数结束，随后f()函数结束，最后才是main函数结束。

我们可以发现，作为程序入口的main反而是最后结束的，而越后执行的函数越先结束，这就是栈的后进先出特性。所以函数就是利用栈来实现调用的。

然后printf f() main再依次出栈，程序结束。

顺序表实现栈

1.为什么通常采用顺序表实现栈？

我们可以发现，对栈进行插入和删除操作时，永远是在栈顶进行操作，我们把栈顺时针旋转90°，
就变成了只在表尾插入删除的线性表，因为不会大量挪动元素，所以我们选择顺序表实现。

2.栈的实现

头文件 Stack.h

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef int STDataType;
typedef struct Stack
{STDataType* a;//存放数据的空间首地址int capacity;//当前栈最大容量int top;//模拟栈顶指针
}ST;
//初始化栈
void StackInit(ST* ps);
//销毁栈 
void StackDestroy(ST* ps);
//插入
void StackPush(ST* ps, STDataType x);
//弹出 
void StackPop(ST* ps);
//获取栈顶元素
STDataType GetTop(ST* ps);
//获取栈当前元素个数
int StackSize(ST* ps);
//判断栈是否为空
bool StackEmpty(ST* ps);

源文件 Stack.c

//初始化栈
void StackInit(ST* ps)
{assert(ps);ps->a = NULL;ps->capacity = ps->top = 0; 
}
//销毁栈 
void StackDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;
}
//插入
void StackPush(ST* ps, STDataType x)
{assert(ps);//判满 if(ps->capacity == ps->top){int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);if(tmp == NULL){printf("malloc fail\n");exit(-1);}ps->a = tmp;ps->capacity = newcapacity;}//插入元素 ps->a[ps->top++] = x;
}
//弹出 
void StackPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));ps->top--;
}
//获取栈顶元素
STDataType GetTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->a[ps->top - 1];
}
//获取栈当前元素个数
int StackSize(ST* ps)
{assert(ps);return ps->top;
}
//判断栈是否为空
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

测试一下写出来的栈是否可用

源文件 test.c

int main()
{Stack st;StackInit(&st);StackPush(&st, 1);	StackPush(&st, 2);StackPush(&st, 3);StackPush(&st, 4);StackPush(&st, 5);while(!StackEmpty(&st)){printf("%d ", GetTop(&st));StackPop(&st);}return 0;
}

结果：