第三章 栈和队列
一、选择题
1．已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（ ）
A.5，4，3，2，1，6    B.2，3，5，6，1，4
C.3，2，5，4，1，6    D.1，4，6，5，2，3
2．在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（ ）
A．top不变          B．top=0          C．top--        D．top++
3．在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为（ ）
A．rear％n= = front          B．（front+l）％n= = rear
C．rear％n -1= = front      D．(rear+l)％n= = front
4．在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为（ ）
A．rear％n= = front          B．front+l= rear
C．rear= = front             D．(rear+l)％n= front
5．在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为（ ）
A．front=front->next   　 B．rear=rear->next
C．rear=front->next     　D．front=rear->next
6．某堆栈的输入序列为1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素为（ ）
A．i     B．n-i     C．n-i+1   D．哪个元素无所谓
7．用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时(     )。
A．仅修改队头指针          B. 仅修改队尾指针
C. 队头、队尾指针都要修改  D. 队头,队尾指针都可能要修改
二、解答题
1．一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。 试为此双向栈设计初始化InitStack ( S ) 、入栈Push( S , i , x) 和出栈Pop( S , i )等算法， 其中i为0 或1， 用以表示栈号。
2．利用两个栈S1、S2模拟一个队列时，如何使用栈的运输实现队列的插入、删除运算。









参 考 答 案
第三章 栈和队列
一、选择题
1．C
2．C
3．D
4．C
5．A
6．C
7．D
二、解答题
1．
#define M 20
struct DStack{
    Selemtype data[M];
    int top1,top2;
};
void InitStack(DStack &s)
{
    s.top1=0;
    s.top2=M-1;
}
int IsEmpty(DStack s,int i)
{
    switch(i)
    {
    case 0:return s.top1==0;
    case 1:return s.top2==M-1;
    }
}
int IsFull(DStack s)
{
    return s.top1>s.top2;
}
void Push(DStack &s ,int i,Selemtype x)
{
    if (IsFull(s))
        {
            cout<<"full"<<endl;
            return;
        }
    switch(i)
    {
    case 0:
        s.data[s.top1]=x;
        s.top1++;
        break;
    case 1:
        s.data[s.top2]=x;
        s.top2--;
        break;
    }
    return;
}
Selemtype Pop(DStack &s,int i)
{
    Selemtype e;
    if(IsEmpty(s,i))
    {
        cout<<"Empty"<<endl;
        exit(-1);
    }
    switch(i)
    {
    case 0:
        s.top1--;
        e=s.data[s.top1];
        break;
    case 1:
        s.top2++;
        e=s.data[s.top2];
    }
    return e;
}
2．
#define M 3
struct Stack{
    Qelemtype data[M];
    int top;
};
struct Queue{
    Stack s1;
    Stack s2;
};
void InitQueue(Queue &Q)
{
    Q.s1.top=0;
    Q.s2.top=0;
}
int IsEmpty(Queue &Q)
{
    if(Q.s1.top==0&&Q.s2.top==0)
        return 1;
    if(Q.s2.top==0&&Q.s1.top!=0)
    {
        while(Q.s1.top!=0)
            Q.s2.data[Q.s2.top++]=Q.s1.data[--Q.s1.top];
    }
    return 0;
}

int IsFull(Queue &Q)
{
    if(Q.s1.top==M&&Q.s2.top!=0)
        return 1;
    if(Q.s1.top==M&&Q.s2.top==0)
    {
        while(Q.s1.top!=0)
            Q.s2.data[Q.s2.top++]=Q.s1.data[--Q.s1.top];
        return 0;
    }
    if(Q.s1.top!=M)
        return 0;
}

void InQueue(Queue &Q,Qelemtype e)
{
    if(IsFull(Q))
    {
        cout<<"OVERFLOW"<<endl;
        exit(-1);
    }
    Q.s1.data[Q.s1.top++]=e;
}

void DeQueue(Queue &Q,Qelemtype &e)
{
    if(IsEmpty(Q))
    {
        cout<<"UNDERFLOW"<<endl;
        exit(-1);
    }
    e=Q.s2.data[--Q.s2.top];
}