#include<iostream>
using namespace std;

#if !defined(DOUBLESTACK_H)
#define DOUBLESTACK_H

template <class T>
class DoubleStack {
	T *A;
	int redTop;
	int blueTop;
	int size;
public:
	//The argument is the initial size of the array
	DoubleStack(int s = 10) : size(s), redTop(-1){
		A = new T[s];
		blueTop = s;
	};
	virtual ~DoubleStack() {
		delete [] A;
	};

	void pushRed(const T & x); //amortized O(1)
	void pushBlue(const T & x); //amortized O(1)
	void popRed(); //O(1)
	void popBlue(); //O(1)
	const T & topRed() const; //O(1)
	const T & topBlue() const; //O(1)
	void expand(); //O(N)

	friend ostream& operator<<(ostream & os, const DoubleStack<T> & s)
	{
		int i;
		os << "Red: ";
		for (i =0; i <= s.redTop; ++i)
			os << s.A[i] << " ";
		os << endl << "Blue: ";
		for (i=s.size-1; i >= s.blueTop; --i)
			os << s.A[i] << " ";
		return os;
	};
	
	
};

template<class T>
void 
DoubleStack<T>::pushRed(const T & x){
	if ((redTop+1) == blueTop) //full
		expand();
	A[++redTop] = x;
};

template<class T>
void 
DoubleStack<T>::pushBlue(const T & x){
	if (redTop + 1 == blueTop) //full
		expand();
	A[--blueTop] = x;
};

template<class T>
void 
DoubleStack<T>::popRed(){
	if (redTop == -1)
		return;
	redTop--;
};

template<class T>
void 
DoubleStack<T>::popBlue(){
	if (blueTop == size)
		return;
	blueTop++;
};

template<class T>
const T & 
DoubleStack<T>::topRed() const{ 
	if (redTop == -1) 
		return 0; //This gives a waring in VC++ because its bad style.
					//I should, instead, throw an exception.
	return A[redTop];
};

template<class T>
const T & 
DoubleStack<T>::topBlue() const{ 
	if (blueTop == size)
		return 0;
	return A[blueTop];
};

template<class T>
void
DoubleStack<T>::expand() { 
//	cout << "Calling expand" << endl;
	int ns = size * 2;
	T * b = new T[ns];
	int i;
	for (i= 0 ; i<= redTop; ++i)
		b[i] = A[i];
	int j;
	for (i=size -1, j= ns-1; i >= blueTop; --i, --j)
		b[j] = A[i];
	blueTop = j+1;
	size = ns;
	delete [] A;
	A = b;
}

#endif