/*
 * stack-01.cc    Standard Library, std::stack, exercise 1.
 */
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

template<typename T, typename Container = std::vector<T>>
class Queue
{
public:
   using value_type     = typename Container::value_type;
   using size_type      = typename Container::size_type;
   using container_type = Container;

   explicit Queue(const Container& contents = Container());

   bool              empty() const;
   size_type         size() const;
   value_type&       front();
   const value_type& front() const;
   value_type&       back();
   const value_type& back() const;
   void              push(const value_type& x);
   void              pop();

private:
   std::stack<T, Container> instack_;
   std::stack<T, Container> outstack_;
   void transfer();
   void untransfer();
};

template<typename T, typename Container>
Queue<T, Container>::Queue(const Container& contents) 
   : outstack_{ contents }
{}

template<typename T, typename Container>
bool Queue<T, Container>::empty() const 
{
   return instack_.empty() && outstack_.empty();
}

template<typename T, typename Container>
typename Queue<T, Container>::size_type Queue<T, Container>::size() const
{
   return instack_.size() + outstack_.size();
}

template<typename T, typename Container>
typename Queue<T, Container>::value_type& Queue<T, Container>::front()
{
   transfer(); 
   return outstack_.top();
}
template<typename T, typename Container>
const typename Queue<T, Container>::value_type& 
Queue<T, Container>::front() const
{
   transfer();
   return outstack_.top();
}
template<typename T, typename Container>
typename Queue<T, Container>::value_type& Queue<T, Container>::back()
{
   untransfer();
   return instack_.top();
}

template<typename T, typename Container>
const typename Queue<T, Container>::value_type& 
Queue<T, Container>::back() const
{
   untransfer();
   return instack_.top();
}

template<typename T, typename Container>
void Queue<T, Container>::push(const value_type& x)
{
   instack_.push(x);
}

template<typename T, typename Container>
void Queue<T, Container>::pop()
{
   transfer(); outstack_.pop();
}

template<typename T, typename Container>
void Queue<T, Container>::transfer()
{
   if (outstack_.empty())
      while (! instack_.empty())
      {
	 outstack_.push(instack_.top());
	 instack_.pop();
      }
}

template<typename T, typename Container>
void Queue<T, Container>::untransfer()
{
   if (instack_.empty())
      while (! outstack_.empty())
      {
	 instack_.push(outstack_.top());
	 outstack_.pop();
      }
}

int main()
{
   Queue<int> q;

   for (int i = 0; i < 10; ++i)
   {
      q.push(i);
      cout << i << " pushed\n";
   }
   cout << '\n';

   cout << "queue size is " << q.size() << '\n';
   cout << "queue front is " << q.front() << '\n';
   cout << "queue back is " << q.back() << '\n';
   cout << '\n';

   while (! q.empty())
   {
      cout << q.front() << " popped\n";
      q.pop();
   }
   cout << '\n';

   cout << "queue size is " << q.size() << '\n';

   return 0;
}