Inheritance (Stack and Queue Inherit Array)

[ScrubOb]

I am new to C++ programming.
I have a task: Define an inheriting system that can inherit a class called “myArray”, this class will include virtual functions to serve two data structures: "Queue" and "Stack".

My code for myArray and Stack are below. I am unsure if I have used C++ inheritance correctly, so any help would be greatly appreciated.

class myArray
{
public:
myArray(int = 10); // default constructor (array size 10)
~myArray() { delete[] arrayPtr; } // destructor
virtual bool insertA(const int&); // insert an element into the array
virtual bool deleteA(int&); // remove an element from the array
virtual bool isEmpty() { return top == -1; }
virtual bool isFull() { return top == size - 1; }

private:
int size; // # of elements in the array`
int top; // location of the top element`
int *arrayPtr; // pointer to the array`
};

myArray::myArray(int s)
{
size = s > 0 ? s : 10;
top = -1; // array is initially empty
arrayPtr = new int[size]; // allocate space for elements
}
​
// Insert an element into the array
// return 1 if successful, false otherwise
bool myArray::insertA(const int &insertValue)
{
if (!isFull()) {

arrayPtr[++top] = insertValue; // place item in array

return true; // insert successful

}

return false; // insert unsuccessful
}

bool myArray::deleteA(int &insertValue)
{
if (!isEmpty()) {

insertValue = arrayPtr[top--]; // remove item from array

return true; // delete successful

}
return false; // delete unsuccessful
}

Stack:

class StaticStack : public myArray
{
public:
StaticStack(int = 10); // default constructor (stack size 10)
~StaticStack() { delete[] stackPtr; } // destructor
virtual bool push(const int&); // insert an element from the stack
virtual bool pop(int&); // remove an element into the stack
virtual bool isEmpty() { return top == -1; }
virtual bool isFull() { return top == size - 1; }

private:
int size; // # of elements in the stack
int top; // location of the top element
int *stackPtr; // pointer to the stack
};

StaticStack::StaticStack(int s)
: myArray()
{
size = s > 0 ? s : 10;
top = -1; // stack is initially empty
stackPtr = new int[size]; // allocate space for elements
}

// Insert an element into the stack
// return 1 if successful, false otherwise
bool StaticStack::push(const int &insertValue)
{
if (!isFull()) {
stackPtr[++top] = insertValue; // place item in stack
return true; // insert successful
}
return false; // insert unsuccessful
}

bool StaticStack::pop(int &insertValue)
{
if (!isEmpty()) {
insertValue = stackPtr[top--]; // remove item from stack
return true; // delete successful
}
return false; // delete unsuccessful
}

[tpb]

You are totally misunderstanding inheritance. The point is to NOT redefine member variables and functions that don't need to be redefined, thereby "inheriting" those from the base class. In particular, you definitely don't want to redefine size, top, and the data pointer. Since myArray already has those and you are inheriting from it, if you also declare them in the derived class you will have all of that TWICE! Even the member functions are defined exactly like the ones in Array (just named differently).

I don't actually understand the assignment since it's hard to see why the functions need to be virtual. In fact, inheritance itself seems wrong here. It would make more sense if Stack simply contained an Array.

[ScrubOb]

The purpose of the assignment is to use late binding. Is that correct?

[poteto]

I don't think you can even use polymorphism here (unless the array is the polymorphic object, but then you would need to have an abstract array type).

I think what you need is composition, which is like C style of inheritance where instead of overloading the parent, you put the parent into an object and call it directly.

Since std::queue only uses the 2nd template overload to be equal to deque, but that could be a vector or list or anything. But that does not mean it uses polymorphism. The array is meerly an object inside the class and uses functions that all those lists have using template magic.

In this example you don't need a template, you can just create a array inside the queue or stack, and use it however you need it.

[dhayden]

Please post the full assignment. I suspect there is more here than what you've stated. Maybe something that you think is trivial is actually important.

[ScrubOb]

"Dynamic binding inheritance

Define an inheriting system that can inherit a class called “DataStructure”, this class will include virtual functions from the list below to serve different data structures. The suggested data structures are listed below:
1. MyArray.
2. Stack.
3. Queue.
4. Single Linked list.
5. Doubly linked list.
6. Binary tree.
7. Hashing.

Based on the structured above there are standard functionalities can be used with these structures, some of them can be common methods, and the others can be specific for certain structure(s), the functionalities (Methods) can be as shown below:
1. Initialize.
2. IsFull
3. IsEmpty
4. Insert
5. Delete
6. Push
7. Pop
8. ShowElement
9. ShowAll
10. ClearAll.
11. DeleteStruct
12. Etc…

In your design, you do not need to implement the functionalities rather than have an empty function for a future implementation.

Task Mark allocated

Classes definitions: 50
DataStructure class: 10
MyArray class: 5
Stack class: 5
Queue class: 5
SingleLinkedList class: 5
DoublyLinkedList class: 5
BinaryTree class: 5
Hashing class: 5

Virtual function design: 20
Normal virtual function in classes: 8
Pure virtual functions in classes: 8
Extra functions added: 4
Constructors in classes: 20
7 constructors - excluding DataStructure class: 4-5
Extra supporting classes: 6

This assignment is due on Friday, 24th."

[tpb]

So it was due yesterday?

Anyway, as you can see, the assignment doesn't say that you are supposed to derive "Stack" from "MyArray". It says that they are both supposed to be derived from DataStructure.

Still, the assignment is idiotic. There is no reason for these wildly different data structures to have a common base class.

[ScrubOb]

Yes, it was due yesterday.

My prof said that the myArray and SingleLinkedList classes are intended to inherit DataStructure. The myArray class is then inherited by Stack, Queue and Hashing.
DoublyLinkedList is meant to a derived class from SingleLinkedList.

[dhayden]

Here's an example that I came up with. If I'm reading the assignment right, you do NOT have to implement all the methods of the data structures. The idea is just to see if you can define the classes in a sane way.

class DataStructure {
public:
    // Is the collection full?  Most can grow without bound so
    // the default is to return false
    virtual bool IsFull() { return false; }

    // Is the collection empty?
    virtual bool IsEmpty() = 0;

    // Insert/delete a value. Returns success/failure
    virtual bool Insert(int val) = 0;
    virtual bool Delete(int val) = 0;

    // Print all values to the stream
    virtual void ShowAll(ostream &) = 0;

    // Clear the data structure
    virtual void ClearAll() = 0;

    virtual ~DataStructure();
};

// Array that increases
class MyArray : public DataStrture
{
public:
    MyArray(size_t cap=0) :
	capacity(cap),
	data(new int(cap)),
	size(0)
    {}
    virtual ~MyArray() { delete data; }
    // Need copy/move constructor and assignment operator

    int &operator[](size_t index) {return data[index]; }
    
    // Inherited from DataStructure
    virtual bool IsEmpty() {return size == 0; }
    virtual bool Insert(int val);    // Inserts at end of array.
    virtual bool Delete(int val);
    virtual void ShowAll(ostream &);
    virtual void ClearAll() {
	delete[] data;
	cap = size = 0;
    }
    
protected:
    size_t capacity;		// number of elements that data can hold
    size_t size;		// number of elements currently in data
    int *data;			// the data
};
    

// I'll use an array to implement a stack. Another possibility is a singly linked list
class Stack : protected MyArray
{
public:
    void Push(int val) { Insert(val); }

    // Pop the most recently inserted item. No error checking.
    int Pop() {
	return data[--size];
    }
	    
protected:
    // Hide operator[] and Delete()
    using MyArray::operator[];
    using MyArray::Delete;
};