[Austen944]

Hello, I'm having quite some difficulties with this current problem I'm doing.

I am to code and implement a "Template Stack" such that if the Stack gets full, it doubles the size of its Dynamically Allocated Array, copies the data into the newly allocated larger array, and releases the old array.

To test the stack I do the following for the elements of type "integer", "double", and "string"(the string object) :

1.Create a Stack of default size,

2.Use the pseudo random number generator “int rand()” to push 100 integer elements onto the stack.

3.Display all the elements on the stack by popping, approximately 20 per line, until the stack is empty.

4.Next, push 250 pseudo random integer elements onto the stack. The memory should get doubled twice; once when the 101st element is being pushed, and then when the 201st one comes along.

5.Put a “cout statement” in the appropriate method to flag when the memory is getting Doubled.

6.Display all the elements by popping the stack until it is empty, approximately 20 per line.


My code so far :

#include <iostream>
#include <string>
#include <stdlib.h>
#include <string.h>
#include <cctype>
using namespace std;

void reverse(char cs[]);
void ftoa(double f, char cs[]);

template<class T>
class Stack
{
public :
	Stack();
	Stack(const Stack&);
	~Stack();
	bool isEmpty() const;
	bool isFull() const;
	void push(T value);
	T pop();
	int getSize() const;

private :
	T* stackPtr; // pointer to the stack
	int size; // # of elements in the stack
	int capacity; // current size of the stack
	void ensureCapacity(); // check if there is space in the stack
};

// no-arg constructor
template<class T>
Stack<T> :: Stack() : size(0), capacity(100) // default size of 100
{
	stackPtr = new T[capacity];
}

template<class T>
Stack<T> :: Stack(const Stack& stack)
{
	stackPtr = new T[stack.capacity]; // copy constructor
	size = stack.size;
	capacity = stack.capacity;
	for(int i = 0; i < size; i++)
	{
		stackPtr[i] = stack.stackPtr[i];
	}
}

// destructor
template<class T>
Stack<T> :: ~Stack()
{
	delete [] stackPtr;
}

// check if stack is empty
template<class T>
bool Stack<T> :: isEmpty() const
{
	return size == -1;
}

// check if stack is full
template<class T>
bool Stack<T> :: isFull() const
{
	return stackPtr[size - 1];
}

// add a new element to the stack
template<class T>
void Stack<T> :: push(T value)
{
	ensureCapacity();
	stackPtr[size++] = value;
}

// increase capacity if needed
template<class T>
void Stack<T> :: ensureCapacity()
{
	if(size >= capacity)
	{
		// flag that the memory is getting doubled
		cout << "The memory is getting doubled " << endl;

		T* old = stackPtr;
		capacity = 2*size;
		stackPtr = new T[size*2]; // create a new array

		for(int i = 0; i < size; i++) // copy to the new array
		{
			stackPtr[i] = old[i];
		}
		delete [] old; // destroy the old array
	}
}

// remove a element from the stack
template<class T>
T Stack<T> :: pop()
{
	return stackPtr[--size];
}

// get the stack size
template<class T>
int Stack<T> :: getSize() const
{
	return size;
}


int main ()
{
	// Create a stack of 100 random int values
	Stack<int> intStack;
	for(int i = 0; i < 100; i++)
	{
		int n = rand();
		intStack.push(n);

		while(!intStack.isEmpty())
		{
			cout << intStack.pop() << " ";

			if(i % 20 == 0)
			{
				cout << '\n';
			}
		}
	}

	cout << endl;
	cout << endl;

	// stack of 250 random int values
	for(int i = 0; i < 250; i++)
		{
			int n = rand();
			intStack.push(n);

			while(!intStack.isEmpty())
			{
				cout << intStack.pop() << " ";

				if(i % 20 == 0)
				{
					cout << '\n';
				}
			}
		}

	cout << endl;
	cout << endl;

	// Create a stack of 100 random double values
	Stack<double> doubleStack;
	for(int i = 0; i < 100; i++)
	{
		double n = (double)(rand()/100.0);
		doubleStack.push(n);

		while(!doubleStack.isEmpty())
		{
			cout << doubleStack.pop() << " ";

			if(i % 20 == 0)
			{
				cout << '\n';
			}
		}
	}

	cout << endl;
	cout << endl;

	// stack of 250 random double values
	for(int i = 0; i < 250; i++)
		{
		    double n = (double)(rand()/100.0);
			doubleStack.push(n);

			while(!doubleStack.isEmpty())
			{
				cout << doubleStack.pop() << " ";

				if(i % 20 == 0)
				{
					cout << '\n';
				}
			}
		}

	cout << endl;
	cout << endl;

	// create a stack of 100 random strings
	int MAX_SIZE = 100;
	char cs[MAX_SIZE];
	Stack<string> stringStack;

	return 0;
}

