데이터 구조 --- 스 택 과 대기 열의 종합 응용

실험 목적
데이터 구조 에서 대기 열의 기본 조작 을 익히 면 창고 와 대기 열의 구 조 를 결합 시 켜 실제 문 제 를 유연 하 게 해결 할 수 있다.
실험 문제
많은 언어 현상 에서 흔히 볼 수 있 는 abcba 와 같은 문자 입 니 다. 이런 문 자 는 왼쪽 에서 오른쪽으로 읽 는 것 과 오른쪽 에서 왼쪽으로 읽 는 결 과 는 같 습 니 다. 이런 문 자 는 흔히 말 하 는 답문 입 니 다.프로그램 을 설계 하면 주어진 문자 가 답장 인지 아 닌 지 를 판단 할 수 있다.
스 택 의 선진 적 인 후 출 과 대열 의 후진 선 출 을 고려 하여 이 두 가지 구 조 를 결합 하여 필요 한 기능 을 실현 할 수 있 습 니 다. 곧 문 자 를 각각 입 대 를 하고 스 택 에 들 어간 다음 에 차례대로 출력 하여 서로 다른 문자 가 있 는 지 여 부 를 판단 할 수 있 습 니 다. 발견 하면 문자 가 답문 이 아니 라 는 것 을 증명 합 니 다.
힌트
1. 대기 열의 주요 데이터 구 조 는 다음 과 같다.

typedef struct QNode{
char  data;
struct QNode *next;
}QNode,*Queueptr;
typedef struct{
Queueptr front;
Queueptr rear;
}linkQueue;

   2. 프로그램의 주 프레임 워 크 는 다음 과 같다.

scanf("%c",&c);
while(c!='#') {push(&s,c); EnQueue(&Q,c);       scanf("%c",&c);  }
while(!(s.top==s.base))
{  pop(&s,&a); DeQueue(&Q,&b);
if(a!=b) {printf("This isn't acycle
");exit(0);   }
}
printf("This is acycle
");  return OK;

넷. 이루어지다

#include<stdio.h>
#include<stdlib.h>

/**********************      **********************/
/*
               
*/
typedef struct queue
{    //        
	int data;
    struct queue *next;
}queue,*que;

typedef struct 
{
	 que front;   //      
	 que rear;    //      
}Q;


typedef struct  
{  //      
	int *top;
	int *base;
	int stacksize;
}sqstack;


/**********************    **********************/
/*
         。50   。 
*/
void initStack(sqstack &s)
{
     s.base=(int *)malloc(50*sizeof(sqstack));
     if(!s.base)
         printf("        !
");
     s.top=s.base;
     s.stacksize=50;
}

/*
         ，  bool  
*/
bool isEmpty(sqstack &s)
{
     bool result=true;
     if(s.top==s.base)
        result=false;
     else
        result=true;
     return result;
}

/*
    
*/
void push(sqstack &s,int e)
{
     if(s.top-s.base>=s.stacksize)//    ,        
     {
           s.base=(int *)realloc(s.base,(s.stacksize+10)*sizeof(sqstack));
           s.top=s.base+s.stacksize; // top       
           s.stacksize+=10;
     }
     *s.top++=e;
}

/*
    ，  char  
*/
char pop(sqstack &s,int &e)
{
    if(s.top==s.base)
        printf("    !"); 
    e=*--s.top;
    return e;
}

/*
          
*/
void initQ(Q &q)
{
     q.front=q.rear=(queue *)malloc(sizeof(queue));
     if(!q.front)
        printf("        !");
     q.front->next=NULL;
}

/*
    
*/
void EnQueue(Q &q,int e)
{
    queue *p=(queue *)malloc(sizeof(queue));
    p->data=e;
    p->next=NULL;
    
    q.rear->next=p; //    
    q.rear=p;       //      
}

/*
    ，  char  .
*/
char DeQueue(Q &q,int &e)
{
     queue *p=(queue *)malloc(sizeof(queue));
     if(q.front==q.rear)
        printf("    !");
     p = q.front->next;  //          t
     e = p->data;        
     q.front->next=p->next;//     
     if(q.rear==p)//       t，            (   t   )
        q.rear = q.front;
     free(p);
     return e;
     
}

/**********************   **********************/
int main()
{
    char c;
    int e,k;
    bool ss=true; 
    sqstack s;
    Q q;
    
    
    initStack(s);
    initQ(q);
    printf("     ，  #   ：
");
    scanf("%c",&c);
    while(c!='#') 
    {
     push(s,c);     //    
     EnQueue(q,c);	 //   
     scanf("%c",&c);  
    }
    while(!(s.top==s.base))//       
    {   
        pop(s,e);
        DeQueue(q,k);
	    if(e!=k) 
        {
         printf("This isn't a cycle！
");
         exit(0);
        }
    }
    printf("This is a cycle！
");  
    system("PAUSE");
    return 0;
}