①i进栈,i出栈,j进栈,j出栈,k进栈,k出栈。此时具有最小值的排在最前面p;位置,具有中间 值的排在其后p位置,具有最大值的排在p位置,有p<p<pk,不可能出现p<pk<p的情形 ②i进栈,i出栈,j进栈,k进栈,k出栈,j出栈。此时具有最小值的排在最前面p;位置,具有最大 值的排在p位置,具有中间值的排在最后p位置,有p<pk<p,不可能出现p<pk<p的情形; ③i进栈,j进栈,j出栈,i出栈,k进栈,k出栈。此时具有中间值的排在最前面p位置,具有最小 值的排在其后p位置,有p<p<pk,不可能出现p<pk<p1的情形; ④i进栈,j进栈,j出栈,k进栈,k出栈,i出栈。此时具有中间值的排在最前面p位置,具有最大 值的排在其后p位置,具有最小值的排在p位置,有p<p<p,也不可能出现p<pk<p1的情形 ⑤i进栈,j进栈,k进栈,k出栈,j出栈,i出栈。此时具有最大值的排在最前面p位置,具有中间 值的排在其后p位置,具有最小值的排在p位置,有p<p<p,也不可能出现p<pk<p的情形; 3-4将编号为0和1的两个栈存放于一个数组空间Ⅴm中,栈底分别处于数组的两端。当第0号栈的栈顶 指针top0等于-1时该栈为空,当第1号栈的栈顶指针top[]等于m时该栈为空。两个栈均从两端向中间 增长。当向第θ号栈插入一个新元素时,使topω增1得到新的栈顶位置,当向第1号栈插入一个新元素 时,使top[1]减1得到新的栈顶位置。当top[O]+1==top[]时或topo]==top[l]-1时,栈空间满,此时不 能再向任一栈加入新的元素。试定义这种双栈( Double stack)结构的类定义,并实现判栈空、判栈满、插入、 删除算法。 【解答】 top[OI toll bot[1] 双栈的类定义如下: #include <assert. h template <class Type> class DblStack i ∥双栈的类定义 nt top[2], bot2]; ∥双栈的栈顶指针和栈底指针 I ∥栈数组 ∥栈最大可容纳元素个数 DbIStack( int Sz=10 ) ∥初始化双栈,总体积m的默认值为10 ∥析构函数 oid DblPush( const Type& x, int 1); 把x插入到栈i的栈顶 int DblPop( int i ) ∥退掉位于栈i栈顶的元素 Type* DblGetTop( int 1) ∥返回栈i栈顶元素的值 int IsEmpty(inti) consti return top=bo;}∥判栈i空否,空则返回1,否则返回0 sFull ()const( return top[O+l ==top[1];) ∥判栈满否,满则返回1,否则返回0 ∥清空栈i的内容 template <class Type> DblStack<Type>: DblStack int Sz): m(sz), top[o](-1), bot[0J(1),top(1](sz), bot([1](sz)i ∥建立一个最大尺寸为sz的空栈,若分配不成功则错误处理 elements new Type[m]: ∥创建栈的数组空间 assert( elements I= NULL ) 断言:动态存储分配成功与否19 ① i 进栈，i 出栈，j 进栈，j 出栈，k 进栈，k 出栈。此时具有最小值的排在最前面 pi 位置，具有中间 值的排在其后 pj 位置，具有最大值的排在 pk 位置，有 pi < pj < pk, 不可能出现 pj < pk < pi 的情形； ② i 进栈，i 出栈，j 进栈，k 进栈，k 出栈，j 出栈。此时具有最小值的排在最前面 pi 位置，具有最大 值的排在 pj 位置，具有中间值的排在最后 pk 位置，有 pi < pk < pj , 不可能出现 pj < pk < pi 的情形； ③ i 进栈，j 进栈，j 出栈，i 出栈，k 进栈，k 出栈。此时具有中间值的排在最前面 pi 位置，具有最小 值的排在其后 pj 位置，有 pj < pi < pk, 不可能出现 pj < pk < pi 的情形； ④ i 进栈，j 进栈，j 出栈，k 进栈，k 出栈，i 出栈。此时具有中间值的排在最前面 pi 位置，具有最大 值的排在其后 pj 位置，具有最小值的排在 pk 位置，有 pk < pi < pj, 也不可能出现 pj < pk < pi 的情形； ⑤ i 进栈，j 进栈，k 进栈，k 出栈，j 出栈，i 出栈。此时具有最大值的排在最前面 pi 位置，具有中间 值的排在其后 pj 位置，具有最小值的排在 pk 位置，有 pk < pj < pi, 也不可能出现 pj < pk < pi 的情形； 3-4 将编号为 0 和 1 的两个栈存放于一个数组空间 V[m]中，栈底分别处于数组的两端。当第 0 号栈的栈顶 指针 top[0]等于-1 时该栈为空，当第 1 号栈的栈顶指针 top[1]等于 m 时该栈为空。两个栈均从两端向中间 增长。当向第 0 号栈插入一个新元素时，使 top[0]增 1 得到新的栈顶位置，当向第 1 号栈插入一个新元素 时，使 top[1]减 1 得到新的栈顶位置。当 top[0]+1 == top[1]时或 top[0] == top[1]-1 时，栈空间满，此时不 能再向任一栈加入新的元素。试定义这种双栈(Double Stack)结构的类定义，并实现判栈空、判栈满、插入、 删除算法。 【解答】 双栈的类定义如下： #include <assert.h> template <class Type> class DblStack { //双栈的类定义 private: int top[2], bot[2]; //双栈的栈顶指针和栈底指针 Type *elements; //栈数组 int m; //栈最大可容纳元素个数 public: DblStack ( int sz =10 ); //初始化双栈, 总体积 m 的默认值为 10 ~DblStack ( ) { delete [ ] elements; } //析构函数 void DblPush ( const Type& x, int i ); //把 x 插入到栈 i 的栈顶 int DblPop ( int i ); //退掉位于栈 i 栈顶的元素 Type * DblGetTop ( int i ); //返回栈 i 栈顶元素的值 int IsEmpty ( int i ) const { return top[i] == bot[i]; } //判栈 i 空否, 空则返回 1, 否则返回 0 int IsFull ( ) const { return top[0]+1 == top[1]; } //判栈满否, 满则返回 1, 否则返回 0 void MakeEmpty ( int i ); //清空栈 i 的内容 } template <class Type> DblStack<Type> :: DblStack ( int sz ) : m(sz), top[0] (-1), bot[0](-1), top[1](sz), bot[1](sz) { //建立一个最大尺寸为 sz 的空栈, 若分配不成功则错误处理。 elements = new Type[m]; //创建栈的数组空间 assert ( elements != NULL ); //断言: 动态存储分配成功与否 } 0 m-1 bot[0] top[0] top[1] bot[1]