学步园

1.用2个栈实现队列：第一个栈输入进数据，在delete数据时，将第一个栈的数据pop到第二个栈中，这样就能用栈构建队列了

2.用2个队列构建栈：当两个队列都为空时，将数据输入到第一个队列中，在delete时，将第一个队列中除了最后一个输入的数据之外的其他数据pop到另一个队列中，pop第一个队列这样就起到了后进先出的作用，继续删除时，将第二个队列中除了最后一个数之外 的数都pop到第一个中，删除第二个队列中最后一个，。。。。。不多说了，代码上来。

//2个栈实现队列的队尾插入和队头删除
#include <iostream>
#include <stack>
#include <assert.h>
using namespace std;
template<class T> class CQueue
{
public:
	CQueue() {}
	~CQueue() {}

	void appendTail(const T& node);  // append a element to tail
	void deleteHead();               // remove a element from head 

private:
	stack <T> m_stack1;
	stack <T> m_stack2;
};
template<typename T> void CQueue<T>::appendTail(const T& element)
{
	m_stack1.push(element);
} 
template<typename T> void CQueue<T>::deleteHead()
{
	if(m_stack2.size() <= 0)
	{
		while(m_stack1.size() > 0)
		{
			T& data = m_stack1.top();
			m_stack1.pop();
			m_stack2.push(data);
		}
	}
	assert(m_stack2.size() > 0);
	m_stack2.pop();
}
int main()
{
	CQueue<int> m_queue;
	m_queue.appendTail(1);
	m_queue.appendTail(2);
	m_queue.appendTail(3);
	m_queue.appendTail(4);
	m_queue.appendTail(5);
	m_queue.appendTail(6);
	m_queue.deleteHead();
	return 0;
}
//用2个队列实现栈
#include <iostream>
#include <queue>
using namespace std;
template <class T> class CStack
{
public:
	CStack(){};
	~CStack(){};
	void inputnum(const T &node);
	void deletenum();
private:
	queue<int> m_queue1;
	queue<int> m_queue2;
};
template <class T> void CStack<T>::inputnum(const T &node)
{
	if (m_queue1.empty()&&m_queue2.empty())
	{
		m_queue1.push(node);
	}
	else
	{
		if (!m_queue1.empty())
		{
			m_queue1.push(node);
		}
		if (!m_queue2.empty())
		{
			m_queue2.push(node);
		}
	}

}
template <class T> void CStack<T>::deletenum()
{
	if (m_queue2.empty())
	{
		while (m_queue1.size()>1)
		{
			T &data=m_queue1.front();
			m_queue1.pop();
			m_queue2.push(data);
		}
		if (m_queue1.size()==1)
		{
			m_queue1.pop();
		}
	}
	else
	{
		if (m_queue1.empty())
		{
			while (m_queue2.size()>1)
			{
				T &data=m_queue2.front();
				m_queue2.pop();
				m_queue1.push(data);
			}
			if (m_queue2.size()==1)
			{
				m_queue2.pop();
			}
		}
	}
}
int main()
{
	CStack<int> m_stack;
	m_stack.inputnum(1);
	m_stack.inputnum(2);
	m_stack.inputnum(3);
	m_stack.inputnum(4);
	m_stack.inputnum(5);
	m_stack.deletenum();
	m_stack.deletenum();
	m_stack.inputnum(6);
	m_stack.deletenum();
	return 0;
}