剑指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
赞 (0)