使用两个栈实现队列，使用两个队列实现栈。

我是一个栈，我的双胞胎弟弟叫队列。我的爸爸是数组，我的妈妈是链表。在上一篇文章中，向你们介绍了我的家族成员对于数据存储方面的能力和特性。还包括如何通过数组和链表来实现栈和队列。

上一次的介绍中，还遗留一个问题。其实我和我的双胞胎弟弟队列之间是可以互相转换的。可以通过栈来实现队列，也可以通过队列来实现栈。这也是很多面试官喜欢问的知识点。这篇文章就来像你介绍下这个知识点。

栈的队列的特点

栈和队列都是用来保存数据的，无论底层是使用数组还是链表来实现，其基本原理是不变的，那就是栈的特点的先进后出，队列的特点是先进先出。

要想通过栈来实现队列，需要两个栈才可以。使用队列来实现栈亦然。

栈和队列，作为两个数据结构，都包含插入、删除等功能的。

栈的常用方法

• isEmpty()
  • 判断栈是否为空
• size()
  • 返回栈中元素的个数
• push()
  • 向栈中插入数据
• pop()
  • 从栈中弹出数据并返回
• peek()
  • 返回栈顶的数据

队列的常用方法

• isEmpty()
  • 判断队列是否为空
• size()
  • 返回队列中元素的个数
• enqueue()
  • 向队列中插入数据
• dequeue()
  • 从队列中弹出数据并返回
• peek()
  • 返回队列中第一个数据

本文，主要来实现栈和队列的插入和删除方法。即push()、pop()和 enqueue()、dequeue()方法。其他方法实现起来比较简单，作为思考题供大家自己实现。

使用栈来实现队列

首先我们来考虑如何使用两个栈来实现队列。队列的特点是先进后出，如果向队列中保存"hollis"的顺序是h、o、l、l、i、s，那么取出元素的数序也应该是h、o、l、l、i、s。

而对于栈来说，如果你想要让一个元素能够第一个被弹出，就要保证他永远位于栈的顶部。也就是说，如果你希望出站的顺序是h、o、l、l、i、s，那么入站顺序需要时silloh。

我们现在已经有的数据结构是栈，如果按照h、o、l、l、i、s的顺序向一个栈中保存数据的话，这些元素在栈中的顺序应该是s、i、l、l、o、h。也就是他正常的弹出顺序应该是silloh，但是我们想要的弹出顺序是hollis。 那么如何解决这个问题呢，就需要另外一个栈来配合，两个栈互相倒换。具体如何操作呢？

有一种方案是这样的：两个栈严格区分开来使用，一个专门用来做插入（插入栈），一个专门用来做弹出（弹出栈）。这样在做插入的时候什么都不需要做，直接调用插入栈的push方法就可以了。但是在弹出的时候就要麻烦一点，先判断在弹出栈中是否包含数据，如果包含，直接从顶部弹出，如果不包含，把插入栈中的元素挨个导入到弹出栈中。然后再从栈顶将第一个元素弹出。

说起来好像挺绕的，没关系。接着往下看，我们先来定义一下这个队列：

class MyQueue {
        stack<int> in;
        stack<int> out;
}

接下来，我们通过一张图来模拟下如何使用两个栈来实现队列的插入操作。

上图中可以看出来，插入还是比较简单的，只需要往插入栈中push就可以了，代码实现如下：

void push(int x) {
    in.push(x);
}

插入的时候简单了，那么弹出的时候可能就要经过一番操作了。再来一张图，看看如何使用两个栈来实现队列的弹出操作。 简单介绍下过程：队列中原有三个数据，插入顺序是HOL，进行以下三个操作：1、弹出H，2、插入L，3、弹出O。

从上面的图中可以看到，当我们尝试弹出H的时候，由于stack-out为空，需要把stack-in栈中的数据pop出来，并push进入stack-out，然后再从stack-out的栈顶就能直接弹出H了。 当我们尝试弹出O的时候，因为stack-out中包含数据，那么就直接从stack-out中往外弹数据就可以了。

代码实现如下：

int pop() {
    if (!out.empty()) {
        int temp = out.top();
        out.pop();
        return temp;
    }
    else {
        if (in.empty()) {
            return -1;
        }
        else {
            while (!in.empty()) {
                out.push(in.top());
                in.pop();
            }
            int temp = out.top();
            out.pop();
            return temp;
        }
    }
}

使用队列来实现栈

上面的队列实现中。插入方法并没有额外的操作，只是在弹出的时候需要做些额度的处理。那么另外一个思路就是在插入的时候做些事情，这样在弹出的时候就可以无须额外操作直接弹出了。同样，还是需要两个队列来实现栈。具体如何操作呢？

先来定义一下这个栈：

class MyStack {
    queue<int> a;
    queue<int> b;
}

还是通过一张图，看下使用队列实现的栈是如何进行元素的插入的。

从上图中可以看出，用来实现栈的两个队列是不区分用途的，也就是说两个队列都具备插入和弹出的功能。之所以可以这么做的原因就是，他要保证任何时候都只有一个队列中有元素。

上图的插入操作，插入H的时候，两个队列都为空，优先选择从queue1插入。 当想要插入O的时候，由于queue1中已经包含了数据，那么就讲O插入queue2中，然后再将queue1中的数据依次插入queue2。实现代码如下：

void push(int x) {
    if (a.empty() && b.empty()) {
        a.push(x);
        return;
    }
    if (a.empty()) {
        a.push(x);
        while (!b.empty()) {
            a.push(b.front());
            b.pop();
        }
    }
    else {
        b.push(x);
        while (!a.empty()) {
            b.push(a.front());
            a.pop();
        }
    }
}

再来一张图，看看如何使用两个队列来实现栈的弹出操作。

由于我们在插入的时候，保证了两个队列中只有一个队列包含数据，并且数据的顺序已经调整好了（包含数据的那个队列的队列头就是整个栈的栈顶），那么就直接从有数据的那个队列中往外弹数据就可以了。实现代码如下：

int pop() {
    if (a.empty()) {
        int temp = b.front();
        b.pop();
        return temp;
    }
    else {
        int temp = a.front();
        a.pop();
        return temp;
    }
}

好了，至此，我们已经完成了使用两个栈实现队列和两个队列实现栈的功能的介绍。总结一下，主要有两种方案。拿通过栈来实现队列举例。

方案一：定义两个栈，一个专门用来插入，一个专门用来弹出。插入操作只会插入到插入栈。弹出的时候，优先从弹出栈往外弹，如果弹出栈中的内容为空，那么就将插入栈中的数据依次弹出，并压入弹出栈，然后再弹出。

方案二：定义两个栈，不区分作用，但是有一个原则就是始终要保证其中一个栈为空。每次插入的时候先将待插入数据直接插入到空的栈中，然后再将另外一个栈中的数据依次弹出，并压入这个刚刚插入新数据的栈中。弹出的时候，只要从那个有数据的栈中往外弹数据就可以了。

无论以上哪种方案，其实根本原理都是和我们小时候玩的汉诺塔游戏差不多。