1.
龙港网站建设公司创新互联公司,龙港网站设计制作，有大型网站制作公司丰富经验。已为龙港1000多家提供企业网站建设服务。企业网站搭建\外贸网站建设要多少钱，请找那个售后服务好的龙港做网站的公司定做！
//使用两个队列实现一个栈,优化版（1.入栈只如q1,出栈将q1数据倒q2，删掉刚进来的，
//若q1无数据，从q2倒,删q2中最后一个数据2.只保证一个栈中有数据，简单，易理解）
//第一种实现
template
class Stack
{
public:
bool Empty()
{
return _q1.empty() && _q2.empty();
}
void Push(const T& x)
{
_q1.push(x);
}
void Pop()
{
assert((!_q1.empty()) || (!_q2.empty()));
if (_q1.empty())
{
while (_q2.size()!= 1)
{
_q1.push(_q2.front());
_q2.pop();
}
_q2.pop();
}
else
{
while (_q1.size()!= 1)
{
_q2.push(_q1.front());
_q1.pop();
}
_q1.pop();
}
}
int Size()
{
return _q1.size() + _q2.size();
}
//先取_q1的back,若_q1为空，再取_q2的值
T& Top()
{
assert((!_q1.empty()) || (!_q2.empty()));
if (!_q1.empty())
return _q1.back();
else
return _q2.back();
}
protected:
queue _q1;
queue _q2;
};
2.
//第二种实现
template
class Stack
{
public:
void Push(const T& x)
{
if (!_q2.empty())
_q2.push(x);
else
_q1.push(x);
}
void Pop()
{
if (!_q1.empty())
{
while (_q1.size() != 1)
{
_q2.push(_q1.front());
_q1.pop();
}
_q1.pop();
}
else
{
while (_q2.size() != 1)
{
_q1.push(_q2.front());
_q2.pop();
}
_q2.pop();
}
}
T& Top()
{
if (!_q1.empty())
{
return _q1.back();
}
else
return _q2.back();
}
protected:
queue _q1;
queue _q2;
};
void Test1()
{
Stack s1;
s1.Push(1);
s1.Push(2);
s1.Push(3);
s1.Push(4);
s1.Push(5);
s1.Pop();
cout << s1.Top() << endl;
s1.Pop();
cout << s1.Top() << endl;
//cout << s1.Size() << endl;
s1.Push(6);
cout << s1.Top() << endl;
s1.Pop();
cout << s1.Top() << endl;
s1.Push(7);
cout << s1.Top() << endl;
s1.Pop();
s1.Pop();
s1.Pop();
cout << s1.Top() << endl;
}
分享名称：两个队列实现一个栈
网页链接：
http://bzwzjz.com/article/jhpcpp.html
