利用两个栈进行实现队列的入队和出队操作
题目:
解题分析:
该题目需要借助两个栈来实现队列的“入队”和“出队”,并封装好了三个对应的函数。我们需要注意的是栈的特点是“先进后出”,与队列的”先进先出“的输出并不一致。所以,我们要利用栈来输出正常排序的序列,需要借助类似取反的原理,例如 !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;
}