/* Function to convert decimal fraction to c-string */
void ftoa(double f, char cs[])
{

}

Problems so far :

1) I'm almost sure that I coded the "class Stack" right but when I output the integer and double values using the class stack, I get this :

41
134265530
18467 6334 26500 19169 15724 11478 29358 26962 24464 5705 28145 23281 16827 9961 491 2995 11942 4827 5436 32391
14604 3902 153 292 12382 17421 18716 19718 19895 5447 21726 14771 11538 1869 19912 25667 26299 17035 9894 28703
..................................................... ect

4833
31115 4639 29658 22704 9930 13977 2306 31673 22386 5021 28745 26924 19072 6270 5829 26777 15573 5097 16512 23986
13290 9161 18636 22355 24767 23655 15574 4031 12052 27350 1150 16941 21724 13966 3430 31107 30191 18007 11337 15457
..................................................... ect

283.21
3.95644e-270
195.58 236.46 279.82 4.81 41.44 231.96 202.22 71.29 21.61 55.35 204.5 111.73 104.66 120.44 216.59 262.92 264.39 172.53 200.24 261.54
..................................................... ect

280.19
21.25 265.76 216.94 226.58 263.02 173.71 224.66 46.78 225.93 238.51 254.84 10.18 284.64 211.19 231.52 28 180.87 310.6 19.26 90.1
..................................................... ect

Being that there is a single int / double value on a line at the beginning but proceeds to print the rest out 20 per line correctly. Any ideas why its doing that?


2)I can't seem to output the "cout statement" that says the memory is getting doubled. Did I misplace the "cout statment" or am I doing it very wrong?

section of code for cout statement :

// increase capacity if needed
template<class T>
void Stack<T> :: ensureCapacity()
{
	if(size >= capacity)
	{
		// flag that the memory is getting doubled
		cout << "The memory is getting doubled " << endl;

		T* old = stackPtr;
		capacity = 2*size;
		stackPtr = new T[size*2]; // create a new array

		for(int i = 0; i < size; i++) // copy to the new array
		{
			stackPtr[i] = old[i];
		}
		delete [] old; // destroy the old array
	}
}

