习题---利用两个栈实现队列的“入队”和“出队”
利用两个栈进行实现队列的入队和出队操作
题目：
解题分析：
该题目需要借助两个栈来实现队列的“入队”和“出队”，并封装好了三个对应的函数。我们需要注意的是栈的特点是“先进后出",与队列的”先进先出“的输出并不一致。所以，我们要利用栈来输出正常排序的序列，需要借助类似取反的原理，例如 ！false == true，而 ！（！false） == false。
即我们需要现将元素存入栈s1，在对其执行出栈操作，此时我们得到元素的排列顺序与初始相反。此时我们在将该元素序列存入栈s2，再次取出便能得到“先进先出”排列顺序的元素。
可是要完成该“入队”操作，我们必须对当前两个栈的状态进行判断，因为两个栈的存储状态会影响到元素的排列顺序与输出顺序。大致可以将两个栈的存储状态分为三类：
-
s1满，s2空：将s1中的元素依次出栈，在依次入栈s2。此时，s1空，在将需要“入队”的元素入栈s1，便可以得到“先进先出”顺序的元素序列
-
s1不满，s2空：同样将s1存有的元素依次次出栈，在依次入栈s2，这样的做法可以保证s1中已经存储的元素，可以在s2中按正确的顺序排列，并且不会影响到新“入队”的元素
-
s1满，s2不空：此时无法进行入队操作
从上面的分析情况可得，当s1中存在元素时，s2必须为空，否则无法执行“入队”操作。
原因分析：当s2不空的时候，s2中的元素是按“先进先出”的顺序进行排列的，此时若是将s1中的元素依次出栈，再依次入栈到s2中的话，会导致无法实现“先进先出”特点的输出。例如：
我们想要输出a b c d e f的队列;
此时 s2中存储的是 a b c ,其中a为栈顶 ，且符合不空的情况;
s1按 e d c 存储，且e为栈顶，且符合不满的情况；
则此时对s1依次出栈，再依次出栈至s2的操作后;
s2的存储情况变更为： d e f a b c 如下图所示：
此时我们可以看出，s1中的元素排列顺序是正确的，s2中原本的元素排列顺序也是正确的。但是，此时对s2执行“出队”的操作后，我们得到的队列就是错的。所以我们需要再执行“入队”的操作前，保证s2是为空的状态
代码实现：
- “入队”算法
//入队
bool enQueue(s1,s2,int x)
{
int temp; //用于存储出栈的元素的值
//1.判断栈s1是否已满，此时分为两种情况(满了 or 未满)
if (s1->top + 1 >= maxSize)
{
//说明栈s1已满，此时分为两种情况（栈s2空 or 栈s2不空）
if ( isEmpty(s2) )
{
//此时栈s2为空，所以需要把栈s1的元素依次出栈到s2中
while( ! isEmpty(s1) )
{
pop(s1,&temp); //把出栈元素暂时存储在temp中
push(s2,temp); //把变量temp中的元素入栈到s2
}
push(s1,x); //此时栈s1为空，所以可以把元素x入栈到s1
return true;
}
else
{
//此时栈s2不空，所以无法入队
return false;
}
}
else
{
//此时栈s1未满，所以可以把元素x入栈到s1中
push(s1,x);
}
return true;
}
- "出队"算法
//出队
bool enQueue(s1,s2,&x)
{
int temp; //为了存储出栈的元素
//1.判断队列是否为空，此时分为两种情况（空 or 不空）
if (isQueueEmpty(s1,s2))
{
return false;
}
else
{
//说明队列不空，此时又分为两种情况（栈s2空 or 栈s2不空）
if ( !isEmpty(s2) )
{
//说明栈s2不空，则直接把元素出栈
pop(s2,&x);
}
else
{
//说明栈s2为空，此时需要把栈s1的元素依次出栈到s2中
while( ! isEmpty(s1) )
{
pop(s1,&temp); //把出栈元素暂时存储在temp中
push(s2,temp); //把变量temp中的元素入栈到s2
}
pop(s2,&x);
}
}
return true;
}
- "判断队列为空"算法
//判断队列为空
int isQueueEmpty(s1,s2)
{
if (isEmpty(s1) && isEmpty(s2))
{
return 1;
}
else
return 0;
}