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.