已知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 0typedef 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");}