最近看了个面试的帖子讲的是“怎么用两个栈来实现队列的操作”，好奇的我也想试下这道题目，咋一看这道题目挺简单的呀，嗯，确实不难。先简单讲下我第一眼看到这个题目时想到的解法。讲解法之前先给大家讲下数据结构中的栈和队列吧，免得有的人不明白栈和队列，那就没办法继续看下去了。
栈(stack)(wiki)
我们经常会在面试中听到“栈”这个词语，理解这个概念对于理解程序的运行至关重要。栈这个词语在不同的语境中表达的含义是不同的。下面我将解释下栈的三种含义（参考：《Stack的三种含义》）。
-
含义一：数据结构
我们这里讲的其实就是这种含义，stack是一种存储数据的结构，特点是LIFO，即后进先出（last in First out）。
这种数据结构其底层是用链表来现实的，最大特点是只能操作最上面的元素，所以先进栈的被压在下面只能后出栈。
这种数据结构通常又下面几种方法来操作最上面的元素：
push : 进栈
pop ： 出栈
top ： 获取栈顶元素
empty ：判断栈是否为空
-
含义二：代码的运行方式
stack的第二种含义是“调用栈“，表示函数像积木一样的堆放，以供层层调用，我们在函数中的递归就是用堆栈实现的，递归简单点来说就是函数中调用该函数。
-
含义三：内存区域
stack的第三种含义就是存储数据的一种内存区域。程序在运行时需要一定的空间来存储数据。一般来说系统会划分出两种不同的内存空间，一种是栈（stack），另一种是堆（heap）。
栈是由操作系统自动分配和释放的，存放函数的参数值，局部变量值等。堆一般由程序员分配并释放，若程序员不释放，程序结束时可能由OS回收，分配方式类似于链表。我们经常讲的内存泄漏其实就是指的就是堆。
介绍完了栈的定义，简单说下栈和队列的区别吧，栈的特点是先进的后出，队列的特点是先进的先出。这道题目考查的重点还是对于栈和队列特性的理解，其次再加上一些思考就好了。
看完这道题目我其实第一反应就觉得这道题挺简单的，新建两个栈s1、s2，然后当有入栈请求的时候先将s1栈中的数据依次出栈进入到s2的栈中，然后将新请求入栈的数据放入s1中，最后将s2栈中数据依次出栈进入到s1栈中。每次有出栈请求的时候将s1栈中的数据出栈就好了。这种解法应该是比较常规的解法，也比较容易想到的。
但是仔细想下这种方法效率比较低，有频繁的出栈和入栈操作，对于性能的影响比较大，那有没有什么更好的方法能解决这个问题呢？其实我们可以在出栈的时候把栈底元素取出来，入栈的时候正常入栈。具体实现就是当有入栈请求的时候将数据压入栈s1，当有出栈请求的时候将s1数据依次出栈压入s2栈中，那么这时s2的栈顶元素就是s1的栈底元素，最后将s2的数据又依次压入s1中。这么这样的话就只有出栈的操作会有频繁的栈操作，对于入栈来讲没有额外的栈操作。这种方法其实效率已经非常高了。
其实还有一种效率更高的方法来解决这个问题，仔细想下这么问题，将上面的解法做个优化，将s1栈中的数据依次压入s2中后又依次压入s1中，那为什么又要将s2中的数据重新压回s1呢？其实这步操作可以避免，我们可以当有入栈的操作时将数据压入s1，当有出栈操作时将s2中的数据出栈，若s2栈为空，则将s1中的数据全部依次压入s2中，这样的方法效率会比上面的方法更优。
下面的代码就是上面提到的最后一种方法的实现：
#include <iostream>
#include <cstdio>
#include <stack>
#include <algorithm>
using namespace std;
std::stack<int>s1, s2;
int main()
{
printf("Please input argument：1 push，2 pop\n");
int operation, num;
while(scanf("%d", &operation) != EOF)
{
if(operation == 1)
{
printf("please input queue push num:");
scanf("%d", &num);
s1.push(num);
}
else if(operation ==2)
{
if(!s2.empty())
{
printf("Queue pop num: %d\n", s2.top());
s2.pop();
}
else if(!s1.empty())
{
while(!s1.empty())
{
s2.push(s1.top());
s1.pop();
}
printf("Queue pop num: %d\n", s2.top());
s2.pop();
}
else
{
printf("queue empty\n");
}
}
else
{
printf("Input invalid, please input repeat");
}
}
return 0;
}
