#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define OVERFLOW -1
#define ERROR 0
typedef struct
{
int *base;
int *top;
int stacksize;
}SqStack;
typedef struct QNode
{
int data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
int InitStack(SqStack &S)
{
S.base=(int*)malloc(100*sizeof(int));
if(!S.base)exit(OVERFLOW);
S.top=S.base;
S.stacksize=100;
return OK;
}
int Push(SqStack &S,int e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(int *)realloc(S.base,(S.stacksize+100)*sizeof(int));
if(!S.base)exit(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=100;
}
*S.top++=e;
return OK;
}
int Pop(SqStack &S)
{
int e;
if(S.top==S.base)
return ERROR;
e=*--S.top;
return e;
}
int SIsEmpty(SqStack &S)
{
if (S.top-S.base==0) return(1);
else return(0);
}
int makeEmpty(SqStack &S)
{
while(S.top!=S.base)
Pop(S);
return OK;
}
int InitQueue(LinkQueue &Q)
{
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front)exit(OVERFLOW);
Q.front->next=NULL;
return OK;
}
int EnQueue(LinkQueue &Q,int e)
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
if(!p)exit(OVERFLOW);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}
int DeQueue(LinkQueue &Q)
{
int e;
QueuePtr p;
if(Q.front==Q.rear)
return ERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
free(p);
return e;
}
int QIsEmpty(LinkQueue &Q)
{
if(Q.front==Q.rear)
return(1);
else return(0);
}
void main()
{
SqStack s;
LinkQueue q;
int n,data,e;
InitStack(s);
InitQueue(q);
if(SIsEmpty(s))
makeEmpty(s);
if(QIsEmpty(q))
{
printf("Queue is empty!\n");
printf("Please input the length of the queue:\n");
scanf("%d",&n);
printf("Please input the data of the Queue:\n");
for(int i=0;i<n;i++)
{
scanf("%d",&data);
EnQueue(q,data);
}
}
QueuePtr p;
p=q.front->next;
printf("The queue is:");
while(p)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
for(int i=0;i<n;i++)
{
e=DeQueue(q);
Push(s,e);
}
for(i=0;i<n;i++)
{
e=Pop(s);
EnQueue(q,e);
}
printf("After reverse the Queue is:");
for(i=0;i<n;i++)
{
data=DeQueue(q);
printf("%d ",data);
}
printf("\n");
}
