栈的经典面试题之用两个栈实现一个队列

拿到这种问题，我们首先应该思考这两种结构的特性是什么，为什么会出这样的题。其实就说明这两者的特性是有某种联系的，这么想的话其实很简单，栈的最大特点就是先进后出，让我们用两个先进后出的栈来实现一个先进先出的队列，那么我们把数据压入第一个栈，此时我们很清楚它的出战顺序是与我们想要的队列的出队顺序是相反的，如果再把这个栈里面的元素依次压入第二个栈，此时我们想想栈2里面的元素的顺序，相当于对一组数据进行了两次倒序，此时对第二个栈进行的出栈操作的顺序就相当于这组数据进入队列的顺序了。

上面这段话是对思路的一个详细分析，但是是比较啰嗦的，大家完全可以通过思考就能想明白而不必要看它，当然你也可以凑合瞅瞅，缕缕思路。可以看看下面的图，假设现在入队的元素是1,2,3,4，那么入队之后处在队头的元素为1，队尾为4，那么我们想要通过s1和s2实现这样的队列。

接下来才是重点所在，我们要用这两个栈来实现一个队列，那么需要写出队列中的几个基本操作函数，如下所示：

push和pop函数：

我们来看一下比较重要的push和pop操作，可以这么来想，当有数据要入队的时候，我们就让它压入stack1，要进行pop操作的时候，我们就把stack1里面的数据全部压入stack2中，然后对stack进行一次pop操作就可以了，因为此时stack的栈顶就相当于队列的最先进来的数据（当然在pop操作里需要先判断两个栈是否都为空，而且当stack2不为空的话就可以直接进行stack2.pop，stack2为空但是stack1不为空在进行上面的操作）。

再来看看上面的图：我们就把1,2,3,4压入s1中，当pop操作的时候，我们就把s1的元素都压入到s2中，然后对s2进行pop操作就相当于对队列的pop了。

void push(const T& data)
    {
        s1.push(data);
    }
    void pop
    {
        if (s1.empty && s2.empty)
        {
 cout << "The queue is empty";
        }
        if (!s2.empty)
        {
 s2.pop;
        }
        else
        {
 while (!s1.empty)
 { 
 s2.push(s1.top);
 s1.pop;
 }
        }
    }

看代码，是否觉得很简单。

front和back函数：

再来看看它的front和back函数，前面也有提到，这个队列的front就是stack2的栈顶元素，只要stack2不为空我们返回stack2的栈顶就可以，为空的话还是像之前一样，我们把stack1的所有数据全部压入stack2中再取栈顶。那么back取队尾的操作如何实现呢，我们先来想想我么实现的这个队列的队尾在哪里。

看下图，情况一是当我的stack1的数据还没有压入stack2中的时候，stack1中的栈顶元素是最后一个压入stack1的，也就相当于队列的队尾啊是不是，那么在stack1不为空的情况下只需要返回stack1的栈顶元素即s1.top。情况二中是stack1为空，那么此时的队尾应该是stack2的栈底，这样的话我们又需要把stack2的元素全部压入到s1中，stack2的栈底也就成了stack1的栈顶，再返回stack1

的栈顶就行。 其实还有一种是stack1和stack2都不为空的情况，这其实和情况一一个道理，直接返回s1.top就OK.

T& Front
    {
        assert(!s1.empty || !s2.empty);
        if (s2.empty)
        {
 while (!s1.empty)
 {
 s2.push(s1.top);
 s1.pop;
 }
        }
        return s2.top;
    }
    T& Back
    {
        assert(!s1.empty || !s2.empty);
        if (s1.empty )
        {
 while (!s2.empty)
 {
 s1.push(s2.top);
 s2.pop;
 }
        }
        return s1.top;
    }

empty和size：

最后看看最简单的empty和size函数，判断队列是否empty的话，那就是判断我们用的两个栈是否都为空，如果s1和s2都为空的话就返回true，否则返回false。size函数及返回两个栈的size之和。

最后附上本人的整体代码，欢迎指正：

 1 #include<stack>
 2 template<typename T>
 3 class QueueBy2Stack
 4 {
 5 public:
 6 
 7     void push(const T& data)
 8     {
 9         s1.push(data);
10     }
11     void pop
12     {
13         if (s1.empty && s2.empty)
14         {
15 cout << "The queue is empty";
16         }
17         if (!s2.empty)
18         {
19  s2.pop;
20         }
21         else
22         {
23 while (!s1.empty)
24  { 
25  s2.push(s1.top);
26  s1.pop;
27  }
28  s2.pop;
29         }
30     }
31     T& Front
32     {
33         assert(!s1.empty || !s2.empty);
34         if (s2.empty)
35         {
36 while (!s1.empty)
37  {
38  s2.push(s1.top);
39  s1.pop;
40  }
41         }
42         return s2.top;
43     }
44     T& Back
45     {
46         assert(!s1.empty || !s2.empty);
47         if (s1.empty )
48         {
49 while (!s2.empty)
50  {
51  s1.push(s2.top);
52  s2.pop;
53  }
54         }
55         return s1.top;
56     }
57     size_t size
58     {
59         return s1.size + s2.size;
60     }
61     bool empty
62     {
63         if (s1.empty && s2.empty)
64         {
65 return true;
66         }
67         return false;
68     }
69 private:
70     stack<T> s1;
71     stack<T> s2;
72 };

文章作者：Mr_listening。 博客地址：
http://www.cnblogs.com/MrListening/