C++-堆棧的基本知識(shí)

電子教案Version2.0綜合專題〔二〕：堆棧及其應(yīng)用1.什么是堆棧？通俗地講，堆?！瞫tack〕是內(nèi)存中的一個(gè)數(shù)組(或者鏈表)，該數(shù)組(或者鏈表)的兩端分別稱為棧頂(top)和棧底(bottom)，而數(shù)據(jù)元素的插入和刪除只能在棧頂進(jìn)行。出(退)棧(pop)進(jìn)(入)棧(push)a0a1a2...an-1...bottomtop數(shù)組堆棧示意圖2.堆棧的操作特點(diǎn)后進(jìn)先出〔LastInFirstOut〕簡(jiǎn)稱LIFO先進(jìn)后出〔FirstInLastOut〕簡(jiǎn)稱FILObottomtoppush子彈倉(cāng)bottomtoppop子彈倉(cāng)3.堆棧數(shù)據(jù)結(jié)構(gòu)與根本操作的實(shí)現(xiàn)〔1〕數(shù)組棧數(shù)據(jù)結(jié)構(gòu)#defineN100/*棧最大容量*/structSTACK{ints[N];/*棧數(shù)組*/inttop;/*棧頂指針*/};（2）入棧與退棧操作...top=-1空棧1...top=01234...top=3123...top=2/*入棧操作函數(shù)*/voidpush(structSTACK

*p,intx){if(p->top>=N-1)return;/*棧滿不進(jìn)行入棧操作*/p->top++;/*棧頂指針自加1*/p->s[p->top]=x;/*x存入棧頂*/}/*退棧操作函數(shù)*/intpop(structSTACK

*p){intx;if(p->top<=-1)return0;/*?？詹贿M(jìn)行退棧操作*/x=p->s[p->top];/*取棧頂元素*/p->top--;/*棧頂指針自減1*/

returnx;/*返回棧頂元素*/}〔3〕測(cè)試棧空與棧滿操作/*測(cè)試?？蘸瘮?shù)*/intempty(structSTACK

*p){returnp->top<=-1;}/*測(cè)試棧滿函數(shù)*/intfull(structSTACK

*p){returnp->top>=N-1;}〔4〕置空棧操作〔棧初始化〕/*置空棧函數(shù)*/voidinit(structSTACK

*p){p->top==-1;}4.堆棧應(yīng)用舉例2002年〔秋〕西南交大博士研究生入學(xué)考試程序設(shè)計(jì)〔C語(yǔ)言〕試卷最后一題編程輸入一個(gè)自然數(shù)n，輸出該自然數(shù)所有不增的和式。如：n=4n=54=45=54=3+15=4+14=2+25=3+24=2+1+15=3+1+14=1+1+1+15=2+2+15=2+1+1+15=1+1+1+1+1算法設(shè)計(jì)(1)置?？?輸入n值;(2)m=n;/*m為當(dāng)前求和項(xiàng)，n作為剩余和*/(3)while(m>0){push(m);n=n-m;if(n等于0){以入棧順序按要求格式打印各求和項(xiàng);do{m=pop();n=n+m;m--;}while(m為0且棧不空);}m=min(m,n);}221...top棧6=2+2+1+?m=1n=1源程序#include"stdio.h"#defineMAX_N10voidmain(){intn,m,n0,s[MAX_N],top=-1,i;printf("Inputn=");scanf("%d",&n);m=n;n0=n;while(m>0){s[++top]=m;n-=m;if(n==0){printf("%d=%d",n0,s[0]);for(i=1;i<=top;i++)printf("+%d",s[i]);printf("\n");do{m=s[top--];n+=m;m--;}while(m==0&&top!=-1);}m=m<=n?m:n;}}問題與思考：