用两个栈兑现一个队列

用两个栈实现一个队列

这个题目的思想如下：

①可以假设栈A和栈B，并且都为空

②栈A提供入栈的功能，栈B提供出栈的

③如果栈B不为空，直接弹出栈B的数据，如果栈B为空，则依次弹出栈A的元素，然后将栈A弹出的元素放入到栈B中，再弹出栈B 的数据

代码如下：

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

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

struct MyQueue
{
stack<T> s1;
stack<T> s2;
void push(T &t)
{
  s1.push(t);
}
T front()
{
  if (s2.empty())
  {
   if (s1.empty())
   {
    throw;
   }
   while (!s1.empty())
   {
    s2.push(s1.top());
    s1.pop();
   }
  }
  return s2.top();
}

void pop()
{
  if (s2.empty())
  {
   while (!s1.empty())
   {
    s2.push(s1.top());
    s1.pop();
   }
  }
  if (!s2.empty())
  {
   s2.pop();
  }
}

};

int _tmain(int argc, _TCHAR* argv[])
{
MyQueue<int> queue;
for (int i=0;i<5;i++)
{
  queue.push(i);
}
for (int i=0;i<5;i++)
{
  cout<<queue.front();
  queue.pop();
}

system("pause");
return 0;
}

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

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

struct MyQueue
{
	stack<T> s1;
	stack<T> s2;
	void push(T &t)
	{
		s1.push(t);
	}
	T front()
	{
		if (s2.empty())
		{
			if (s1.empty())
			{
				throw;
			}
			while (!s1.empty())
			{
				s2.push(s1.top());
				s1.pop();
			}
		}
		return s2.top();
	}
	
	void pop()
	{
		if (s2.empty())
		{
			while (!s1.empty())
			{
				s2.push(s1.top());
				s1.pop();
			}
		}
		if (!s2.empty())
		{
			s2.pop();
		}
	}

};



int _tmain(int argc, _TCHAR* argv[])
{
	MyQueue<int> queue;
	for (int i=0;i<5;i++)
	{
		queue.push(i);
	}
	for (int i=0;i<5;i++)
	{
		cout<<queue.front();
		queue.pop();
	}

	system("pause");
	return 0;
}

用两个栈兑现一个队列

相关推荐