/////////////////////////////////////////////////////////////////
// ADT.h
// Header file for simple abstract data types: 
//       Vec, Stack, Queue, Heap
/////////////////////////////////////////////////////////////////

template<class T> void swap (T&, T&);  // swap elements a and b 


template<class T> class Vec {  // adjustable length 1D array
 T* data;
 int ndata;
public:
 Vec(int);
 ~Vec();

 int size();    // return current max size of array used to store the vector
 T& operator[](int); // so we can reference vector by a[i]
 void extend(int n, int r=0); // extend max size by n, rotate
};


template<class T> class Stack {
 Vec<T> stack;
 int top, max_size;

public:
 Stack(int)
 ~Stack();
 
 //Push item of type T on stack
 void push(T);

 //Pop item of type T off stack
 T* pop();
};


template<class T> class Queue {
 Vec<T> queue;
 int first, last, max_size;

public:
 Queue(int i=0);
 ~Queue();
 
 void push(T); //Push item of type T on back of queue

 T* pop(); //Pop item of type T off front of queue
};

template<class T, class C> class Heap {
 Vec<T> heap;
 int max_size;
 int last;
public:
 Heap(int i=0);
 ~Heap();
 
 void push(T);
 //Push item of type T on heap

 T* pop();
 //Pop item of type T off heap, return pointer to it.

 // Allow access for a swap function
 friend void swap(T&, T&);
};
