文档介绍：数据结构****题课-栈和队列
基本知识题
算法题
练****题
8/5/2018
基本知识题
设有一顺序栈S,元素s1,s2,s3,s4,s5,s6依次进栈,如果6个元素出线的顺序是s2,s3,s4, s6 , s5,s1,则栈的容量至少应该是_____。
设有一顺序栈已含3个元素,元素a4正等待进栈。那么下列4个序列中不可能出现的出栈序列是____。
①a3,a2,a4,a1 ②a3,a1,a4,a2
③a3,a4,a2,a1 ④a4,a3,a2,a1
8/5/2018
基本知识题
若一个栈以向量V[1..n]存储,初始栈顶指针top为n+1,则下面x进栈的正确操作是( )。
=top+1; V[top]=x
B. V[top]=x; top=top+1
C. top=top-1; V[top]:=x
D. V[top]=x; top=top-1
8/5/2018
基本知识题
循环队列存储在数组A[0..m]中,则入队的操作是:
A. rear=rear+1
B. rear=(rear+1)mod(m-1)
C. rear=(rear+1)mod m
D. rear=(rear+1)mod(m+1)
8/5/2018
算法题
假设有二个栈共同使用一块顺序存储的空间(双栈Double Stack) ,为简单起见可设为共同使用数组a[0..199]。它们的栈底分别设在数组的两端,而栈顶指针在进行插入操作时,向中间方向移动。请给出进出栈的算法。
8/5/2018
算法题
0和1的两个栈存放于一个数组空间a[m]中,栈底分别处于数组的两端
其中0栈是从底部开始增长的栈;1栈是从顶部开始增长的栈
8/5/2018
算法题
template <class Type> class DblStack{//双栈的类定义
private:
int size;
int top[2], bot[2]; //双栈的栈顶指针和栈底指针
Type *a; //栈数组
8/5/2018
算法题
public:
DblStack ( int length )
{ size = length;
top[0]=bot[0]=-1;
top[1]=bot[1]=size;
a = new Type[size];
}
~DblStack ( ) { delete [ ] a; }
void DblPush ( const Type& x, int i );
Type DblPop (int i);
8/5/2018
算法题
template <class Type> void DblStack<Type> :: DblPush ( const Type& x, int i ) {
if(top[0]+1 == top[1]) return; // 栈满
if ( i == 0 ) a[ ++top[0] ] = x;
else a[--top[1] ] = x;
}
8/5/2018
算法题
template<class Type> Type DblStack<Type>::
DblPop(int i){
if(top[i] == bot[i]) return null;
if ( i == 0 )
return top[0]--; //栈0情形:栈顶指针减1
else
return top[1]++; //栈1情形:栈顶指针加1
}
8/5/2018