資料結構之堆棧（一）

堆棧的基本概念

堆棧是一種特殊的線性表，堆棧的資料元素以及資料元素間的邏輯關系和線性表完全相同，其差别是：線性表允許在任意位置插入和删除資料元素操作，而堆棧隻允許在固定一端進行插入和删除資料元素操作

根據堆棧的定義，每次進棧的資料元素都放在原目前棧頂元素之前而成為新的棧頂元素，每次退棧的資料元素都是原目前棧頂元素，這樣，最後進入堆棧的資料元素總是最先退出堆棧，是以，堆棧也稱作後進先出的線性表，或簡稱後進先出表。

例子

設有資料元素序列A,B,C，是否可以利用一個堆棧，得到資料元素序列B, A, C。

分析：按照如下方法操作：A入棧，B入棧，B出棧，A出棧，C入棧，C出棧，則輸出資料元素序列為B, A, C。是以，利用一個堆棧，可以把資料元素序列A, B, C變換為資料元素序列B, A,C。其操作過程的堆棧内容示意圖下圖所示。

輸出序列為B, A, C的操作過程

在軟體設計中，需要利用堆棧進行資料元素序列轉換的例子很多。例如，在編譯軟體系統中，就需要頻繁地把中綴表達式形式的算術表達式，轉換成字尾表達式形式的算術表達式。又如，任何支援遞歸算法的程式設計語言，都是借助堆棧來實作遞歸算法需要的後調用的過程先執行的要求的。

堆棧操作集合

初始化StackInitiate(S)：初始化堆棧S。

非空否StackNotEmpty(S)：堆棧S非空否。若堆棧非空，則函數傳回1；否則函數傳回0。

入棧StackPush(S, x)：在堆棧S的目前棧頂插入資料元素x。

出棧StackPop(S, d)：把堆棧S的目前棧頂資料元素删除并由參數d帶回。若出棧成功，則傳回1；失敗，則傳回0。

取棧頂資料元素StackTop(S, d)：取堆棧S的目前棧頂資料元素并由參數d帶回。若取到資料元素，則傳回1；否則傳回0。

順序堆棧的存儲結構

順序存儲結構的堆棧稱作順序堆棧。

順序堆棧和順序表的資料成員是相同的，不同之處是，順序堆棧的入棧和出棧操作隻能對目前棧頂元素進行。

順序堆棧的存儲結構示意圖如圖3-3所示。其中，a0, a1, a2, a3, a4表示順序堆棧要存儲的資料元素序列，stack表示順序堆棧存放資料元素的數組，MaxStackSize表示順序堆棧數組stack的最大存儲單元個數，top表示順序堆棧數組stack的目前棧頂位置。

順序堆棧的存儲結構示意圖

定義結構體SeqStack如下：

#define MaxSize 50
typedef int ElemType;
typedef struct{
    ElemType data[MaxSize];        //連續記憶體空間存放棧中元素
    int top;            //存放棧頂元素在data數組中的下标
}SqStack;      

順序堆棧的操作實作

初始化StaticInitiate(*S)
void StaticInitiate(*S)
{
    S->top=0;    //初始化棧頂下标值
}      

非空否StackNotEmpty(S)

int StackPush(SeqStack *S,DataType x)//把資料元素x存入順序堆棧S中，入棧成功傳回1，否則傳回0
{
    if(S->top>=MaxStackSize)
    {
        printf("堆棧已滿，無法插入！\n")
        return 0;
    }
    else
    {
        S->Stack[S->top]=x;
        S->top++;
        return 1;
    }
}      

入棧StackPush(SeqStack *S,DataType x)

int StackPush(SeqStack *S,DataType x)//把資料元素x存入順序堆棧S中，入棧成功傳回1，否則傳回0
{
    if(S->top>=MaxStackSize)
    {
        printf("堆棧已滿，無法插入！\n")
        return 0;
    }
    else
    {
        S->Stack[S->top]=x;
        S->top++;
        return 1;
    }
}      

出棧StackPop(SeqStack *S,DataType)

int StackPop(SeqStack *S,DataType) //取出順序堆棧S的棧頂元素值由參數d帶回，出棧成功則傳回1，否則傳回0
{
    if(S->top<=0)
    {
        printf("堆棧已空無資料元素出棧！\n");
        return 0;
    }
    else
    {
        S->top--;        //得注意top--，--top的差别
        *d=S->stack[S->top];
        return 1;
    }
}      

取棧頂資料元素StackTop(SeqStack S,DataType *d)

int StackTop(SeqStack S,DataType *d) //取棧頂資料元素值由參數d帶回，成功傳回1，不成功傳回0
 {
      if(S.top<=0)
      {
         printf("堆棧已空！\n");
         return 0;
      }
      else
      {
          *d=S.stack[S.top-1];
          return 1;
      }
  }      

撤銷動态申請空間Destory(SLNode *head)

void Destory(SLNode *head)
{
    LSNode *p,*p1;
    p=head;
    while(p!=NULL)
    {
        p1=p;
        p=p->next;
        free(p);
    }
}