数据结构----栈和队列的综合应用
一．实验目的
熟悉掌握数据结构中队列的基本操作，能够结合栈与队列的结构灵活解决一些实际中问题。
二．实验题目
在许多语言现象中，常见到一种形如abcba的文字，这种文字从左到右读和从右到左读结果是一样的，这种文字就是常说的回文。设计一个程序可以判断给定的一个文字是否是回文。
考虑到栈的先进后出以及队列的后进先出，可以结合这两种结构来实现需要的功能，即将文字分别入队和入栈，然后依次输出判断是否有不相同的字符，一旦发现就证明文字不是一个回文。
三．实现提示
1．队列的主要数据结构定义如下：
#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("存储空间分配失败!\n"); 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("请输入字符，以 # 结束：\n"); 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！\n"); exit(0); } } printf("This is a cycle！\n"); system("PAUSE"); return 0;}