两个栈实现一个队列

方法一：

时间复杂度：

push O(1)
pop O(n)
peek O(n) 查看队头元素
empty O(1)

方法二：

pop 和 peek 的时间复杂度为 O(n) 是因为访问了队头(都位于栈底)，对于栈来说访问栈顶是最快的，那么我们只需要使用两个栈实现先入队位于s1的栈顶就可以解决pop 和 peek 的时间复杂度高的问题、

当执行push操作时，向s1内压栈元素
如果做pop或peek操作，都从s2栈顶直接操作，如果s2为空，那么就将s1中的元素全部入栈到s2中

//两个栈实现一个队列
class queue
{
public:
	void push(int val)
	{
		s1.push(val);
	}
	void pop()
	{
		if (s2.empty())
		{
			while (!s1.empty())  //将s1中的元素 dump 到s2中
			{
				s2.push(s1.top());
				s1.pop();
			}
			s2.pop();
		}
		else
		{
			s2.pop();
		}
	}
	int peek()
	{
		if (s2.empty())
		{
			while (!s1.empty())  //将s1中的元素 dump 到s2中
			{
				s2.push(s1.top());
				s1.pop();
			}
			return s2.top();
		}
		else
		{
			return s2.top();
		}
		
	}
	bool empty()
	{
		if (s1.empty() && s2.empty())
		{
			return true;
		}
		return false;
	}
private:
	stack<int> s1;
	stack<int> s2;
};