用队列将栈中元素逆置

题目

编程实现利用队列将栈中元素逆置的算法。

逆置函数

void Inverse(Stack *S,Queue *Q){
    ElemType x;
    while(!IsEmpty(S)){  //函数重载
        Top(S,&x);
        EnQueue(Q,x);
        Pop(S);
    }
    while(!IsEmpty(Q)){  //函数重载
        Front(Q,&x);
        Push(S,x);
        DeQueue(Q);
    }
}

完整程序

#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define N 100
typedef int BOOL;
typedef int ElemType;

typedef struct{
    int top;
    int maxSize;
    ElemType *element;
}Stack;

/*
void Create1(Stack *S, int mSize);
BOOL IsEmpty1(Stack *S);
BOOL IsFULL1(Stack *S);
BOOL Top(Stack *S,ElemType *x);
BOOL Push(Stack *S,ElemType x);
BOOL Pop(Stack *S);
void Create2(Queue *Q,int mSize);
BOOL IsEmpty2(Queue *Q);
BOOL IsFULL2(Queue *Q);
BOOL Front2(Queue *Q,ElemType *x);
BOOL DeQueue(Queue *Q);
void Output(Stack *S,int n);
int Inverse(Stack *S,Queue *Q,int n);
*/

void Create1(Stack *S, int mSize){
    S->maxSize=mSize-1;
    S->element=(ElemType*)malloc(sizeof(ElemType)*mSize);
    S->top=-1;
}

BOOL IsEmpty(Stack *S){
    return S->top==-1;
}

BOOL IsFULL1(Stack *S){
    return S->top==S->maxSize;
}

BOOL Top(Stack *S,ElemType *x){
    if(IsEmpty(S))
        return FALSE;
    *x=S->element[S->top];
    return TRUE;
}

BOOL Push(Stack *S,ElemType x){
    if(IsFULL1(S))
        return FALSE;
    S->top++;
    S->element[S->top]=x;
    return TRUE;
}

BOOL Pop(Stack *S){
    if(IsEmpty(S))
        return FALSE;
    S->top--;
    return TRUE;
}

typedef struct{
    int front;
    int rear;
    int maxSize;
    ElemType *element;
}Queue;

void Create2(Queue *Q,int mSize){
    Q->maxSize=mSize;
    Q->element=(ElemType*)malloc(sizeof(ElemType)*mSize);
    Q->front=Q->rear=0;
}

BOOL IsEmpty(Queue *Q){
    return Q->front==Q->rear;
}

BOOL IsFULL2(Queue *Q){
    return (Q->rear+1)%Q->maxSize==Q->front;
}

BOOL Front(Queue *Q,ElemType *x){
    if(IsEmpty(Q))
        return FALSE;
    *x=Q->element[(Q->front+1)%Q->maxSize];
    return TRUE;
}

BOOL EnQueue(Queue *Q,ElemType x){
    if(IsFULL2(Q))
        return FALSE;
    Q->rear=(Q->rear+1)%Q->maxSize;
    Q->element[Q->rear]=x;
    return TRUE;
}

BOOL DeQueue(Queue *Q){
    if(IsEmpty(Q)){
        return FALSE; 
    }
    Q->front=(Q->front+1)%Q->maxSize;
    return TRUE;
}

/*
void Output(Stack *S,int n){
    int i;
    i=S->top;
    if(S->top==-1){
        printf("NULL");
    }
    while(S->top!=-1){
        printf("%d",S[i--]);
    }
    printf("\n");
}
*/

void PrintStack(Stack *S){
    if(!IsEmpty(S)){
        for(int i=S->top;i>=0;i--){   //不需要top-1，因为top指向栈顶
            printf("%d ",S->element[i]);
        }
    }
    else printf("The stack is empty\n");
}


/*
int Inverse(Stack *S,Queue *Q,int n){
    int i;
    ElemType a[N];
    for(i=0;i<n;i++){
        if(IsEmpty1(S)){
            return FALSE;
        }
        a[i]=S->element[S->top];
        EnQueue(Q,a[i]);
        Pop(S);
    }
    for(i=0;i<n;i++){
        if(IsEmpty2(Q)){
            return FALSE;
        }
        a[i]=Q->element[Q->front+1%Q->maxSize];
        Push(S,a[i]);
        DeQueue(Q);
    }
}
*/



void Inverse(Stack *S,Queue *Q){
    ElemType x;
    while(!IsEmpty(S)){  //函数重载
        Top(S,&x);
        EnQueue(Q,x);
        Pop(S);
    }
    while(!IsEmpty(Q)){  //函数重载
        Front(Q,&x);
        Push(S,x);
        DeQueue(Q);
    }
}



int main(){
    int n,i,x;
    Stack S;
    Queue Q;
    scanf("%d",&n);
    // printf("\n");
    Create1(&S,n);
    Create2(&Q,n+1);  // 防止出现空队列，满队列的情况
    for(i=0;i<n;i++){
        scanf("%d",&x);
        Push(&S,x);
    }
    // Output(&S,n);
    Inverse(&S,&Q);
    //Output(&S,n);
    PrintStack(&S);
    return 0;
}

实验结果

将 2 3 1 5 4 依次入栈，然后利用队列进行逆置，最后输出新栈的元素，是从 top 开始打印的。