1 棧的概念
棧(Stack)：是限制在表的一端進行插入和刪除操作的線性表。又稱為後進先出LIFO (Last In First Out)或先進後出FILO (First In Last Out)線性表。
棧頂(Top)：允許進行插入、刪除操作的一端，又稱為表尾。用棧頂指針(top)來指示棧頂元素。
棧底(Bottom)：是固定端，又稱為表頭。
空棧：當表中沒有元素時稱為空棧。
設棧S=(a1，a2，…an)，則a1稱為棧底元素，an為棧頂元素，如圖3-1所示。 棧中元素按a1，a2，…an的次序進棧，退棧的第一個元素應為棧頂元素。即棧的修改是按後進先出的原則進行的。
ADT Stack{
數據對象：D ={ ai|ai∈ElemSet, i=1,2,…,n，n≥0 }
數據關系：R ={(ai-1, ai)| ai -1， ai ∈D, i=2,3,…,n }
基本操作：初始化、進棧、出棧、取棧頂元素、求棧的長度、判斷棧是否為空等
} ADT Stack
采用靜態一維數組來存儲棧。
◆ 棧底固定不變的；棧頂則隨著進棧和退棧操作而變化，用一個整型變量top(稱為棧頂指針)來指示當前棧頂位置。
◆ 用top=0表示棧空的初始狀態，每次top指向棧頂在數組中的存儲位置。
◆ 結點進棧：首先執行top加1，使top指向新的棧頂位置，然後將數據元素保存到棧頂(top所指的當前位置)。
◆ 結點出棧：首先把top指向的棧頂元素取出，然後執行top減1，使top指向新的棧頂位置。
棧的類型定義
define MAX_STACK_SIZE 100 /* 棧向量大小 */
typedef int ElemType ;
typedef struct sqstack
{ ElemType stack_array[MAX_STACK_SIZE] ;
int bottom; //棧底，實為數組下標
int top; //棧頂，實為數組下標
}SqStack ;棧的初始化
SqStack Init_Stack(void)
{ SqStack S ;
S.bottom=S.top=0 ;
return(S) ;
}
壓棧(元素進棧)
Status push(SqStack &S , ElemType e)
/* 使數據元素e進棧成為新的棧頂 */
{ if (S.top==MAX_STACK_SIZE-1)
return ERROR; /* 棧滿，返回錯誤標志 */
S.top++ ; /* 棧頂指針加1，下標為0的位置不放元素 */
S.stack_array[S.top]=e ; /* e成為新的棧頂 */
return OK; /* 壓棧成功 */
}
思考：若調換S.top++ 和S.stack_array[S.top]=e 的位置，結果如何？
彈棧(元素出棧)
ElemType pop( SqStack &S)
/*彈出棧頂元素*/
{ if ( S.top==0 )
return ERROR ; /* 棧空，返回錯誤標志 */
e=S.stack_array[S.top] ;
S.top-- ;
return e ;
}
當棧滿時做進棧運算必定產生空間溢出，簡稱“上溢”。上溢是一種出錯狀態，應設法避免。
當棧空時做退棧運算也將產生溢出，簡稱“下溢”。下溢則可能是正常現象，因為棧在使用時，其初態或終態都是空棧，所以下溢常用來作為控制轉移的條件。
采用動態一維數組來存儲棧。所謂動態，指的是棧的大小可以根據需要增加。
◆ 用bottom表示棧底指針，棧底固定不變；棧頂則隨著進棧和退棧操作而變化。用top(稱為棧頂指針)指示當前棧頂位置。
◆ 用top=bottom作為棧空的標記，每次top指向棧頂數組中的下一個存儲位置（或指向棧頂元素）。
◆ 結點進棧：判斷棧是否已滿，如果棧滿，則重新申請更大的內存空間，然後將數據元素保存到棧頂(top所指的當前位置)，然後執行top加1，使top指向棧頂的下一個存儲位置;
◆ 結點出棧：首先執行top減1，使top指向棧頂元素的存儲位置，然後將棧頂元素取出。
基本操作的實現
1 棧的類型定義
＃define STACK_SIZE 100 /* 棧初始向量大小 */
＃define STACKINCREMENT 10 /* 存儲空間分配增量 */
typedef int ElemType ;
typedef struct sqstack
{ ElemType *bottom; /* 棧不存在時值為NULL */
ElemType *top; /* 棧頂指針 */
int stacksize ; /* 當前已分配空間，以元素為單位 */
}SqStack ;2 棧的初始化
Status Init_Stack(SqStack *S )
{
S ->bottom=(ElemType *)malloc(STACK_SIZE *sizeof(ElemType));
if (! S -> bottom) //若返回空指針，內存分配失敗
return ERROR;
S -> top=S -> bottom ; /* 棧空時棧頂和棧底指針相同 */
S -> stacksize=STACK_SIZE;
return OK ;
}
3 壓棧(元素進棧)
Status push(SqStack *S , ElemType e)
{ if (S -> top-S -> bottom>=S -> stacksize-1)
{ S -> bottom=(ElemType *) realloc (S -> bottom, (STACKINCREMENT+STACK_SIZE) *sizeof(ElemType));
/* 棧滿，追加存儲空間 */
if (! S -> bottom) return ERROR;
S -> top=S -> bottom+S -> stacksize ; //為什麼？
S -> stacksize+=STACKINCREMENT ;
}
*S-> top=e;
S -> top++ ; /* 棧頂指針加1，e成為新的棧頂 */
return OK;
}
4 彈棧(元素出棧)
ElemType pop( SqStack *S)
/*彈出棧頂元素*/
{ if ( S->top== S-> bottom )
return ERROR ; /* 棧空，返回失敗標志 */
S-> top-- ;
e=*S -> top ;
return e ;
}
ElemType pop( SqStack *S) /*彈出棧頂元素*/
{ if ( S ->top== 0 )
return ERROR ; /* 棧空，返回失敗標志 */
S -> top-- ; e =S-> bottom[S ->top];
return e ;
}
ElemType Get_top( SqStack *S) /*彈出棧頂元素*/
{ if ( S ->top== 0 )
return ERROR ; /* 棧空，返回失敗標志 */
S -> top-- ; e =S-> bottom[S ->top];
return e ;
} 
