【原】剑指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