StackArray
A.First Edition
This is my first edition of a simple assignment of C++. And I hesitate for some time to decide whether to add it.
A Taste of the Real Life
------------------------
A Stack is a data structure that can store data in a last-in,
first-out (LIFO) fashion. Stacks are manipulated with push and
pop methods. A push method puts new data onto the Stack. A pop
method returns the last elements from the Stack.
For example, if we created a Stack with 4 elements then the data
structure would be empty like this:
-------------------------
| | | | |
-------------------------
^
next
The marker "next" tells us where to push the next peice of data.
If we pushed data onto the stack, say the value 13, then we have
-------------------------
| 13 | | | |
-------------------------
^
next
If we pushed another value, say 4, then we would get
-------------------------
| 13 | 4 | | |
-------------------------
^
next
Popping off a value from the Stack results in returning the value
4 and moving the 'next' marker back one:
-------------------------
| 13 | 4 | | |
-------------------------
^
next
Pushing a new value onto the Stack, say 73, would produce
-------------------------
| 13 | 73 | | |
-------------------------
^
next
... etc...
Your job is to create a Stack by inheriting an Array class that has
been precompiled for you. The required files may be found at:
Array Header: http://www.ece.concordia.ca/~c_taille/COEN244/ASS4/Array.h
Stack Header: http://www.ece.concordia.ca/~c_taille/COEN244/ASS4/Stack.h
Array Object Code ( for Windows Users ):
http://www.ece.concordia.ca/~c_taille/COEN244/ASS4/Array.obj
Array Object Code ( for UNIX Users ):
http://www.ece.concordia.ca/~c_taille/COEN244/ASS4/Array.o
Make sure you test your Stack using a comprehensive driver program!!!
Include the output with your solution.
There is nothing special about this assignment except that the base class was given as object file which means
that you don't know the exact implementation of Array class except all interfaces declared in .h file.
1. bool Stack::resize()
This utility function does a safe mode resize which delete old data until dynamic allocating succeeds.
E.Further improvement
1. Are you kidding? For such a trivial program?
Array.h
///////////////////////////////////
// Array Header File
///////////////////////////////////
#ifndef ARRAY_H
#define ARRAY_H
#include <iostream>
using std::ostream ;
class Array {
friend ostream &operator<<( ostream &, const Array & );
public:
Array( int = 10 ); // default constructor
Array( const Array & ); // copy constructor
~Array(); // destructor
int getSize() const; // return size
protected:
int size; // size of the array
int *ptr; // pointer to first element of array
};
#endif
Stack.h
#ifndef MYSTACK_H
#define MYSTACK_H
#include <iostream>
using std::ostream ;
#include "Array.h"
class Stack : public Array {
// Should only output the data that is in the stack
friend ostream& operator<<(ostream&, Stack& ) ;
public:
// Constructor creating array of size integers
Stack( int size ) ;
// Put data into the stack, return true if sucessful, otherwise
// return false.
bool push( int data ) ;
// Take data off the stack and return its value.
int pop() ;
// Returns true if the stack is empty
bool operator!() ;
private:
// Mark the next place in the stack (i.e. array) where data
// will be pushed. Data is popped from (next-1).
int next ;
//this const is the increment size for each resize
const int increment;
//an utility function to reloc mem, if failed, return false
bool resize();
//utility function to test if stack is empty
bool isEmpty();
} ;
#endif
Stack.cpp
/*******************************************************************
*Program: Stack.CPP
*Assignment no.: 4
*Date: Jul. 31, 2003
*Author: Qingzhe Huang
*ID: 5037735
*Features:
* 1. I implement the similar function of dynamic array, so that size of
* stack will be increase dynamically by relocating.
* 2. I particularly want to make dynamic allocationg in a safe mode,
* that is when memory allocation fails, the original data in stack will
* by no means be lost! So, at least we can keep what we already have.
* 3. I defined a private const data memeber for stack---increment which
* is the increment of size of memory for each resize.
********************************************************************/
#include "Stack.h"
using namespace std;
Stack::Stack(int size):Array(size),increment(10)
{
next = 0;
}
bool Stack::push(int data)
{
if (next>=size)//need to resize
{
if (!resize())//resize handles exception if dynamic alloc fails
{
return false;
}
}
//now do the pushing job
ptr[next] = data;
next++;
return true;
}
//a simple utitlity function cause I don't want repeating same code
//this utitlity function is used in both overloaded operator "!"
//and pop() function, so should be an utility function
bool Stack::isEmpty()
{
return next==0;
}
int Stack::pop()
{
if (!isEmpty())
{
next--;
return ptr[next];
}
else
{
cout<<"Stack is empty!\n";
return 0;//I really don't know what is appropriate to return
}
}
//this resize function use a safe method to rellocate
//that is delete old data only after dynamic allocating succeeding
//otherwise, restore the old ptr to keep original data
bool Stack::resize()
{
int *tmpPtr = ptr;
//every time size increment "size of increment"--a const of 10
ptr = new int[size+increment];
if (ptr==NULL)//if mem allocating fails
{
//since failed, we need to restore all old data
ptr = tmpPtr;
//size has not been changed yet!
return false;
}
else
{
//copy old data, now there should be "size" number of datas!
for (int i=0; i<size; i++)
{
ptr[i] = tmpPtr[i];
}
size+=increment;//update size
delete []tmpPtr;//and delete old Ptr;
return true;
}
}
bool Stack::operator !()
{
return isEmpty();
}
//no data is changed in stack
ostream& operator<<(ostream& out, Stack& S )
{
int count = S.next;
for (int i=0; i<count;i++)
{
out<<"no."<<i<<" is "<<S.ptr[i]<<'\n';
}
out<<'\n';
return out;
}
Main.cpp
#include "Stack.h"
#include <iostream>
using namespace std;
int main()
{
Stack S(5);
//test the dynamic allocating mem of stack
cout<<"test the dynamic mem allocating function by push more elements than\n"
<<"size of stack, say 4 times of original size"<<endl;
for (int i=0; i<21; i++)
{
S.push(i);
}
//now test the friend function of ostream
cout<<"now test friend function of ostream which will show all 21 elements\n"
<<" and the stack should remain the same after outputing\n"
<<"you can make sure of this by the result of pop action after this"<<endl;
cout<<S;
//now test the pop function and try to pop one more element in stack
cout<<"now test the pop function and try to pop one more element in stack\n"
<<"so, there will be an error message at end "<<endl;
for (i=0; i<22; i++)
{
cout<<S.pop()<<endl;
}
//test operator !
cout<<"now test operator!, since stack is empty now, \n"
<<"it should return true\n";
cout<<(!S?"TRUE"
:"FALSE")<<endl;
//now test extreme situation by passing negative size to stack
cout<<"now test extreme situation by passing negative size to stack"<<endl;
Stack P(-1);
for (i=0; i<5; i++)
{
P.push(i);
}
cout<<P;
return 0;
}
Running result of program:
test the dynamic mem allocating function by push more elements than size of stack, say 4 times of original size now test friend function of ostream which will show all 21 elements and the stack should remain the same after outputing you can make sure of this by the result of pop action after this no.0 is 0 no.1 is 1 no.2 is 2 no.3 is 3 no.4 is 4 no.5 is 5 no.6 is 6 no.7 is 7 no.8 is 8 no.9 is 9 no.10 is 10 no.11 is 11 no.12 is 12 no.13 is 13 no.14 is 14 no.15 is 15 no.16 is 16 no.17 is 17 no.18 is 18 no.19 is 19 no.20 is 20 now test the pop function and try to pop one more element in stack so, there will be an error message at end 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Stack is empty! 0 now test operator!, since stack is empty now, it should return true TRUE now test extreme situation by passing negative size to stack no.0 is 0 no.1 is 1 no.2 is 2 no.3 is 3 no.4 is 4