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*/

請讀者思考，對于上述改寫后的算法，是否適合于順序棧。