#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:
DoubleStack(int s = 10) : size(s), redTop(-1){
A = new T[s];
blueTop = s;
};
virtual ~DoubleStack() {
delete [] A;
};
void pushRed(const T & x); void pushBlue(const T & x); void popRed(); void popBlue(); const T & topRed() const; const T & topBlue() const; void expand();
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) expand();
A[++redTop] = x;
};
template<class T>
void
DoubleStack<T>::pushBlue(const T & x){
if (redTop + 1 == blueTop) 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; 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() {
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