C++算法之 用兩個棧實現一個隊列

C++算法之 用兩個棧實現一個隊列

算法思路：

一個棧用來入隊列，一個棧用來出隊列：

現有兩個棧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 
#include 
using namespace std;

template
class CQueue
{
public:
	CQueue(){}
	~CQueue(){}

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

private:
	stack s1;
	stack s2;
};

template
void CQueue::appendTail(const T& node)
{
	
	s1.push(node);//入棧即是入隊列
}

template
T CQueue::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
void CQueue::Prints()
{
	while (!s1.empty())
	{
		T& data = s1.top();
		cout< q;
	q.appendTail(1);
	q.appendTail(2);
	q.appendTail(3);
	q.appendTail(4);
	q.appendTail(5);

	q.Prints();

	getchar();
	return 0;
}