path: root/4.00.stack.cc

/*
 * =====================================================================================
 *
 *       Filename:  4.00.stack.cc
 *
 *    Description:  Implementation of stack as Class
 *
 *        Version:  1.0
 *        Created:  05.05.2014 09:49:24
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Stefan Suhren (SSuhren), suhren.stefan@fh-swf.de
 *   Organization:  FH Südwestfalen, Iserlohn
 *
 * =====================================================================================
 */

#include	<cstdlib>
#include	<iostream>
#include	<iomanip>
#include	<cassert>

using namespace std;

const int MAXARRAY = 100;

// =====================================================================================
//        Class:  Stack
//  Description:  Simple implementation of Stack
// =====================================================================================
class Stack
{
	public:
		// ====================  LIFECYCLE     ======================================= 
		Stack();								// constructor 
		Stack(int);								// constructor 
		~Stack();								// destructor

		// ====================  ACCESSORS     ======================================= 
		void push(int);
		int pop();
		bool isEmpty();
		int top();
		int height();
		void dup();
		void exch();
		void copy(const Stack&);
		void print(string msg);

	private:
		// ====================  METHODS       ======================================= 
		void init( int );
		// ====================  DATA MEMBERS  ======================================= 
		int *stack;
		int next;
		int max;

}; // -----  end of class Stack  ----- 

void belege (int);

// ===  FUNCTION  ======================================================================
//         Name:  main
//  Description:  Tests stack
// =====================================================================================
int main ( int argc, char *argv[] ){
	//-----------------------------------------------------------------------------
	//  4.1
	//-----------------------------------------------------------------------------

	Stack test1(MAXARRAY);

	// Fill test1
	for(int i = 0; i < 99; i++){
		test1.push(i);
	}
	
	// some testcases for the functions
	cout << "\nTest1.isEmpty() = " << boolalpha << test1.isEmpty() << "\n";
	cout << "Test1.top() = " << test1.top() << "\n";
	cout << "Test1.height() = " << test1.height() << "\n";
	test1.exch();
	test1.dup();
	cout << "Test1.height() = " << test1.height() << "\n";

	// Empty test1 and verfiy
	for(int i = 0; i < 100; i++){
		cout << test1.pop() << " ";
	}

	cout << "\nTest1.isEmpty() = " << boolalpha << test1.isEmpty() << "\n";

	//-----------------------------------------------------------------------------
	//  4.2
	//-----------------------------------------------------------------------------

	system("free");

	belege(1024);

	system("free");

	//-----------------------------------------------------------------------------
	//  4.3
	//-----------------------------------------------------------------------------

	Stack stapel2(30), stapel3(20);
	// Fill stack2
	for( int i = 0; i < 15; i++ ){
		stapel2.push(i);
	}

	// Fill stack3
	for( int i = 0; i < 10; i++ ){
		stapel3.push(i);
	}

	// Now print both stacks
	cout << "\n";
	stapel2.print( "Stapel2" );
	cout << "\n";
	stapel3.print( "Stapel3" );

	// Copy 2 on 3
	stapel3.copy(stapel2);

	// Now print both stacks again
	cout << "\n";
	stapel2.print( "Stapel2" );
	cout << "\n";
	stapel3.print( "Stapel3" );

	return EXIT_SUCCESS;
}				// ----------  end of function main  ---------- 

// ===  FUNCTION  ======================================================================
//         Name:  belege
//  Description:  Recursive function for testing the stack
// =====================================================================================
void belege ( int n ){
	if( n <= 0 ){
		system("free");
	}
	else{
		Stack test;
		belege( n-1 );
	}
}		// -----  end of function belege  ----- 

