C++算法之用两个栈实现一个队列

浏览数：24 / 时间：2015年06月08日

算法思路：

一个栈用来入队列，一个栈用来出队列：

现有两个栈s1 和s2；s1用来入栈，比如队列进入 1 2 3 4 5 那么s1进栈 1 2 3 4 5 ，现在要出队列，意思就是要1先出来；

那么我们把栈s1的数据取出来都压到栈s2当中，那么栈s2就是 5 4 3 2 1 ；s2再出栈，此时1出栈就模拟出出队列的效果；

编写代码：

// QueueFrom2Stack.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <stack>
using namespace std;

template<typename T>
class CQueue
{
public:
	CQueue(){}
	~CQueue(){}

	void appendTail(const T& node);
	T deleteHead();
	void Prints();

private:
	stack<T> s1;
	stack<T> s2;
};

template<typename T>
void CQueue<T>::appendTail(const T& node)
{
	
	s1.push(node);//入栈即是入队列
}

template<typename T>
T CQueue<T>::deleteHead()
{
	if (s2.size() <= 0)  //如果栈为空,就要先把s1出栈然后再压栈
	{
		if (i = 0; i < s1.size();i++)
		{
			T& data = s1.top();
			s1.pop();
			s2.push(data);
		}
	}

	if (s2.size() == 0)
	{
		throw new exception("queue is empty");
	}

	T head = s2.top();
	s2.pop();

	return head;
}

template<typename T>
void CQueue<T>::Prints()
{
	while (!s1.empty())
	{
		T& data = s1.top();
		cout<<data<<endl;
		s1.pop();
	}
}


int _tmain(int argc, _TCHAR* argv[])
{

	CQueue<int> q;
	q.appendTail(1);
	q.appendTail(2);
	q.appendTail(3);
	q.appendTail(4);
	q.appendTail(5);

	q.Prints();

	getchar();
	return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

C++算法之用两个栈实现一个队列