剑指offer之两个队列实现栈的问题 / 开普饭

1 问题

两个队列实现栈的插入和获取头部元素的功能

2 分析

1）获取头部元素的功能分析：

我们有2个队列，我们知道队列的特点的先进先出，而栈的特点是先进后出，比如我们有数据1,2,3,4,我们分别依次压入队列1，队列2目前是空，我们需要有栈的效果，加上队列2也是先进先出的特点，意味着我们队列2里面的数据依次是4,3,2,1入队列2，现在问题转成了我们怎么操作队列1里面的数据让它依次弹出4,3,2,1入队列2

接下来我们分析怎么操作队列1里面的数据让它依次弹出4,3,2,1入队列2

我们知道队列1数据进去的时候是1,2,3,4.我们需要得到4，我们可front()得到进入队列的第一个元素，然后push到队列1，然后执行pop()函数，那么队列1就变成了2,3,4,1, 同理我们也这样操作，知道元素4在队列的最头部，队列1也就变成了3,2,1,4，我们把4弹出来压入到队列2里面去，然后队列1的数据是3,2,1，我们依然按照上面的方法，把3弹出来压入队列2，最后队列2就入队列的元素依次是4,3,2,1 再把队列2弹出头部元素，就是我们栈获取头部元素的效果。

2）插入元素的功能分析：

如果队列2不为空的情况下，我们需要先把队列2里面的元素一一弹出来放到(push)队列1里面去，确保队列2是空的之后，然后再把新的元素push到队列的1的尾巴

如果队列2为空的情况下，我们可以直接把新的元素push到队列1里面去就行。

3 代码实现

#include <iostream>
#include <queue>

using namespace std;

class student
{
public:
    student(){}
    ~student(){}
    student(std::string name, std::string age, std::string sex)
    {
        this->name = name;
        this->age = age;
        this->sex = sex;
    }
    void toString()
    {
        std::cout << "name is "<< name << " age is "<< age << " sex is "<< sex << std::endl;
    }
private:
    std::string name;
    std::string age;
    std::string sex;
};

template <typename T>
class Test
{
public:
    Test(){}
    ~Test(){}
    Test(const T& t);
    //往队列里面添加元素
    void add(const T& t);
    //往队列里面删除元素
    T top();
private:
    std::queue<T> queue1;
    std::queue<T> queue2;
};

template <typename T> void Test<T>::add(const T& t)
{
    if (!queue2.empty())
    {
         T& top = queue2.front();
         queue1.push(top);
         queue2.pop();
    }
    queue1.push(t);
}

template <typename T> T Test<T>::top()
{
    if (queue2.empty())
    {
        while (!queue1.empty())
        {
            int size = queue1.size();
            for (int i = 1; i < size; ++i)
            {
                T& top = queue1.front();
                queue1.push(top);
                queue1.pop();
            }
            T& value = queue1.front();
            queue2.push(value);
            queue1.pop();
        }
    }

    T top = queue2.front();
    queue2.pop();
    return top;
}
int main() {

    student std1("chenyu", "27", "man");
    student std2("chencaifeng", "27", "woman");
    student std3("chenzixuan", "3", "woman");
    student std4("chenzixi", "2", "woman");
    student std5("chenxuan", "21", "man");

    Test<student> stack;
    stack.add(std1);
    stack.add(std2);
    stack.add(std3);
    stack.add(std4);

    student top1 = stack.top();
    top1.toString();
    student top2 = stack.top();
    top2.toString();
    student top3 = stack.top();
    top3.toString();
    std::cout << "--------------------" << std::endl;
    stack.add(std5);
    student top4 = stack.top();
    top4.toString();
    student top5 = stack.top();
    top5.toString();  

return 0;
}

4 运行结果

name is chenzixi age is 2 sex is woman
name is chenzixuan age is 3 sex is woman
name is chencaifeng age is 27 sex is woman
--------------------
name is chenxuan age is 21 sex is man
name is chenyu age is 27 sex is man

如果我分析的有点问题或者哪里没有考虑到，欢迎大家指出来。

最后附加：

我的微信：

打赏博主非常感谢：

剑指offer之两个队列实现栈的问题