习题---利用两个栈实现队列的“入队”和“出队”

利用两个栈进行实现队列的入队和出队操作

题目:

解题分析:

​ 该题目需要借助两个栈来实现队列的“入队”和“出队”,并封装好了三个对应的函数。我们需要注意的是栈的特点是“先进后出",与队列的”先进先出“的输出并不一致。所以,我们要利用栈来输出正常排序的序列,需要借助类似取反的原理,例如 !false == true,而 !(!false) == false。

​ 即我们需要现将元素存入栈s1,在对其执行出栈操作,此时我们得到元素的排列顺序与初始相反。此时我们在将该元素序列存入栈s2,再次取出便能得到“先进先出”排列顺序的元素。

​ 可是要完成该“入队”操作,我们必须对当前两个栈的状态进行判断,因为两个栈的存储状态会影响到元素的排列顺序与输出顺序。大致可以将两个栈的存储状态分为三类:

  1. s1满,s2空:将s1中的元素依次出栈,在依次入栈s2。此时,s1空,在将需要“入队”的元素入栈s1,便可以得到“先进先出”顺序的元素序列

  2. s1不满,s2空:同样将s1存有的元素依次次出栈,在依次入栈s2,这样的做法可以保证s1中已经存储的元素,可以在s2中按正确的顺序排列,并且不会影响到新“入队”的元素

  3. 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;
}

热门相关:史上第一密探   战斗就变强   福慧双全   越境鬼医   伏天剑尊