两个队列实现一个栈-创新互联

1.

让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：空间域名、虚拟主机、营销软件、网站建设、突泉网站维护、网站推广。

//使用两个队列实现一个栈,优化版（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;

}

创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。

网站栏目：两个队列实现一个栈-创新互联
文章链接：http://cxhlcq.com/article/ddihsp.html