3.1 堆栈

3.1.1 堆栈的定义及基本运算

堆栈简称为栈，是限定只能在表尾的一端进行插入和删除操作的线性表。在表中，允许插入和删除的一端称为“栈顶”，另一端称为“栈底”。通常将元素插入栈顶的操作称为“入栈”（进栈或压栈），称删除栈顶元素的操作为“出栈”，如图3-1所示。因为出栈时后入栈的元素先出，故堆栈又被称为是一种“后进先出”表，或称为LIFO（Last In First Out）表。

堆栈的基本运算如下。

（1）StackInit()初始化堆栈。

（2）StackEmpty(s)判定栈s是否为空。

（3）StackLength(s)求堆栈s的长度。

（4）GetTop(s)获取栈顶元素的值。

（5）Push(s,e)将元素e进栈。

（6）Pop(s)出栈（删除栈顶元素）。

3.1.2 堆栈的顺序存储结构

与线性表类似，栈也有两种存储表示，其顺序存储结构简称为顺序栈。与顺序表类似，对顺序栈也需要事先为它分配一个可以容纳最多元素的存储空间，即一维数组，以及表示栈顶元素在栈中位置（栈顶位置）的值。

顺序栈的类型描述如下。

#define MaxSize 堆栈可能达到的最大长度
typedef struct
{ ElementType elem[MaxSize];
  int top;  /*栈顶位置*/
} SeqStack;

顺序栈的基本运算的算法如下。

（1）初始化堆栈StackInit()：

SeqStack StackInit(SeqStack *s)
{
    s->top=-1;
    return(s);
}/* StackInit */

（2）判定栈s是否为空StackEmpty(s)：

int StackEmpty(SeqStack s)
{
    return(s.top==-1);
}/* StackEmpty */

（3）求堆栈s的长度StackLength(s)：

int StackLength(SeqStack s)
{
     return(s.top+1);
}/* StackLength*/

（4）获取栈顶元素的值GetTop(s)：

ElementType GetTop(SeqStack s)
{  if (StackEmpty(S))  /*栈空*/
        return(nil);/* nil表示与ElementType类型对应的空值*/
   return(s.elem[s.top]);
}/* GetTop */

（5）将元素e进栈Push(s,e)：

void Push(SeqStack *s,ElementType e)
{ if (S->top==MaxSize-1)  /*栈满*/
        printf(“Full”);
    else
    {  s->top++;
       s->elem[s->top]=e ;
     }
} /* Push */

（6）出栈Pop(s)：

ElementType Pop(SeqStack *s)
{ if (S->top==-1)   /*栈空*/
        return(nil);/* 返回空值*/
    else
        {  e=s->elem[s->top];
           s->top--;
return (e);
    }
}/* Pop */

【例3-1】假设有两个栈共享一个一维数组空间[0,MaxSize-1]，其中一个栈用数组的第0单元（元素）作为栈底，另一栈用数组的第MaxSize-1号单元（元素）作为栈底（两个堆栈从两端向中间延伸），如图3-2所示是两栈共享空间的示意图。其对应的类型描述如下。

#define MaxSize 堆栈可能达到的最大长度
typedef struct
{ ElementType elem[MaxSize];
  int top1,top2;  /*栈顶位置*/
} ShareStack;

试写出共享栈的进栈、出栈算法。

若有声明：

ShareStack *s;

则栈1的栈顶表示为s->top1，栈2的栈顶表示为s->top2，栈1的进栈操作使得栈顶1右（后）移，即s->top1++，栈2的进栈操作使得栈顶2左（前）移，即s->top1--，栈满时两个栈顶相邻，即s->top1+1＝＝s->top2。

void Push(ShareStack *s,ElementType e,int i)
/*将元素e压入栈i(i=1,2)*/
{  if (s->top1+1＝＝s->top2)  /*栈满*/
         printf(“Full”);
   else
      {  if (i==1)
         {  s->top1++;
            s->elem[s->top1]=e ;
         }
         else
         {  s->top2--;
            s->elem[s->top2]=e ;
         }
         }
} /* Push */

