数据结构实训作业(II)

//在下面的begin和end间填写相应代码
void inistack(TWSTACK &S)
//该函数实现初始化S，得到2个空栈。根据双向栈的示意图，理解初始化要求。
{
/***************begin***************/
    for(int i=0;i<N;i++){
        S.elem[i]=0;//每个元素置0
    }
    S.top1=0;
    S.top2=N-1;//初始化指针
/*************** end ***************/
}
int push(TWSTACK &S,int i,ElemType e)
//i取值1或2，分别对应左或右栈，将元素e压入S的对应栈。成功入栈返回1，否则返回0
{
/***************begin***************/
    if(i==1){
        if(S.top1>S.top2) return 0;
        S.elem[S.top1++]=e;
        return 1;
    }
    else{
        if(S.top1>S.top2) return 0;
        S.elem[S.top2--]=e;
        return 1;
    }
    /*************** end ***************/
}

int pop(TWSTACK &S,int i, ElemType &e)
//i取值1或2，分别对应左或右栈，将S对应栈的栈顶元素出栈，赋值给e。成功出栈返回1，否则返回0
{
/***************begin***************/
    if(i==1){
        if(S.top1==0) return 0;
        e=S.elem[--S.top1];
        return 1;
    }
    else{
        if(S.top2==N-1) return 0;
        e=S.elem[++S.top2];
        return 1;
    }

/*************** end ***************/
}
注意根据栈指针的特性规定前缀还是后缀

//在下面的begin和end间填写相应代码
void iniQueue(QUEUE &Q)
//该函数实现初始化Q
{
/***************begin***************/
    for(int i=0;i<MAXLENGTH;i++){
        Q.elem[i]=0;
    }
    Q.front=0;
    Q.length=0;
/*************** end ***************/
}
int enQueue(QUEUE &Q,ElemType e)
//将元素e入队Q。成功入栈返回1，否则返回0
{
/***************begin***************/
    if(Q.length==MAXLENGTH) return 0;
    Q.elem[(Q.front+Q.length)%MAXLENGTH]=e;
    Q.length++;
/*************** end ***************/
}
int deQueue(QUEUE &Q, ElemType &e)
//将Q队首元素出队，赋值给e。成功出队返回1，否则返回0
{
/***************begin***************/
    if(!Q.length) return 0;
    e=Q.elem[Q.front];
    Q.front=(Q.front+1)%MAXLENGTH;
    Q.length--;
/*************** end ***************/
}
注意循环链表的移动规则
判定双向链表为满的规则?

int isPalindrome(char *str)
//判断字符串str是否回文，是则返回1，否则返回0
{
/**********begin**********/
    char x,y;
    TWSTACK S;
    QUEUE Q;
    iniQueue(Q);
    inistack(S);
    while(*str!='@'){
        push(S,1,*str);
        enQueue(Q,*str);
        str++;
    }
    while(S.top1){
        pop(S,1,x);
        deQueue(Q,y);
        if(x!=y) return 0;
    }
    return 1;
/********** end **********/
}