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