stack2.cpp

// stack2.cpp
//
// This is the second version of the Stack data structure, in C++
// It demonstrates a base and derived class, for re-usability purposes,
// not really for polymorphism, or virtual functions.
//
// There are 2 classes here: Array, a basic array container class, and
// Stack, derived from Array.

#include <iostream.h>
#include <assert.h>
#include <string.h> // For memmove()

// The Array Class
class Array
{
public:
	Array(int NewElementSize, int NewSize=0);
	~Array() { delete Data; }
	int GetAt( int Index, void * Dest );
	int SetAt( int Index, void * Src );
	int Insert( int Index, void * Src );
	void Delete( int Index );
protected:
	enum GB { GrowBy=8 };
	int ElementSize, ElementCount, DataSize;
	char * Data;	// char, for convenience later with pointer arithmetic
};

// Array Constructor
Array::Array(int NewElementSize, int NewSize)
{
	ElementCount = 0;
	ElementSize = NewElementSize;
	DataSize = NewSize;
	
	if( DataSize==0 )
		Data = 0;
	else
	{
		Data = new char[NewSize * ElementSize];
		assert( Data!=0 );
	}
}

// Array::GetAt - Retrieve element from array
int Array::GetAt( int Index, void *Dest )
{
	if( Index>=ElementCount || Index < 0 )
		return(0);
	memmove( Dest, Data + Index*ElementSize, ElementSize );
	return(1);
}

// Array::SetAt - Sets an element in the array
int Array::SetAt( int Index, void *Src )
{
	if( Index>=ElementCount || Index < 0 )
		return(0);
	memmove( Data + Index*ElementSize, Src, ElementSize );
	return(1);
}

// Array::Insert - Inserts new element into array
int Array::Insert( int Index, void * Src )
{
	if( Index < 0 || Index > ElementCount )
		return(0);
	char * Tmp;
	if( (DataSize%GrowBy) == 0 )
	{
		if( (Tmp=new char[ElementSize*(DataSize+GrowBy)]) == 0 )
			return(0);
		memmove( Tmp, Data, ElementSize*ElementCount);
		delete [] Data;
		Data = Tmp;
		DataSize+=GrowBy;
	}
	memmove( Data+(Index+1)*ElementSize, Data+(Index)*ElementSize, 
			(ElementCount-Index)*ElementSize );
	memmove( Data+Index*ElementSize, Src, ElementSize );
	ElementCount++;
	return(1);
}

// Array::Delete - Removes element from array
void Array::Delete( int Index )
{
	memmove( Data+Index*ElementSize, Data+(Index+1)*ElementSize, 
		(ElementCount-Index-1)*ElementSize );
	ElementCount--;
}

// Now, note how little code we need to write for Stack
class Stack : protected Array
{
public:
	Stack( int NewSize=0 ) : Array( sizeof(int), NewSize ) { Index=0; }
	int Push( int Value ) { return( Insert( Index++, &Value ) ); }
	int Pop( int* Dest ) { if(Index==0) return(0); GetAt(--Index, Dest ); return(1); }
	int IsFull() { return( Index==DataSize ); }
	int IsEmpty() { return( Index==0 ); }
private:
	int Index;
	
};


void main()
{
	Stack X;
	int V;
	X.Push(1);
	X.Push(2);
	X.Push(3);
	while( X.Pop(&V) == 1 )
		cout << V << endl;
	// Note: Destructor for X automatically called
}