用栈和队列来判断字符序列是不是回文 - 数据结构与算法

得分:0

回复 2楼 yuccn

#include <stdio.h>

#define N 82

typedef struct node squeue;
struct node
{
    char data[N];
    int front;
    int rear;

};

typedef struct snode sqstack;
struct snode
{
    char elem[N];
    int top;
};

void init_sqstack(sqstack &q);
void push_sqstack(sqstack &q, char x);
void pop_sqstack(sqstack &q, char &x);
void output_sqstack(sqstack q);

void init_squeue(squeue &s);
void push_squeue(squeue &s, char x);
void pop_squeue(squeue &s, char &x);
void output_squeue(squeue s);

void compare(squeue q, sqstack s);

int main(void)
{
    squeue s;
    sqstack l;
    char ch, sh, ch1, sh1;

    printf("init a stack: ");
    init_sqstack(l);
    printf("\npush some number to the stack: ");
    ch=getchar();
    while(ch != ' ')
    {
        push_sqstack(l,ch);
        ch=getchar();
    }

    printf("\ninit a squeue: ");
    init_squeue(s);
    printf("\npush some number to the squeue: ");
    sh=getchar();
    while(sh != ' ')
    {
        push_squeue(s,sh);
        sh=getchar();
    }

    printf("\nwhether is huiwen.");

    compare(s,l);
    return 0;
}

void init_squeue(squeue &s)
{
    s.front=s.rear=0;
}

void push_squeue(squeue &s, char x)
{
    if(s.front==(s.rear+1)%N)
        printf("Error.\n");
    else
    {
        s.data[s.rear]=x;
        s.rear=(s.rear+1)%N;
    }
}

void pop_squeue(squeue &s, char &x)
{
    if(s.front==s.rear)
        printf("the squeue is empty.\n");
    else
    {
        x=s.data[s.front];
        //printf("%c",x);
        s.front=(s.front+1)%N;
    }
}

void init_sqstack(sqstack &q)
{
    q.top=0;
}

void push_sqstack(sqstack &q, char x)
{
    if(q.top>=N)
        printf("the sqstack is full.\n");
    else
    {
        q.top++;
        q.elem[q.top]=x;
    }
}

void pop_sqstack(sqstack &q, char &x)
{
    if(q.top==0)
        printf("the sqstack is empty.\n");
    else
    {
        x=q.elem[q.top];
        q.top--;
    }
}

void compare(squeue s, sqstack q)
{

    char ch1, ch2;

    if(s.front==s.rear || q.top==0)
        printf("It's not huiwen.\n");

    pop_sqstack(q,ch1);
    pop_squeue(s,ch2);
    while(ch1!=NULL &&ch2!=NULL)
    {
        if(ch1==ch2)
        {
                pop_sqstack(q,ch1);
                pop_squeue(s,ch2);
        }
        else
        {
            printf("It's not huiwen.\n");
            break;
        }
    }

}

void output_squeue(squeue s)
{
    for(s.front=0;s.front<s.rear ; s.front ++)
        printf("%d", s.data [s.front ]);
}

void output_sqstack(sqstack q)
{
    while(q.top>0)
        printf("%c", q.elem[q.top]);
}