栈和队列的应用

     ”栈和队列“这方面的面试题是挺多的，栈和队列之间的应用也是面试中常常会见到的问题，下面我们就来讨论以下的这两个问题：

1）两个栈实现一个队列

2）两个队列实现一个栈

问题一：

       栈最主要的特点就是“先进后出”，而队列的特点是“先进先出”。那么我们应该怎样用两个栈实现一个队列？给定两个栈s1和s2，s1只用于插入数据，当s2和s1中都没有数据时，则队列为空。若s1中有数据，s2中没有数据，则将s1中的数据进行出栈，将每个出栈的数据压入s2中，在s2中进行pop栈顶上的数据，则实现了队的“先进先出”的特点。若s2中有元素，s1中有数据，这种情况下也是在s2中进行删除数据，直到s2中数据为空，再重复上面s1中有数据，s2中没有数据的情况。根据这种方式，则用两个栈就能够实现队列的功能。在面试中，一般由于时间的关系，可以实现主要的功能，即push和pop。

下面为简单的图示：

下面为两个栈实现队列的程序代码：

//使用两个栈实现队列#include 
     
      using namespace std;#include 
      
       #include 
       
        template 
        
         class SetQueue{public:     void appendTail(const T& node)        //尾插     {         s1.push(node);    //插入压入栈S1     }          T deleteHead()      //头删     {          if (s2.size() == 0)      //当          {               while (s1.size() > 0)                   {                    s2.push(s1.top());                          s1.pop();               }          }          if (s2.size() == 0)      //证明S1和S2中都没有元素          {               cout << "The Queue is empty；" << endl;          }          T head = s2.top();                 //s2非空的情况          s2.pop();       //头删节点          return head;     }         void Display()     //打印     {          if (s2.empty())          {               if (s1.empty())               {                    cout << "The Queue is empty!" << endl;               }               else               {                    while (!s1.empty())                    {                         T tmp = s1.top();                         s2.push(tmp);                         s1.pop();                    }                    while (!s2.empty())                    {                         cout << s2.top() << endl;                         s2.pop();                    }               }          }          else          {               if (s1.empty())               {                    while (!s2.empty())                    {                         cout << s2.top() << endl;                         s2.pop();                    }               }               else               {                    while (!s2.empty())                    {                         cout << s2.top() << endl;                         s2.pop();                    }                    while (!s1.empty())                    {                         T tmp = s1.top();                         s2.push(tmp);                         s1.pop();                    }                    while (!s2.empty())                    {                         cout << s2.top() << endl;                         s2.pop();                    }               }          }     }     private:     stack
         
           s1;     stack
          
            s2;};
          
         
        
       
      
     

问题二：两个队列实现一个栈

         给定两个队列Q1和Q2，需要一个栈的功能，Q1主要是用来插入数据，对于删除操作，需要看情况来决定。当Q1中有数据，而Q2中没有数据的情况下，将Q1中的数据出队，同时插入对Q2中，直到Q1中剩下一个元素，这时将Q1中的数据pop，但是不用将其插入Q2中，再次进行pop数据时，再将Q2中的数据pop，并插入到Q1中，直到最后一个数据，将其进行删除。当Q1、Q2中都有数据时，先将Q2中的数据按照上面的方式，将Q2中的数据pop，并插入到Q1中，同时删除Q2中的数据，这时就转变为Q1中有数据，Q2中没有数据的情况。

下面为简单的操作图示：

下面为两个队列实现栈的程序代码：

//两个队列实现一个栈#include 
     
      using namespace std;#include 
      
       #include 
       
        template 
        
         class Stack{public:     void PushBack(const T& x)    // 压栈     {          Q1.push(x);     //将数据都压入Q1中     }          void PopBack()      //出栈     {          if (!Q1.empty())          {               while (!Q1.empty())               {                    T tmp = Q1.front();                    Q1.pop();                    if (!Q1.empty())                    {                         Q2.push(tmp);                    }               }          }          else          {               if (!Q2.empty())               {                    while (!Q2.empty())                    {                         T cur = Q2.front();                         Q2.pop();                         if (!Q2.empty())                         {                              Q1.push(cur);                         }                    }               }          }     }          bool empty()     //判断栈为空     {          return Q1.empty() && Q2.empty();     }          T& Top()        //读栈顶元素     {          T tmp = NULL;          if (!Q1.empty())          {               tmp = Q1.back();          }          else          {               if (!Q2.empty())               {                    tmp = Q2.back();               }          }          return tmp;     }  protected:     queue
         
           Q1;     queue
          
            Q2;};