（二）线性结构——（3）堆栈的理解

  后缀表达式   (从左往右逐个扫描，逐个处理运算符号和运算数）   6 2/3-4 2*+=8;

   需要有一种存储方式，能顺序存储运算数，并且在需要的时候倒序输出！这就是堆栈！

    （一）堆栈的抽象数据类型描述

     堆栈（Stack):具有一定操作约束的线性表。旨在一端（top,栈顶）做插入，删除。

     插入数据：入栈Push                 删除数据Pop                   后入先出：Last In First Out

    push和pop可以穿插交替进行

Push(S,A)
Push(S,B)
Push(S,C)
Pop(s)
Pop(s)
Pop(s)//输出CBA

 栈的顺序结构通常是由一个一维数组和一个记录栈顶元素位置的变量组成的

#define Maxsize//存储数据元素的最大个数
typedef struct SNode*Stack;
struct SNode{
    ElementType Date[Maxsize];
    int top;
};

入栈
void Push(Stack PtrS,ElementType item)
{
   if(Ptrl->top==Maxsize-1)
  {
    printf("堆栈满“）；
    return;
 }
  else{
  Ptrs->Date[++PtrS->Top)]=item;
   return;
 }

出栈
ElementType Pop(stack ptrs)
{
  if(Ptrs->Top==-1)
   {
    printf("堆栈空”）;
    return ERROR;
}//ERROR是ElementType的特殊值，标志错误
 else
{
 return(Ptrs->Date[(Ptrs->Top)--]);
}

用一个数组实现俩个堆栈，要求最大地利用数组空间，使得数组只要有空间入栈就可以成功 

（使得俩个栈分别从数组的俩头开始向中间生长；当俩个栈的栈顶相遇时，表示俩个栈都满了）

#define Maxsize 10
struct DStack{
  ElementType Date[Maxsize];
 int Top1;
 int Top2;
 }s;

堆栈为空的条件
S.Top1=-1;
S.Top2=Maxsize;

void push(struct DStack*PtrS,ElemntType item,int Tag)//tag作为俩个堆栈的标志，取值为1和2
{
   if(PtrS->Top2-PtrS->Top1==1)
    {
         printf("堆栈满“）；  return;
    }
   
   if(Tag==1)
    PtrS->Date[++(PtrS->Top1)]=item;
   else
      Ptrs->Date[--(PtrS->Top2)]=item;

(二）堆栈的链式存储实现

栈的链式存储结构实际上就是一个单链表，叫做链栈。插入和删除操作只能在 链栈的栈顶实现。

用链表来表示堆栈时候，链表一定在堆栈头上。

typedef struct SNode*Stack;
struct SNode{
        ElementType Date;
        struct SNode*Next;
            }

Stack CreateStack()
{//构建一个堆栈的头结点，返回指针
  Stack S;
  S=（Stack)malloc(sizeof(struct SNode));
  S->Nest=NULL;
  return S;
}

int IsEmpty(Stack S)
{  //判断堆栈S是否为空，若为空返回整数1，否则返回0
   return(S->Next==NULL);
}

void Push(ElementType item,Stack S)
{   //将元素item放在堆栈S中

struct SNode *TmpCell;
TmpCell=(struct SNode*)malloc(struct SNode);
TmpCell->Element=item;
TmpCell->Next=S->Next;
S->Next=TmpCell;

}

ElementType Pop(Stack S)
{
   //删除并且返回堆栈S的栈顶元素
 struct SNode *FirstCell;
 ElementType TopElem;

if(isempty(s))
 {
  printf("堆栈空”）;
  return NULL;
 }

else{
 FirstCell=s->Next;
 S->Nest=FirstCell->Next;
 TopElem=FirstCell->Element;
 return TopElem;
}
}

例：中缀表达式的运算求值——转化为后缀表达式

2+9/3-5-------2 9 3 / +5 -

1 )   运算数的相对顺序不变

2）运算符号的顺序改变（存储等待中的符号，并将等待中的符号和后续的符号进行对比）

遇到左括号，压入堆栈

遇到右括号，就把栈顶的运算符弹出并且输出，直到遇到左括号

遇到运算符：比较运算符和栈顶运算符的优先级（大于栈顶，压栈。小于栈顶，将栈顶运算符号弹出来输出，再比较新的栈顶运算符，直到运算符大于栈顶运算符的优先级为止，然后将该运算符压栈）

输出：2 9 3               输出：2 9 3 / +

存储：+ /                    存储：

有括号怎么办：a*(b+c)/d=abc+*d/

堆栈的实现：

堆栈的其他运用：

函数调用及其递归的实现

深度优先搜索

回溯算法