用两个栈实现一个队列

用两个栈实现一个队列

• 栈的特性：后进先出，只能在一端进栈和出栈
• 队列的特性：先进先出，只能在一端进行入队，在另一端出队

//队列：先进先出  栈：后进先出  利用栈s1和s2实现队列，可以选择把栈s1作为入队缓存，把栈s2作为出队缓存
/*  1.s1未满 s2未满  可以入栈
    2.s1已满 s2空  可以入栈
    3.s1已满 s2未满或者满  不可以入栈



*/
//入队
bool enQueue(s1,s2,int x)
{
    int temp=0;
    if(s1->Top+1>=s1->maxSize)//如果s1栈已满
    {
        //说明栈s1已满，此时分为两种情况（栈s2空 or 栈s2不空）
		if ( isEmpty(s2) )//栈s2为空时
        {
            while(!isEmpty(s1))
            {
                pop(s1,&temp);//s1中元素出栈
                push(s2,temp);//s2中元素进栈
            }
            push(s1,x);

        }
        else//s2不为空时
        {
            return false;
        }
    }
    else//s1没满
    {
        push(s1,x);//新加入的元素直接进栈
    }
    return true;
}

//判断队列是否为空
int isQueueEmpty(s1,s2)
{
    //return (s1->Top=s1->Bottom&&s2->Top=s2->Bottom)?true:false;
    if (isEmpty(s1) && isEmpty(s2))
	{
		return 1;
	}
	else
		return 0;
}

//出队
bool enQueue(s1,s2,&x)
{
    //判断队列是否空，如果为空就无法出队
    if(isQueueEmpty(s1,s2))
    {
        return false;
    }
    //此时有两种情况，s2不为空时 和s2为空时
    if(!isEmpty(s2))
    {
        pop(s2,&x);//x直接出栈
    }
    else
	{
		//说明栈s2为空，此时需要把栈s1的元素依次出栈到s2中
		while( ! isEmpty(s1) )
		{
			pop(s1,&temp); //把出栈元素暂时存储在temp中
			push(s2,temp); //把变量temp中的元素入栈到s2
		}

		pop(s2,&x);
	}
    return true;
}