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

1 问题

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

2 分析

我们定义连个栈stack1，stack2，当队列弹出头部元素的时候，我们知道队列先进后出，我们先把一个元素压到stack1,然后再压一个元素到stack1,然后我们把stack1的top函数得到栈顶值然后pop弹出来，push到stack2里面去，这个时候后面进的元素就在stack2的栈底，然后我们再把stack1的top函数得到栈顶值然后pop弹出来，push到stack2里面去,这个时候我们stack2的top()栈顶函数也就是我们第一个压到stack1的元素，我们只需要把stack2的top()的值获取就是队列的第一个元素。

简言之

队列获取头部元素的功能：如果stack2里面没有元素，我们需要把stack1里面的元素从栈顶一个一个弹出来压入到stack2，当获取队列的头部值的时候，我们只需要获取stack2的顶部元素值（top方法）就行，然后把这个值pop出来，如果stack2里面有元素，我们直接获取stack2的顶部元素值（top方法）就行，然后把这个值pop出来。

插入队列元素的功能，我们只需要把元素直接push到stack1里面就行，不管stack2里面有没有值。


 
3 代码实现

    #include <iostream>
    #include <stack>
     
    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::stack<T> stack1;
        std::stack<T> stack2;
    };
     
    template <typename T> void Test<T>::add(const T& t)
    {
        stack1.push(t);
    }
     
    template <typename T> T Test<T>::top()
    {
        if (stack2.empty())
        {
            //注意这里是while 不是if，我们需要把stack1里面的数据全部弹出来放到stack2里面去
            while (!stack1.empty())
            {
                T& value = stack1.top();
                stack1.pop();
                stack2.push(value);
            }
        }
        
        T top = stack2.top();
        stack2.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", "woman");
        
        Test<student> queue;
        queue.add(std1);
        queue.add(std2);
        queue.add(std3);
        queue.add(std4);
        
        student top1 = queue.top();
        top1.toString();
        student top2 = queue.top();
        top2.toString();
        student top3 = queue.top();
        top3.toString();
        
        queue.add(std5);
        student top4 = queue.top();
        top4.toString();
        student top5 = queue.top();
        top5.toString();  
     
        return 0;
    }


 
4 运行结果

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

 



 



 

作者：chen.yu
深信服三年半工作经验，目前就职游戏厂商，希望能和大家交流和学习,
微信公众号：编程入门到秃头 或扫描下面二维码
零基础入门进阶人工智能(链接)