### 定義
只能在表的一端(棧頂)進行插入和刪除運算的線性表
### 邏輯結構
一對一關系
### 存儲結構
用順序棧或鏈棧存儲均可，但以順序棧更常見
### 運算規則
只能從棧頂運算，且訪問結點時依照后進先出(LIFO)或后進后出(FILO)的原則
### 實現方法
關鍵是編寫入棧和出棧函數，具體實現依順序棧或鏈棧的不同而不同
### 基本操作
- 入棧
- 出棧
- 讀棧頂元素值
- 建棧
- 判斷棧滿
- 棧空
### 棧與一般線性表的區別
棧是一種特殊的線性表，它只能在表的一端(棧頂)進行插入或刪除運算
| ** | 一般線性 表 | 棧 |
|-----|-----|-----|
| 邏輯結構 | 一對一 | 一對一 |
| 存儲結構 | 順序表、鏈表 | 順序棧、鏈棧 |
| 運算規則 | 隨機、順序存儲 | 后進先出 |
### 它們之間在于運算規則不同
> 我們在平常的程序設計中，如果需要按照保存數據時相反的順序來使用數據，可以利用棧來實現。
### 順序棧的表示
~~~
#define MAXSIZE 100
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
~~~
stacksize 指示棧的最大容量；base為棧底指針，它始終指向棧底位置，若base的值為NULL，則表明棧結構不存在；top為棧頂指針，其初值指向棧底，即top=base可作為棧空的標記。每當插入新的棧頂元素時，指針top增加1；刪除棧頂元素時，指針top減1.因此，非空棧中的棧頂指針始終在棧頂元素的下一個位置上。
base == top 是棧空的重要標志
### 棧滿時的處理方法
1.
報錯，返回操作系統。
1.
分更大的空間，作為棧的存儲空間，將原棧的內容移入新棧。
### 初始化
（1）分配空間并檢查空間是否分配失敗，若失敗則返回錯誤
（2）設置棧底和棧頂指針
S.top = S.base;
（3）設置棧大小
【算法描述】
~~~
Status InitStack(SqStack &S)
{
S.base=new SElemType[MAXSIZE];
if(!S.base) return OVERFLOW;
S.top=S.base;
S.stackSize=MAXSIZE;
return OK;
}
~~~
### 判斷順序棧是否為空
~~~
bool StackEmpty(SqStack S)
{
if(S.top == S.base) return true;
else
return false;
}
~~~
### 求順序棧的長度
~~~
int StackLength(SqStack S)
{
return S.top-S.base;
}
~~~
### 清空順序棧
~~~
Status ClearStack(SqStack S)
{
if(S.base)S.top = S.base;
return OK;
}
~~~
### 銷毀順序棧
~~~
Status DestroyStack(SqStack &S)
{
if(S.base)
{
delete S.base;
S.stacksize = 0;
S.base = S.top =NULL;
}
return OK;
}
~~~
### 順序棧進棧
（1）判斷是否棧滿，若滿則出錯
（2）元素e壓入棧頂
（3）棧頂指針加1
~~~
Status Push(SqStack &S,SElemType e)
{
if(S.top - S.base == S.stacksize)//棧滿
return ERROR;
*S.top=e;
S.top++;
return OK;
}
~~~
### 順序棧出棧
(1)判斷是否棧空。若空則出錯
（2）獲取棧頂元素e
（3）棧頂指針減1
Status Pop(SqStack &S,SElemType &e)
{
if(S.top == S.base)//棧空
return ERROR；
–S.top;
e= *S.top;
return OK;
}
### 取順序棧棧頂元素
判斷是否為空棧，若為空則返回錯誤
否則通過棧頂指針獲取棧頂元素
~~~
Status GetTop(SqStack S,SElemType &e)
{
if(S.top == S.base)
return ERROR;//棧空
e = *(S.top-1);
return OK;
}
~~~
