資源描述：
《【數(shù)據(jù)結構電子課件】 棧和隊列.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、棧隊列遞歸第三章棧和隊列棧(Stack)定義:是限定僅在表尾進行插入或刪除操作的線性表。允許插入和刪除的一端稱為棧頂(top)，另一端稱為棧底(bottom)特點：后進先出(LIFO)a1topbottoman....進棧出棧棧的主要操作ADTStack{//對象由數(shù)據(jù)類型為StackData的元素構成intPush(stack*S,StackDatax);//進棧intPop(stack*S,StackData&x);//出棧intGetTop(stack*S,StackData&x);//取棧頂voidInitStack(stack*S);//置空棧i
2、ntStackEmpty(stack*S);//判?？辗駃ntStackFull(stack*S);//判棧滿否}棧的表示和實現(xiàn)順序棧：棧的順序存儲結構，利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，指針top指向棧頂元素在順序棧中的下一個位置，base為棧底指針，指向棧底的位置。base空棧a進棧b進棧aabtopbasetopbasetoptoptopabcdee進棧abcdef進棧溢出abde出棧cbasebasebasetop順序棧的類型表示:#defineSTACK_INIT_SIZE100；#defineSTACKINCREMENT
3、10；typedefcharStackData;typedefstruct{//順序棧定義StackData*base;//棧底指針StackData*top;//棧頂指針intstacksize；//當前已分配的存儲空間}SeqStack；判棧空intStackEmpty(SeqStack*S){if(S->top==S->base)return1//判?？?空則返回1elsereturn0;//否則返回0}判棧滿intStackFull(SeqStack*S){if(S->top-S->base>=S->StackSize)return1//判棧滿,滿
4、則返回1elsereturn0;//否則返回0}順序棧的基本運算:初始化voidInitStack(SeqStack*S){//置空棧S->base=(StackData*)malloc(STACK_INIT_SIZE*sizeof(StackData)); if(!S->base)exit(OVERFLOW);S->top=S->base;S->stacksize=STACK_INIT_SIZE;Returnok;}入棧intPush(SeqStack*S,StackDatax){//插入元素x為新的棧頂元素if(StackFull(S)){S->bas
5、e=(StackData*)malloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(StackData));if(!S->base)exit(overflow);S->top=S->base+S->stacksize;S->stacksize+=STACKINCREMENT;//追加存儲空間}*(S->top)=x;（S->top）++;Returnok}取棧頂元素intGettop(SeqStack*S,StackData&x){//若棧空返回0,否則棧頂元素讀到x并返回1if(StackEmpty(S))
6、return0;(S->top)--;x=*(S->top);return1;}出棧intpop(SeqStack*S,StackData&x){//若棧空返回0,否則棧頂元素退出到x并返回1if(StackEmpty(S))return0;--(S->top);x=*(S->top);return1;}鏈式棧:棧的鏈接表示鏈式棧無棧滿問題，空間可擴充插入與刪除僅在棧頂處執(zhí)行鏈式棧的棧頂在鏈頭適合于多棧操作top鏈式棧(LinkStack)的定義typedefintStackData;typedefstructnode{StackDatadata;//結點
7、structnode*link;//鏈指針}StackNode;typedefstruct{StackNode*top;//棧頂指針}LinkStack;鏈式棧操作實現(xiàn)初始化voidInitStack(LinkStack*S){S->top=NULL;}入棧intPush(LinkStack*S,StackDatax){StackNode*p=(StackNode*)malloc(sizeof(StackNode));p->data=x;p->link=S->top;S->top=p;return1;}判?？読ntStackEmpty(LinkStack*
8、S){returnS->top==NULL;}出棧intPop(L
