Population

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.

    B.The problem

    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.

¡¡
¡¡
C.The idea of program

    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.

    D.The major functions

    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

    ¡¡