第三章栈和队列-点.ppt

第三章 栈、队列和串; 举例1：家里吃饭的碗，通常在洗干净后一个一个地摞在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。 举例2：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。;栈的存储结构 顺序栈 实现：一维数组data[StackSize]（数组中下标为0的一端为栈底）;顺序栈的实现 const int StackSize =20 //栈的最大长度 templateclass T //定义模板类SeqStack class SeqStack { public: SeqStack( ) {top=-1;} ~SeqStack( ) { } void Push(T x); //将数据元素x入栈 T Pop(); //弹出栈顶元素 T GetTop( ) //读出栈顶元素 { if(top!=-1) return(data[top]);} bool Empty( ) {top==-1?return 1:return 0;} private: T data[StackSize]; //存放栈元素的数组 int top; //栈顶指针 };1.入栈 templateclass T void SeqStackT::Push(T x) { if (top==StackSize-1) throw”overflow”; else data[++top]=x; };2. 出栈 templateclass T T SeqStackT::Pop() { if (top==-1) throw“underflow”; return(data[top--]); }; 结论：由于栈的插入和删除操作具有它的特殊性，所以用顺序存储结构表示的栈并不存在插入删除数据元素时需要移动的问题，但栈容量难以扩充的弱点仍没有摆脱。; 0;共享栈的实现 const int StackSize =50 //栈的最大长度 templateclass T //定义模板类BothStack class BothStack { public: BothStack( ) {top1=-1; top2=StackSize;} ~ BothStack( ) { } void Push(int i,T x); //将数据元素x入栈i T Pop(int i); //弹出栈i的栈顶元素 T GetTop(int i); //读出栈i的栈顶元素 bool Empty( int i); // 判断栈i是否为空 private: T data[StackSize]; //存放两个栈的数组 int top1，top2; //栈顶指针 };1.入栈 templateclass T void BothStackT::Push(int i,T x) { if (top1+1==top2) throw”overflow”; if (i==1) data[++top1]=x; if (i==2) data[--top2]=x; };2. 出栈 templateclass T T BothStackT::Pop(int i) { if (i==1) { if(top1==-1) throw“underflow”; return(data[top1- -]); } if (i==2) { if(top2==StackSize) throw“underflow”; return(data[top2++]); } } ;思考： T GetTop(int i); //读出栈i的栈顶元素 bool Empty( int i); // 判断栈i是否为空 这两个算法如何实现？;栈的链式存储 若是栈中元素的数目变化范围较大或不