百度笔试题：用堆栈模拟队列功能

有这样一道百度笔试题：

请使用堆栈（Stack）来模拟队列（FIFO）功能，要求数据必须储存在堆栈内部。需要实现enqueue（入队）、dequeue（出队）、isEmpty（判空）3个功能。

【解   析】 如 图1 所示，用栈 S1 和 S2 来模拟队列。

 
     S1                    S2

假定输出序列为 Y ，对于 n 个元素的输入序列 X ，若按照如下过程进行操作：

①X中元素按序全部顺序进入S1中；

②依次将S1中元素出栈并压入S2栈中，直到S1栈空为止；

③依次将S2中元素出栈并送输出序列Y，直到S2栈空为止。

则输出序列的顺序与输入序列X完全相同，符合队列先进先出的特点。进一步分析可知，若将X从左向右分成若干段，按从左到右的顺序对每个段作上述操作，亦可得到同样的结果。所以，用两个栈模拟队列三个功能的操作过程可描述如下：

① enqueue（入队）：入队元素直接放入S1栈中（Push）。

② dequeue（出队）：若S2栈不为空，则取S2栈的栈顶元素（Pop）作为出队元素；否则将栈S1中元素全部搬到S2中，再取S2栈的栈顶元素（Pop）作为出队元素（这可视为将入队元素分段地通过S1和S2栈）。

③ isEmpty（判空）：若S1和S2两个栈均为空，则队列为空；否则不为空。

【参考程序】

Stack  *S1, *S2;   // S1和S2是两个栈

int  QIsEmpty ( )   // 判队空

{     if( IsEmpty ( S1 ) && IsEmpty ( S2 ) )  return 1;     //IsEmpty是判栈空的函数

      else return 0;

}

void  EnQueue ( int n )   // 入队

{     Push( S1, n );

}

int  DeQueue ( )             //出队

{     if( IsEmpty ( S2 ) ) {

               while( !IsEmpty ( S1 ) ) {

                         Push( S2, Pop( S1 ) );

               }

      }

      if( IsEmpty ( S2 ) )  return -1;

      else return  Pop ( S2 );

}

栈的定义及操作实现的参考代码如下所示。

typedef struct Node

{     int data;

      structNode  *next;

} Node, Stack;

Stack *CreateStack ( )

{     Node *p, *x;

      x= ( Node * ) malloc ( sizeof ( Node ));

      x->data= 0;

      x->next= NULL;

      p= x;

      return p;

}

int  IsEmpty ( Stack  *S )

{     if( S->next != NULL )  return  0;

      else return  1;

}

void  Push ( Stack  *S,  int n )

{     Node *x;

      x= ( Node * ) malloc ( sizeof ( Node ));

      x->data= n;

      x->next= S->next;

      S->next= x;

}

int  GetTop ( Stack  *S )

{     if( !IsEmpty ( S ))  return  S->next->data;

      else return  0;

}

int  Pop ( Stack  *S )

{     Node *p;

      if( !IsEmpty ( S )) {

               p= S->next;

               S->next= S->next->next;

               return p->data;

               }

      else

               return 0;

}

【拓  展】修改本题的已知条件，使用两个队列来模拟一个栈，队列的容量足够大，该如何解决呢？

设用来模拟栈s的队列是q1和q2。队列和栈的操作如表1所示。

表1队列和栈的操作

	操作	函数名	含义
队列	入队	enqueue( q, x )	元素x入队q中
	出队	dequeue( q )	从q中出队一个元素
	判空	IsEmpty( q )	判断队q是否为空
栈	入栈	push(  s, x )	元素x入栈s中
	出栈	pop(  s )	从s中出栈一个元素
	判空	IsEmpty( s )	判断栈s是否为空

使用伪代码描述栈s的操作如下：

push ( s, x )

{     enqueue( q1, x );    // q1为主队列，q2为辅助队列

}

pop ( s )

{     while(!IsEmpty ( q1 ))

      {        y = dequeue ( q1 );

               if  ( !IsEmpty ( q1 ))

                         enqueue( q2, y );  

   // 队列q1中的元素入队列q2中

               else      // y是队列q1中最后入队的元素

               {        while ( !IsEmpty ( q2 ) )

                               enqueue( q1, dequeue ( q2 )); 

// 将q2中的所有元素写回q1中

                         returny;

               ｝

      ｝

}

IsEmpty ( s )

{     return  ( IsEmpty ( q1 ));

}

每当要从栈s中出栈一个元素时，都要将队列q1中的所有元素（除最后入队元素外）移至辅助队列q2中。然后将q1中的最后一个元素出队作为出栈元素。出栈后，还要将元素从q2中移回q1中。时间开销很大。

可以增加一个奇偶标志flag以避免元素的过多移动。两个队列轮流当主队列及辅助队列。只需在出栈前将元素从一个队列移到另一个队列，出栈后不需要再将元素移回。但由于保存元素的队列是变化的，故根据flag值来判定当前操作是对q1进行的，还是对q2进行的。

本文已收录于《横扫Offer--程序员招聘真题详解700题》一书，开点工作室著，清华大学出版社，该书目前已编写修改完成，7月即将上市。更多程序员笔试面试真题的精彩详解请参见该书。