栈1的出栈使得栈顶1左（前）移，即s->top1--，栈2的出栈使得栈顶2右（后）移，即s->top2++，栈1空时满足s->top1==-1，栈2空时满足s->top2==MaxSize。

ElementType Pop(ShareStack *s,int i)
/*栈i(i=1,2)出栈*/
{  if (i==1)
        if (s->top1==-1)  /*栈1空*/
            return(nil);
        else
        {  e=s->elem[s->top1];
           s->top1--;
           return(e);
        }
   if (i==2)
        if (s->top2==MaxSize) /*栈2空*/
             return(nil);
        else
        {  e=s->elem[s->top2];
           s->top2++;
           return(e);
        }
} /*Pop*/

3.1.3 堆栈的链式存储结构

与线性表的链式存储结构相对应，栈也有链式存储，简称为链栈。出于对算法简单性的考虑，正如在链表的头部增加头结点一样，同样在栈顶也增加一头结点，如图3-3所示。链栈的类型描述如下。

typedef struct snode
{ ElementType data;
  struct snode *next;
}StackNode;
typedef StackNode *LinkStack;
/ * LinkStack为指向StackNode的指针类型* /

下面给出的是链栈基本运算的算法实现。

（1）初始化堆栈，StackInit()。

LinkStack StackInit()
{
    s=(LinkStack)malloc(sizeof(StackNode));
    s->next=NULL;
    return (s);
}/* StackInit */

（2）判定栈s是否为空，StackEmpty(s)。

int StackEmpty(LinkStack s)
{
      return(!(s->next));
}/* StackEmpty */

（3）求堆栈s的长度，StackLength(s)。

int StackLength(LinkStack s)
{  p=s->next;
   length=0;
   while (p)
         { length++;
           p=p->next;
         }
   return(length);
}/* StackLength */

（4）获取栈顶元素的值，GetTop(s)。

ElementType GetTop(LinkStack s)
{
    if (StackEmpty(s))  /*栈空*/
            return(nil);/* nil表示与ElementType对应的空值*/
    return(s->next->data);
}/* GetTop*/

（5）进栈，Push(s,e)。

void Push(LinkStack s,ElementType e)
{  p=( StackNode *)malloc(sizeof(StackNode));
   /*生成新结点，并由p指向它*/
   p->data=e;
   p->next=s->next;
   s->next=p;
} /* Push*/

（6）出栈，Pop(s)。

ElementType Pop(LinkStack s)
{  if (StackEmpty(s))  /*栈空*/
return(nil);  /* 返回空值*/
   else
   { p=s->next;
       s->next=p->next;
       e=p->data;
       free(p)
       return(e);
   }
} /* Pop*/

【例3-2】阅读下面的算法，给出算法的返回值与参数n（自然数）的关系。

int Fact(int n)
{  x=n;
   result=1;
   s=( StackNode *)malloc(sizeof(StackNode));  /*生成链栈的头结点*/
   s->next=NULL;
   while(x)
   {  p=( StackNode *)malloc(sizeof(StackNode));
      p->data=x;
      p->next=s->next;
      s->next=p;
       x--;
   }
   while(!s->next)
   {  p=s->next;
      s->next=p->next;
      x=p->data;
      free(p);
      result=result*x;
   }
   return(result);
} /* Fact*/

在以上算法中，第一个while循环首先使x的值（初值为n）进栈s，再使x的值减1，继续进栈直到x的值减为0（0不进栈），如图3-4所示是x的值全部进栈后的示意图。第二个while实现s的循环出栈操作，并使原栈顶元素的值赋给x，直到栈空，result中存放的是从第一个x到最后一个x的累乘结果。因此最后返回的result应该是x的阶乘，也就是说算法的返回值是参数n的阶乘。事实上以上算法完全可以调用链栈的基本运算实现，下面就是调用链栈的基本运算后的算法实现。

int Fact(int n)
{  x=n;
   result=1;
   s=StackInit();
   while(x)
   { Push(s,x);
     x--;
   }
   while(!s)
   { x=Pop(s);
     result=result*x;
   }
   return(result);
} /* Fact*/

请读者思考，对于上述改写后的算法，是否适合于顺序栈。