// ===  FUNCTION  ======================================================================
//         Name:  Stack::Stack
//  Description:  Create a dynamic stack with 1024 items
// =====================================================================================
Stack::Stack (  ){
	init( 1024 );
}		// -----  end of function Stack::Stack  ----- 
// ===  FUNCTION  ======================================================================
//         Name:  Stack::Stack
//  Description:  Create a dynamic stack with length items
// =====================================================================================
Stack::Stack ( int length ){
	assert( length > 0 );
	init( length );
}		// -----  end of function Stack::Stack  ----- 

// ===  FUNCTION  ======================================================================
//         Name:  Stack::~Stack
//  Description:  Free memory
// =====================================================================================
Stack::~Stack (  ){
	delete[] stack;
}		// -----  end of function Stack::~Stack  ----- 

// ===  FUNCTION  ======================================================================
//         Name:  Stack::push
//  Description:  Push value onto stack
// =====================================================================================
void Stack::push ( int value ){
	assert( next < max );

	stack[next++] = value; 
}		// -----  end of function Stack::push  ----- 

// ===  FUNCTION  ======================================================================
//         Name:  Stack::pop
//  Description:  Pop element from stack
// =====================================================================================
int Stack::pop (  ){
	assert( next > 0 );

	return stack[--next];
}		// -----  end of function Stack::pop  ----- 

// ===  FUNCTION  ======================================================================
//         Name:  Stack::isEmpty
//  Description:  Determine if stack is empty
// =====================================================================================
bool Stack::isEmpty (  ){
	return next <= 0;
}		// -----  end of function Stack::isEmpty  ----- 

// ===  FUNCTION  ======================================================================
//         Name:  Stack::top
//  Description:  Get topmost value without poping it
// =====================================================================================
int Stack::top (  ){
	assert( next > 0 );

	return stack[next-1];
}		// -----  end of function Stack::top  ----- 

// ===  FUNCTION  ======================================================================
//         Name:  Stack::height
//  Description:  Get the actual hight of the stack
// =====================================================================================
int Stack::height (  ){
	return next;
}		// -----  end of function Stack::height  ----- 

// ===  FUNCTION  ======================================================================
//         Name:  Stack::dup
//  Description:  Duplicate the topmost item
// =====================================================================================
void Stack::dup (  ){
	push(top());
}		// -----  end of function Stack::dup  ----- 

// ===  FUNCTION  ======================================================================
//         Name:  Stack::exch
//  Description:  Swap the two topmost items
// =====================================================================================
void Stack::exch (  ){
	assert( next > 1 );

	int tmp = stack[next-2];
	stack[next-2] = stack[next-1];
	stack[next-1] = tmp;

}		// -----  end of function Stack::exch  ----- 

// ===  FUNCTION  ======================================================================
//         Name:  Stack:copy
//  Description:  Copys a stack s onto this
// =====================================================================================
void Stack::copy ( const Stack &s ){
	if( &s != this ){
		// As a safty
		int *temp = stack;

		// New Stack
		stack = new int[s.max];

		// Deep Copy
		for(int i = 0; i < max; i++){
			stack[i] = s.stack[i];
		}

		// Now make the object consistent
		max = s.max;
		next = s.next;

		// And free memory
		delete[] temp;
	}
}		// -----  end of function Stack:copy  ----- 

// ===  FUNCTION  ======================================================================
//         Name:  Stack:print
//  Description:  
// =====================================================================================
void Stack::print ( string msg ){
	cout << msg;

	for( int i = 0; i < next; i++ ){
		// Every ten values a new line
		if( (i % 10)  == 0 ){
			cout << "\n" << setw(3) << i << " : ";
		}
		cout << setw(5) << stack[i];
	}

	cout << "\nStack-Länge : " << max << " Belegung : " << next << "\n";
}		// -----  end of function Stack:print  ----- 

// ===  FUNCTION  ======================================================================
//         Name:  Stack::init
//  Description:  Initialise next "pointer"
// =====================================================================================
void Stack::init ( int length ){
	next = 0;

	max = length;
	stack = new int[max];
}		// -----  end of function Stack::init  -----