什么是栈？
栈是一种基本数据结构，因其拥有后进先出的特点（Last in First out），也就是LIFO，栈的一种常见用途就是用来判断一串字符中的括号是否有效。
括号的类型有{}、[]、()，“{[]}”像这样的就是有效的，而像"{[])"这样的就是无效的括号，这通常用于编译器的语法检查。
在内存的中使用也是一种栈，因函数调用会压栈，每调用一次压栈一次，当递归层次太深时，我们经常看到编译器报错：“Stack Overflow”,也就是栈溢出。
栈的主要操作有Push和Pop，入栈和出栈。
栈有俩种实现方法，一种是通过数组，另一种是通过链表。
使用数组实现的查询效率高，易于实现。缺点是想要插入元素困难，而且受限于数组大小。
使用链表的建立易于插入且不用受限于大小，因为每次压栈都会向堆区申请内存。缺点是查询困难，空间成本高。（因为使用了malloc）
顺序栈
先定义数据结构
#define size 100
typedef struct Stack
{
int arr[size];
int top;//指针
}stack;
函数声明
void InitStack(stack* stack);//初始化
int Push(stack* stack, int* e);//入栈
int Pop(stack* stack, int* e);//出栈
int GetTop(stack* stack, int* e);//获取栈顶元素
栈初始化函数
void InitStack(stack* stack)
{
stack->top = -1;
}
Push
int Push(stack* stack,int e)//压栈
{
if (stack->top == size - 1)//判断是否满栈
{
printf("栈满！\n");
return 0 ;//失败返回零
}
else
{
stack->top++;//每次入栈，指针向后移动
stack->arr[stack->top] = e;
return 1;//成功则返回1
}
}
Pop
int Pop(stack* stack, int* e)//出栈
{
if (stack->top == -1)//判断是否为空
{
printf("栈空！\n");
return 0;//出栈失败返回零
}
else
{
*e = stack->arr[stack->top];
stack->top--;//每次出栈指针向前移动
return 1;//出栈成功返回1
}
}
GetTop
int GetTop(stack* stack, int* e)//获取栈顶元素
{
if (stack->top == -1)
{
printf("栈空！\n");//判断是否为空
return;
}
else
{
*e = stack->arr[stack->top];//只获取栈顶元素，top不变
return 1;
}
}
链栈
链栈和顺序栈区别在于一个使用链表实现，另一个使用数组实现。
链栈其主要操作也是Push和Pop
先定义类型
typedef struct Stack
{
int data;
struct Stack* next;
}LinkStack;
函数声明
LinkStack* CreatStack();
void LPush(LinkStack* stack, int e);
int LPop(LinkStack* stack, int* e);
int LGetnext(LinkStack* stack, int e);
void LJudgeNull(LinkStack* stack);
首先建立栈
LinkStack* CreatStack()
{
LinkStack* stack = (LinkStack*)malloc(sizeof(LinkStack));
stack->next = NULL;//初始化
return stack;
}
入栈操作，这里需要注意的是，栈是从高地址到低地址，而不是低地址到高地址。有兴趣可以看下。通过观察，我们可以从编译器中看到，压栈是先使用高地址，再使用低地址。
函数栈帧 ：局部变量的创建与销毁？ 函数的调用？ 传参的形式？
void LPush(LinkStack* stack, int e)//入栈
{
LinkStack* p;
p = (LinkStack*)malloc(sizeof(LinkStack));//新建节点p
p->data = e;
p->next = stack->next;//将p与下一级链接
stack->next = p;//指向栈顶
}
出栈
int LPop(LinkStack* stack, int* e)
{
if (stack->next == NULL)
{
printf("栈空！\n");
return 0;
}
else//出栈
{
*e = stack->next->data;
LinkStack* p = stack->next;
stack->next = stack->next->next;//指向栈顶
free(p);
}
return 1;
}
判空
void LJudgeNull(LinkStack* stack)//判空
{
if (stack->next == NULL)
{
printf("栈空！\n");
return;
}
}
取出栈顶值
void LGetTop(LinkStack* stack,int*e )//取栈顶值
{
if (stack->next == NULL)
{
printf("栈空！\n");
return;
}
else
{
*e = stack->next->data;
}
}