## 問題描述 > Q是一個隊列，S是一個空棧，實現將隊列中的元素逆置的算法 ## 算法思想 > 因為Q是一個隊列，如果僅僅按照隊列先進先出的特性時無法完成自身元素逆置操作的，而題目中又給出了一個可用棧，那么我們只需借助棧先進后出的特性完成元素逆置。 將隊列中的元素逐個出隊，然后入棧，最后再入隊即可完成隊列元素的逆置。 ## 算法描述 ~~~ //創建隊列 while(x!=999){ EnQueue(&Q,x); scanf("%d",&x); } //出隊->入棧 while(Q.front!=Q.rear){ DeQueue(&Q,&x); EnStack(&S,x); } InitQueue(&Q); //出棧->入隊 while(S.top!=-1){ DeStack(&S,&x); EnQueue(&Q,x); } ~~~ 具體代碼見附件。 ## 附件 ~~~ #include<stdio.h> #include<stdlib.h> #define MaxSize 10 typedef int ElemType; //定義隊列 typedef struct{ ElemType data[MaxSize]; int front, rear; }SqQueue; //定義棧 typedef struct{ ElemType data[MaxSize]; int top; }SqStack; void InitQueue(SqQueue*); void EnQueue(SqQueue*,ElemType); void DeQueue(SqQueue*,ElemType*); void InitStack(SqStack*); void EnStack(SqStack*,ElemType); void DeStack(SqStack*,ElemType*); void PrintQueue(SqQueue*); int main(int argc,char* argv[]) { SqQueue Q; SqStack S; InitQueue(&Q); InitStack(&S); ElemType x; scanf("%d",&x); while(x!=999){ EnQueue(&Q,x); scanf("%d",&x); } while(Q.front!=Q.rear){ DeQueue(&Q,&x); EnStack(&S,x); } InitQueue(&Q); while(S.top!=-1){ DeStack(&S,&x); EnQueue(&Q,x); } PrintQueue(&Q); return 0; } //初始化隊列 void InitQueue(SqQueue *Q) { Q->front=0; Q->rear=0; } //入隊 void EnQueue(SqQueue *Q, ElemType x) { Q->data[Q->rear++]=x; } //出隊 void DeQueue(SqQueue *Q, ElemType *x) { if(Q->front==Q->rear){ printf("The Queue is empty!\n"); } *x=Q->data[Q->front++]; } //初始化棧 void InitStack(SqStack *S) { S->top=-1; } //入棧 void EnStack(SqStack *S,ElemType x) { S->data[++S->top]=x; } //出棧 void DeStack(SqStack *S,ElemType *x) { if(S->top==-1){ printf("The stack is empty!\n"); return; } *x=S->data[S->top--]; } //打印全部隊列元素 void PrintQueue(SqQueue *Q) { while(Q->front!=Q->rear){ printf("%4d",Q->data[Q->front++]); } printf("\n"); } ~~~