3)And my biggest problem is actually writing the function "void ftoa(double f, char cs[]);" that converts a decimal fraction "f" to a c-string "cs", which I should create a string object "s" from "cs". Assuming "f" has 2 decimal places.
I am not allowed to use "sprintf()", "stringstream", or vectors and such (havn't learned that far yet).

Any ideas or tips on how I should go about writing this function and creating the string object from the c-string?

Help is greatly appreciated.

[David W]

You might like to look at this 'dynamic array' re-linked here since the DIC snippets have been 'down' for some time now.

template class dynamic array

Or this ... based on a list ( as often a stack is also) ...

template class queue

[Skydiver]

Look closely at your isEmpty() method. Why do you consider the stack to be empty when size is -1?

[Austen944]

Whoops that should be set to 0 right? I was following my instructors partial example >.>
So setting size = to 0 almost fixed the first problem. I still get one int / double value on the first line by itself. Any reason for that?

This post has been edited by Austen944: 02 July 2013 - 07:51 PM

[Skydiver]

Well, with your for loop of i = 0 to 100, when i == 0, then 0 % 20 == 0, so therefore the line is broken as you've commanded the computer to do in your program. Why is that unexpected?

This post has been edited by Skydiver: 02 July 2013 - 08:26 PM

[Austen944]

I just fail at logic. Thanks! Going to see what I can do about the last two problems.

[Austen944]

Just checked with my instructor again and I am allowed to use sprinf(), so my program is pretty much complete. I just have one last problem. I need to put a “cout statement” in the appropriate method to flag when the memory is getting doubled and I can't seem to get it to print out the statement.

Coding of the full program :

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;

void ftoa(double f, char cs[]);

template<class T>
class Stack
{
public :
	Stack();
	Stack(const Stack&);
	~Stack();
	bool isEmpty() const;
	bool isFull() const;
	void push(T value);
	T pop();
	int getSize() const;

private :
	T* stackPtr; // pointer to the stack
	int size; // # of elements in the stack
	int capacity; // current size of the stack
	void ensureCapacity(); // check if there is space in the stack
};

// no-arg constructor
template<class T>
Stack<T> :: Stack() : size(0), capacity(100) // default size of 100
{
	stackPtr = new T[capacity];
}

template<class T>
Stack<T> :: Stack(const Stack& stack)
{
	stackPtr = new T[stack.capacity]; // copy constructor
	size = stack.size;
	capacity = stack.capacity;
	for(int i = 0; i < size; i++)
	{
		stackPtr[i] = stack.stackPtr[i];
	}
}

// destructor
template<class T>
Stack<T> :: ~Stack()
{
	delete [] stackPtr;
}

// check if stack is empty
template<class T>
bool Stack<T> :: isEmpty() const
{
	return size == 0;
}

// check if stack is full
template<class T>
bool Stack<T> :: isFull() const
{
	return stackPtr[size - 1];
}

// add a new element to the stack
template<class T>
void Stack<T> :: push(T value)
{
	ensureCapacity();
	stackPtr[size++] = value;
}

// increase capacity if needed
template<class T>
void Stack<T> :: ensureCapacity()
{
	if(size >= capacity)
	{
                cout << "The memory is getting doubled" << endl;
		T* old = stackPtr;
		capacity = 2*size;
		stackPtr = new T[size*2]; // create a new array

		for(int i = 0; i < size; i++) // copy to the new array
		{
			stackPtr[i] = old[i];
		}
		delete [] old; // destroy the old array
	}
}

// remove a element from the stack
template<class T>
T Stack<T> :: pop()
{
	return stackPtr[--size];
}

// get the stack size
template<class T>
int Stack<T> :: getSize() const
{
	return size;
}


int main ()
{
	// Create a stack of 100 random int values
	cout << "Stack of 100 random int values : " << endl;
	Stack<int> intStack;
	for(int i = 1; i < 101; i++)
	{
		int n = rand();
		intStack.push(n);

		while(!intStack.isEmpty())
		{
			cout << intStack.pop() << " ";

			if(i % 20 == 0)
			{
				cout << '\n';
			}
		}
	}

	cout << endl;
	cout << endl;

	// stack of 250 random int values
	cout << "Stack of 250 random int values : " << endl;
	for(int i = 1; i < 251; i++)
	{
		int n = rand();
		intStack.push(n);

		while(!intStack.isEmpty())
		{
			cout << intStack.pop() << " ";

			if(i % 20 == 0)
			{
				cout << '\n';
			}
		}
	}

	cout << endl;
	cout << endl;

	// Create a stack of 100 random double values
	cout << "Stack of 100 random double values : " << endl;
	Stack<double> doubleStack;
	for(int i = 1; i < 101; i++)
	{
		double n = (double)(rand()/100.0);
		doubleStack.push(n);

		while(!doubleStack.isEmpty())
		{
			cout << doubleStack.pop() << " ";

			if(i % 20 == 0)
			{
				cout << '\n';
			}
		}
	}

	cout << endl;
	cout << endl;

	// stack of 250 random double values
	cout << "Stack of 250 random double values : " << endl;
	for(int i = 1; i < 251; i++)
	{
		double n = (double)(rand()/100.0);
	    doubleStack.push(n);

		while(!doubleStack.isEmpty())
		{
			cout << doubleStack.pop() << " ";

			if(i % 20 == 0)
			{
				cout << '\n';
			}
		}
	}

	cout << endl;
	cout << endl;

	// create a stack of 100 random strings
	cout << "Stack of 100 random string values : " << endl;
	int MAX_SIZE = 10;
	char cs[MAX_SIZE];
	Stack<string> stringStack;

	for(int i = 1; i < 101; i++)
	{
		double n = (double)(rand()/100.0);
		ftoa(n, cs);
		stringStack.push(cs);

		while(!stringStack.isEmpty())
		{
			cout << stringStack.pop() << " ";

			if(i % 20 == 0)
			{
				cout << '\n';
			}
		}
	}

	cout << endl;
	cout << endl;

	// stack of 250 random strings
	cout << "Stack of 250 random string values : " << endl;
	for(int i = 1; i < 251; i++)
	{
		double n = (double)(rand()/100.0);
		// call ftoa function to convert to string
		ftoa(n, cs);
		stringStack.push(cs);

		while(!stringStack.isEmpty())
		{
			cout << stringStack.pop() << " ";

			if(i % 20 == 0)
			{
				cout << '\n';
			}
		}
	}

	return 0;
}

/* Function to convert decimal fraction to c-string */
void ftoa(double f, char cs[])
{
	sprintf(cs, "%.2f", f);
}

I thought adding the "cout statement" in ensurecapacity() would print out when size >= capacity but it doesn't seem to work.

// increase capacity if needed
template<class T>
void Stack<T> :: ensureCapacity()
{
	if(size >= capacity)
	{
        cout << "The memory is getting doubled" << endl;
		T* old = stackPtr;
		capacity = 2*size;
		stackPtr = new T[size*2]; // create a new array

		for(int i = 0; i < size; i++) // copy to the new array
		{
			stackPtr[i] = old[i];
		}
		delete [] old; // destroy the old array
	}
}

Any suggestions?

[David W]

First off ... since you were told you could use sprintf


You would be better advised, in C++, to use stringstream objects to do your conversions ...

/* Function to convert decimal fraction to string */
void ftostring( double f, string& str )
{
    stringstream ss;
    ss << f;
    str = ss.str();
}

So these would be your includes ...

#include <iostream>
#include <sstream> // re.stringstream obj's
#include <iomanip> // re. setw

#include <cstdlib> // re. rand
#include <ctime> // re. time

Also you forgot one of the 'big three' when using dynamic memory ..
an overloaded =

// overloaded =
template<class T>
Stack<T>& Stack< T > :: operator = ( const Stack& stack )
{
    if( this != &stack )
    {
        delete [] stack;
        
        capacity = stack.capacity;
        size = stack.size;
        stackPtr = new T[ capacity ];

        for( int i = 0; i < size; ++i )
        	stackPtr[i] = stack.stackPtr[i];
    }
    return *this;
    
}

Also ... you may like to adjust your dtor ...

// destructor
template<class T>
Stack<T> :: ~Stack()
{
	delete [] stackPtr;
	size = capacity = 0;
	stackPtr = 0;
}

Also ... you may like to have a function like this to pause the output after filling a screen ...

void pauseForEnter()
{
    cout << "\nPress 'Enter' to continue ... " << flush;
    string dummy;
    getline( cin, dummy );
    cout << endl;
}

There were several code fixes here ...

template<class T>
Stack<T> :: Stack() : capacity( STACK_START_CAPACITY ), size(0)
{
	stackPtr = new T[ capacity ];
}

// copy constructor
template<class T>
Stack<T> :: Stack( const Stack& stack )
{
    capacity = stack.capacity;
    size = stack.size;
	stackPtr = new T[ capacity ];
	
	for( int i = 0; i < size; ++i )
		stackPtr[i] = stack.stackPtr[i];
}


// overloaded =
template<class T>
Stack<T>& Stack< T > :: operator = ( const Stack& stack )
{
    if( this != &stack )
    {
        delete [] stack;
        
        capacity = stack.capacity;
        size = stack.size;
        stackPtr = new T[ capacity ];

        for( int i = 0; i < size; ++i )
        	stackPtr[i] = stack.stackPtr[i];
    }
    return *this;
    
}

// destructor
template<class T>
Stack<T> :: ~Stack()
{
	delete [] stackPtr;
	size = capacity = 0;
	stackPtr = 0;
}

// check if stack is empty
template<class T>
bool Stack<T> :: isEmpty() const
{
	return size == 0;
}

// check if stack is full
template<class T>
bool Stack<T> :: isFull() const
{
	return size == capacity;
}

// add a new element to the stack
template<class T>
void Stack<T> :: push( T value )
{
	ensureCapacity();
	stackPtr[size++] = value;
}

// increase capacity if needed
template<class T>
void Stack<T> :: ensureCapacity()
{
	if( size >= capacity )
	{
        cout << "\nThe memory is getting doubled\n";
        
		T* old = stackPtr;  // get copy of address ...
		
		capacity += capacity; // double memory/capacity ...
		stackPtr = new T[capacity]; // create a new array

		for( int i = 0; i < size; ++i ) // copy old to the new array
			stackPtr[i] = old[i];
			
		delete [] old; // destroy the old array
	}
}

// remove a element from the stack
template<class T>
T Stack<T> :: pop()
{
	return stackPtr[--size];
}

// get the stack size
template<class T>
int Stack<T> :: getSize() const
{
	return size;
}

Then your main could be just this ...

int main ()
{
	// Create a stack of 100 random int values
	cout << "Stack of 100 random int values : " << endl;
	Stack< int > intStack;
	
	srand( time(0) );
	
	for( int i = 1; i <= 100; ++i )
	{
		int n = rand() % 100 +1 ;
		intStack.push( n );
	}
	
	// show/pop stack till empty ...
	while( !intStack.isEmpty() )
		cout << setw( 4 ) << intStack.pop();
    pauseForEnter();
    
    
	// stack of 250 random int values
	cout << "Stack of 250 random int values : " << endl;
	for( int i = 1; i <= 250; ++i )
	{
		int n = rand() % 250 +1;
		intStack.push( n );
	}
	
	// show/pop stack till empty ...
	while( !intStack.isEmpty() )
		cout << setw( 4 ) << intStack.pop();
	pauseForEnter();;

	// Create a stack of 100 random double values
	cout << "Stack of 100 random double values : " << endl;
	Stack< double > doubleStack;
	for( int i = 1; i <= 100; ++i )
	{
		double n = rand()/100.0;
		doubleStack.push( n );
	}

	// show/pop stack till empty ...
	while( !doubleStack.isEmpty() )
		cout << setw( 8 ) << doubleStack.pop();
	pauseForEnter();


	// stack of 250 random double values
	cout << "Stack of 250 random double values : " << endl;
	for(int i = 1; i <= 250; i++)
	{
		double n = rand()/100.0;
	    doubleStack.push( n );
	}

	// show/pop stack till empty ...
	while( !doubleStack.isEmpty() )
		cout << setw( 8 ) << doubleStack.pop();
	pauseForEnter();




	// create a stack of 100 random strings
	cout << "Stack of 100 random string values : " << endl;
	
	//const int MAX_SIZE = 32; // see global at top
	//char cs[MAX_SIZE];
	Stack<string> stringStack;
	string str;

	for(int i = 1; i <= 100; ++i )
	{
		double n = rand()/100.0;
		ftostring( n, str );
		stringStack.push( str );
	}
	
	while( !stringStack.isEmpty() )
		cout << setw( 8 ) << stringStack.pop();
	pauseForEnter();


	// stack of 250 random strings
	cout << "Stack of 250 random string values : " << endl;
	for( int i = 1; i <= 250; ++i )
	{
		double n = rand()/100.0;
		// call ftostring function to convert to string
		ftostring( n, str ) ;
		stringStack.push( str );
	}
	
	while( !stringStack.isEmpty() )
		cout << setw( 8 ) << stringStack.pop();
	pauseForEnter();

}

Edit: srand now used above

This post has been edited by David W: 04 July 2013 - 04:19 PM

[Austen944]

Wow, awesome ! Thank you very much for the informative post.