已知Q是一个非空队列，S是一个空栈？

Question

仅用队列和栈的ADT函数和少量工作变量，使用C语言编写一个算法，将队列Q中的所有元素逆置。栈的ADT函数有：makeEmpty(s:stack); 置空栈push(s:stack; value:datatype); 新元素value进栈pop(s:stack):datatype; 出栈，返回栈顶值isEmpty(s:stack):boolean; 判栈空否队列的ADT函数有enqueue(q:queue;value:datatype); 元素value进队deQueue(q:queue):datatype; 出队列，返回队头值isEmpty(q:queue):boolean; 判队列空否

Answer 1

#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");
}