数据结构课件chp3

《数据结构课件chp3》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、栈(Stack)队列(Queue)第三章栈与队列3.2栈(Stack)只允许在一端插入和删除的顺序表允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)特点后进先出(LIFO)templateclassStack{public:Stack(int=10);//构造函数voidPush(constType&item);//进栈TypePop();//出栈TypeGetTop();//取栈顶元素voidMakeEmpty();//置空栈intIsEmpty()const;//判栈空否intIsFull()const;

2、//判栈满否}栈的抽象数据类型#includetemplateclassStack{public:Stack(int=10);//构造函数~Stack(){delete[]elements;}//析构函数voidPush(constType&item);//进栈TypePop();//出栈TypeGetTop();//取栈顶元素voidMakeEmpty(){top=-1;}//置空栈intIsEmpty()const{returntop==-1;}栈的数组表示—顺序栈intIsFull()const{retu

3、rntop==maxSize-1;}private:inttop;//栈顶数组指针Type*elements;//栈数组intmaxSize;//栈最大容量}templateStack::Stack(ints):top(-1),maxSize(s){elements=newType[maxSize];assert(elements!=0);//断言}进栈示例退栈示例templatevoidStack::Push(constType&item){assert(!IsFull());//先

4、决条件断言elements[++top]=item;//加入新元素}templateTypeStack::Pop(){assert(!IsEmpty());//先决条件断言returnelements[top--];//退出栈顶元素}templateTypestack::GetTop(){assert(!IsEmpty());//先决条件断言returnelements[top];//取出栈顶元素}例3.1系统栈栈的应用举例例：括号匹配问题：假设一个算术表达式中允许包含两种括号：圆括号

5、与方括号，其嵌套的次序随意。请设计一个算法判断一个算术表达式中的括号是否匹配。voidcheck(){Stacks;charch[80],*p,e;printf("请输入表达式");gets(ch);p=ch;while(*p)//没到串尾switch(*p){case'(':case'[':s.Push(*p++);break;//左括号入栈，且p++case')':case']':if(!s.Empty()){e=s.Pop();//弹出栈顶元素if(*p==')‘&&e!='('

6、

7、*p==']‘&&e!='['){printf("左右括号不

8、配对");exit(1);}else{p++;break;//跳出switch语句}}//Emptyelse{//栈空printf("缺乏左括号");exit(1);}default:p++;//其它字符不处理，指针向后移}if(s.Empty())//字符串结束时栈空printf("括号匹配");elseprintf("缺乏右括号");}多栈处理栈浮动技术n栈共享一个数组空间V[m]设立栈顶指针数组t[n+1]和栈底指针数组b[n+1]t[i]和b[i]分别指示第i个栈的栈顶与栈底b[n]作为控制量，指到数组最高下标各栈初始分配空间s

9、=m/n指针初始值t[0]=b[0]=-1b[n]=m-1t[i]=b[i]=b[i-1]+s,i=1,2,…,n-1插入新元素时的栈满处理StackFull()双栈共享一个栈空间templatevoidPush(constinti,constType&item){if(t[i]==b[i+1])StackFull(i);elseV[++t[i]]=item;//第i个栈进栈}templateType*Pop(consti){if(t[i]==b[i]){StackEmpty(i);return0;}el

10、sereturn&V[t[i]--];//第i个栈出栈}思考题：P102(2)队列(Queue