由于栈是一个有穷线性表，所以任何实现表的方法都能实现栈（list，vector...)
基本操作

InitStack(*S)
StackEmpty(S)
Push(*S,x)
Pop(*S,*x)
GetTop(S,*x)
ClearStack(*S)

---

顺序栈

采用顺序存储的栈

#define MaxSize 50
typedef strcut{
    Elemtype data[MaxSize];
    int top;   //栈顶游标，空栈是为-1，满栈是MaxSize-1
}SqStack;

初始化

void InitStack(SqStack* S)
{
    S->top=-1;
}

判空

bool StackEmpty(SqStack S)
{
    if(S->top==-1)
        return true;
    return false;
}

进栈

bool Push(SqStack* S, ElemType x)
{
   if(S->top==MaxSize-1)
       return false;
   S->data[++S->top]=x;  //先加1，再入栈
   return true;
}

出栈

bool Pop(SqStack* S, ElemType* x)
{
    if(S->top==-1)
        return false;
    *x=S->data[S->top--];  //先出栈，再减1
    return true;
}

读栈顶元素

bool GetTop(SqStack S, ElemType* x)
{
    if(S->top==-1)
        return false;
    *x=S->data[S->top];
    return true;
}

共享栈
让两个顺序栈共享一个一维数据空间，栈底分别设置在共享控件的两端，两个栈顶向共享空间的中间延伸。
链栈
所有操作都在单链表的表头进行，无头节点，S指向栈顶元素

typedef struct LinkNode
{
    ElemType data;
    struct LinkNode* next;
} *ListStack;
ListStack S;

初始化

LinkStack InitSatck()
{
    LinkStack S;
    S=(LinkStack)malloc(size of(struct LinkNode));
    S->next=NULL;
    return S;
}

入栈

void Push(ElemType x, LinkStack S)
{
    struct LinkNode* tempCell;
    tempCell=malloc(size of(struct LinkNode));
    tempCell->data=x;
    tempCell->next=S->next;
    S->next=tempCell;
}

出栈

bool Pop(LinkStack S, ElemType* x)
{
    if(S->next==NULL)
        return false;
    struct LinkNode* firstCell;
    firstCell=S->next;
    *ElemType=firstCell->data;
    S->next=firstCell->next;
    free(firstCell);
    return true;
}

---

堆栈的应用

函数调用及递归实现（用堆栈来保存一系列函数调用过程中的调用前的状态，调用回来后准备要执行的语句的地址），深度优先搜索，回溯算法，平衡符号[()]ok [(])no，表达式求值
表达式求值*
中缀表达式：运算符位于两个运算数之间a+b*c-d/e
后缀表达式：运算符位于两个运算数之后abc*+de/-
方便计算机计算，遇到运算数入栈，遇到运算符把栈顶上的两个元素出栈进行计算后把结果入栈。
中缀表达式转后缀表达式
用一个栈来存放运算符
读取中缀表达式，遇到运算数则输出，遇到运算符，与运算符栈的栈顶元素比较，若优先级大于栈顶元素则入栈；若优先级小于栈顶元素，则栈顶元素出栈输出，再继续与当前栈顶元素比较。
注：左括号入栈前优先级最高，入栈后优先级最低，遇到右括号时，直接出栈至左括号。各对象处理完毕后则把堆栈中存留的运算符一并输出。

中缀转后缀.PNG
表达式树.PNG
递归
在递归调用的过程中，系统为每一层的返回点，局部变量，传入实参等开辟了递归工作栈来进行数据存储，递归次数过多容易造成栈溢出。其效率不高的原因是包含许多重复计算。将递归转换为非递归算法的时候，通常需要借助栈。