C++-堆栈的基本知识

电子教案Version2.0综合专题〔二〕：堆栈及其应用1.什么是堆栈？通俗地讲，堆栈〔stack〕是内存中的一个数组(或者链表)，该数组(或者链表)的两端分别称为栈顶(top)和栈底(bottom)，而数据元素的插入和删除只能在栈顶进行。出(退)栈(pop)进(入)栈(push)a0a1a2...an-1...bottomtop数组堆栈示意图2.堆栈的操作特点后进先出〔LastInFirstOut〕简称LIFO先进后出〔FirstInLastOut〕简称FILObottomtoppush子弹仓bottomtoppop子弹仓3.堆栈数据结构与根本操作的实现〔1〕数组栈数据结构#defineN100/*栈最大容量*/structSTACK{ints[N];/*栈数组*/inttop;/*栈顶指针*/};（2）入栈与退栈操作...top=-1空栈1...top=01234...top=3123...top=2/*入栈操作函数*/voidpush(structSTACK

*p,intx){if(p->top>=N-1)return;/*栈满不进行入栈操作*/p->top++;/*栈顶指针自加1*/p->s[p->top]=x;/*x存入栈顶*/}/*退栈操作函数*/intpop(structSTACK

*p){intx;if(p->top<=-1)return0;/*栈空不进行退栈操作*/x=p->s[p->top];/*取栈顶元素*/p->top--;/*栈顶指针自减1*/

returnx;/*返回栈顶元素*/}〔3〕测试栈空与栈满操作/*测试栈空函数*/intempty(structSTACK

*p){returnp->top<=-1;}/*测试栈满函数*/intfull(structSTACK

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

*p){p->top==-1;}4.堆栈应用举例2002年〔秋〕西南交大博士研究生入学考试程序设计〔C语言〕试卷最后一题编程输入一个自然数n，输出该自然数所有不增的和式。如：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算法设计(1)置栈空;输入n值;(2)m=n;/*m为当前求和项，n作为剩余和*/(3)while(m>0){push(m);n=n-m;if(n等于0){以入栈顺序按要求格式打印各求和项;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;}}问题与思考：