亲宝软件园·资讯

展开

用栈+队列实现队列中的元素逆置

MyDreamingCode 人气:0

下面举例代码:

提到的Q是一个队列,S是一个空栈,实现将队列中的元素逆置的算法

#include<stdio.h>
#define MaxSize 10
typedef int ElemType;
typedef struct{
    ElemType data[MaxSize];
    int front,rear;
}Queue;
typedef struct{
    ElemType data[MaxSize];
    int top;
}SqStack;
 
void InitStack(SqStack &S) //初始化栈
{
    S.top = -1;
}
 
bool EmptyStack(SqStack S) //判断栈空
{
    if(S.top == -1)
        return true;
    else
        return false;
}
 
bool OverflowStack(SqStack S) //判断栈是否满
{
    if(S.top == MaxSize-1)
        return true;
    else
        return false;
}
 
bool Push(SqStack &S,ElemType x) //进栈
{
    if(OverflowStack(S))
        return false;
    S.data[++S.top] = x;
    return true;
}
 
bool Pop(SqStack &S,ElemType &x) //出栈
{
    if(EmptyStack(S))
        return false;
    x = S.data[S.top--];
    return true;
}
 
void InitQueue(Queue &Q) //初始化队列
{
    Q.front = Q.rear = 0;
}
 
bool IsEmpty(Queue Q) //判断队列是否为空
{
    if(Q.front == Q.rear)
        return true;
    else
        return false;
}
 
bool IsOverflow(Queue Q) //判断队列是否满
{
    if((Q.rear+1)%MaxSize == Q.front)
        return true;
    else
        return false;
}
 
bool EnQueue(Queue &Q,ElemType x) //进队列
{
    if(IsOverflow(Q))
        return false;
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear+1)%MaxSize;
    return true;
}
 
bool DeQueue(Queue &Q,ElemType &x) //出队列
{
    if(IsEmpty(Q))
        return false;
    x = Q.data[Q.front];
    Q.front = (Q.front+1)%MaxSize;
    return true;
}
 
bool ReverseQueue(Queue &Q) 
{
    SqStack S;
    ElemType x;
    InitStack(S);
    while(!IsEmpty(Q)) //当队列不为空时,将队列中的元素依次放入栈中
    {
        DeQueue(Q,x);
        Push(S,x);
    }
    while(!EmptyStack(S)) //当栈不为空时,再将栈中元素依次放入队列中
    {
        Pop(S,x);
        EnQueue(Q,x);
    }
    return true;
}
 
void main()
{
    Queue Q;
    InitQueue(Q);
    EnQueue(Q,1);
    EnQueue(Q,2);
    EnQueue(Q,3);
    ReverseQueue(Q);
    printf("%d ",Q.data[Q.front]);
}

(根据主函数中代码)演示:

例如一开始队列中元素为3 2 1 ->出

1. 将队列中元素依次放到栈中,此时栈:1 2 3 ->出

2. 再将栈中的元素依次放入队列中,此时队列:1 2 3 ->出 

加载全部内容

相关教程
猜你喜欢
用户评论