來源 | OSCHINA 社區
作者 | 華為云開發者聯盟-高彬滔
摘要：本文為大家詳解數據結構中棧的定義和操作。
本文分享自華為云社區《數據結構：詳細講解棧的定義、棧的操作》，作者：高彬滔 。
1.棧的定義
棧（stack）：是只允許在一端進行插入或者刪除操作的線性表（即后進先出，大概可以理解為吃飽了吐出來）
- 空棧：不含元素的空標配
- 棧頂：表尾端
- 棧底：表頭端
- 進棧順序：a1->a2->a3->a4->a5
- 出棧順序：a5->a4-a3->a2->a1
- InitList (&L): 初始化表。構造一個空的線性表 L，分配內存空間
- DestoryList (&L): 銷毀操作。銷毀線性表，并且釋放線性表 L 所占用的空間
- ListInsert (&L,i,e): 插入操作，在表 L 中的第 i 個位置上插入指定元素 e
- ListDelete (&L,i,e): 刪除操作，刪除表 L 中的第 i 個位置的元素，并且用 e 返回刪除元素的值
- LocateElem (L,e): 按值查找操作，在表 L 中查找具有給定關鍵字值的元素
- GetElem (L,i): 按位查找操作，獲取表 L 中第 i 個位置的元素的值
- InitStack (&S): 初始化棧，構造一個空棧 S，分配內存空間
- DestoryStack (&S): 銷毀棧，銷毀并釋放棧 S 所占用的內存空間
- Push (&S,x): 進棧，若棧 S 未滿，則將 x 加入使之成為新的棧頂
- Pop (&S,&x): 出棧，若棧 S 非空，則彈出棧頂元素，并用 x 返回
- GetTop (S,&x): 讀棧頂元素，若棧 S 非空，則用 x 返回棧頂元素
其他常見操作：StackEmpty (S): 判斷一個棧 S 是否為空，若 S 為空，則返回 true，否則返回 false
3. 順序棧
3.1 順序棧的定義# defineMaxSize 10 //定義棧中元素的最大個數
typedefstruct{
ElemType data[MaxSize]; //靜態數組存放棧中的元素
inttop; //棧頂指針
}SqStack; //結構體重命名
聲明一個順序棧后就會在內存中分配一整片連續的空間，其中內存大小為：MaxSize*sizeof (ELemType)
voidtestStack{
SqStack S; //聲明一個順序棧
} 3.2 棧的初始化操作
由于棧頂指針 top 需要指向此時棧頂元素，所以讓 top 指向 0 是不合理的，可以初始化讓 top 指向 - 1; 判斷一個棧是否為空，即判斷 S.top 是否等于 - 1
初始化棧：
voidInittack(SqStack){
SqStack S; //聲明一個順序棧
S.top=- 1;
}
判斷棧空：
bool StackEmpty(SqStack S){
if(S.top==- 1) //棧空
returntrue;
else
returnfalse; //非空
} 3.3 進棧操作
分析：
- 判斷棧是否為空
- 棧頂指針 + 1
- 新元素入棧
if(S.top==NaxSize- 1)
returnfalse;
S.top+= 1;
S. data[S.top]=x;
returntrue;
} 3.4 出棧操作bool Push(SqStack &S,ElemType &x){
if(S.top==- 1)
returnfalse;
x=S. data[S.top--];
returntrue;
} 3.5 讀棧頂元素操作bool GetTop(SqStack &S,ElemType &x){
if(S.top==- 1)
returnfalse;
x=S. data[S.top];
returntrue;
} 4. 共享棧
兩個棧共享同一片空間
# defineMaxSize 10 //定義棧中元素的最大個數
typedefstruct{
ElemType data[MaxSize]; //靜態數組存放棧中的元素
inttop0; //0號棧棧頂指針
inttop1; //1號棧棧頂指針
}SqStack; //結構體重命名
初始化棧：
voidInitStack(ShStack &S){
S.top0= -1;
S.top1=MaxSize;
} 5. 鏈棧的定義
- 進棧 / 出棧都只能在棧頂一段進行
- 鏈頭作為棧頂
ElemType data; //數據域
structLinknode* next; //指針域
}*LiStack //棧類型定義
END
谷歌開發全新搜索引擎Magi，由人工智能技術驅動
