Type Substitution / Software Design Help

tntcoder

tntcoder

tntcoder

Soldato
Joined
7 Apr 2004
Posts
4,212
Hi,

I'm trying to revise for a uni software engineering exam in a couple of weeks, and im having some problems understanding type substitution.

Here is a question from a past exam paper:Click

Now, I hate this exam because of the vagueness between answers, there are multiple correct ones and we have to pick the 'best' answer, in this case i think the best one is A, while D is correct it isn't a reason for 'good design'.

What i don't understand is how (in the case of D) a child class can be substituted for its parent class type, when by definition a child class implements additional functionality to its parent class. So how can you substitute a child type into a parent type which doesn't understand half of its functionality? Maybe im thinking about this incorrectly in which case i hope someone can point me towards the right direction. Is this what strong typing is? :confused:

Thanks for any help
Jack
 
What a crap question, as you say the answers are so vague!

Anyway you should read up on Polymorphism as it is that which you are reffering too.

In a nutshell a derived class can be assigned (or cast) to a variable which is defined of type baseclass, with which you can only use members with a baseclass signature.
Code: 
class BaseClass {
    virtual BaseClassFunction(){}
}

class DerivedClass: BaseClass {
    override BaseClassFunction(){}
    DerivedClassFunction(){}
}

Two simple classes are defined above. Now you can use them in many ways

Code: 
BaseClass var1 = new DerviedClass();
var1.BaseClassFunction();   //will execute version of function in derivedclass
As the variable is of type baseclass you can only use the baseclass members with var1. However if the member has been overriden in the derived class it will execute that version and not the original version in the baseclass.

Hence the you can theoretically replace all instantiations of BaseClass with DerivedClass as long as the variable types stay as BaseClass, when a member is called it checks if the derived class has overriden, if so uses that version, if not uses the BaseClass version.

What if you want to use extra functionality in the dervied class that isn't in the base class you ask?

Well you have to cast the variable in to its true type.
Code: 
var2 = (DerviedClass)var1;
Now you can use:
Code: 
var2.DerivedClassFunction();

That was probably a crap explanation of polymorphism, I just wrote it as I was thinking about it, I would reccomend reading the wiki :p
 
Brilliant, thanks very much. Polymorphism was on my to learn list for another exam anyway, would have helped if i had learnt it properly before this stuff, but i think that makes sense now.

Thanks a lot for the help
 
That's a bit of a weird question :confused:

I'd say that's an example of bad design simply because a double-ended queue isn't a specialised stack. You could hack the functionality in if the Stack base class provided an interface to child classes that allowed it, but I wouldn't say it's a good way of doing things.
 
DoubleEndedQueue is an extension to Stack. It still uses a stack after all.. (both lifo and fifo)

'a' is the best answer from those, though technically all are correct in their entirety.
 
Dj_Jestar said:
It still uses a stack after all.. (both lifo and fifo)
Click to expand...

That doesn't mean it is a stack though. Double-ended queues and stacks are different data structures.

A stack is LIFO, but not FIFO; if a method receives a stack as argument, it could reasonably expect anything that goes in not to come out until everything that was pushed on after that element has been popped off again. This is not the case with a double-ended queue, and since this predicate isn't satisfied, it shouldn't be considered an extension of a stack.
 
Inquisitor said:
That doesn't mean it is a stack though. Double-ended queues and stacks are different data structures.

A stack is LIFO, but not FIFO; if a method receives a stack as argument, it could reasonably expect anything that goes in not to come out until everything that was pushed on after that element has been popped off again. This is not the case with a double-ended queue, and since this predicate isn't satisfied, it shouldn't be considered an extension of a stack.
Click to expand...

This is very true. A queue extends a stack? Someone messed up the principles here :p
 
I would say c is the best answer. In fact, this is a stupid question because a stack is completely different from a queue as Inquisitor says. A queue is a buffer (FIFO) and by combining the two as they have it confuses the two data structures and as a result could cause confusion if used in a real piece of software.
 
Ladforce said:
I would say c is the best answer. In fact, this is a stupid question because a stack is completely different from a queue as Inquisitor says. A queue is a buffer (FIFO) and by combining the two as they have it confuses the two data structures and as a result could cause confusion if used in a real piece of software.
Click to expand...

It's a real data structure - Dequeue:

http://java.sun.com/javase/6/docs/api/java/util/Deque.html

Also, I don't see why you couldn't back a Dequeue by some already implemented data structure, but only if the original data structure was built to allow it. In this case, the add to end and remove from end functionality would likely need access to the array in the Stack class, that is to say that the array would have to be protected (unless the array was given protected getters and setters to provide future extension, edit: heck actually a getter and setter would even still be wrong, you still expose the array). Protected instance variables are a bad code smell (bad design principle).

Some kind of linked data structure would be better to back a Dequeue.
 
Last edited:
Pulseammo said:
Also, I don't see why you couldn't back a Dequeue by some already implemented data structure, but only if the original data structure was built to allow it.
Click to expand...

It doesn't matter what you use to back the deque, just as long as it works properly.

However, the deque should have a Has-a relationship with the backing store, not an Is-a relationship, as is the case in the question (i.e. composition over inheritance).

Extending a class not only allows the child class to inherit properties of the parent, it also makes a fundamental statement about the child class: that it is a particular type of the parent. Since a deque is not a type of stack, inheritance should not be used.
 
Last edited:
Pulseammo said:
It's a real data structure - Dequeue:

http://java.sun.com/javase/6/docs/api/java/util/Deque.html

Also, I don't see why you couldn't back a Dequeue by some already implemented data structure, but only if the original data structure was built to allow it. In this case, the add to end and remove from end functionality would likely need access to the array in the Stack class, that is to say that the array would have to be protected (unless the array was given protected getters and setters to provide future extension, edit: heck actually a getter and setter would even still be wrong, you still expose the array). Protected instance variables are a bad code smell (bad design principle).

Some kind of linked data structure would be better to back a Dequeue.
Click to expand...

I was just making the point that a double ended queue is an extension of a queue not a stack.
 
Inquisitor said:
It doesn't matter what you use to back the deque, just as long as it works properly.

However, the deque should have a Has-a relationship with the backing store, not an Is-a relationship, as is the case in the question (i.e. composition over inheritance).

Extending a class not only allows the child class to inherit properties of the parent, it also makes a fundamental statement about the child class: that it is a particular type of the parent. Since a deque is not a type of stack, inheritance should not be used.
Click to expand...

Ladforce said:
I was just making the point that a double ended queue is an extension of a queue not a stack.
Click to expand...

I understand the Is-a Has-a argument. But to say that a Dequeue isn't a stack is a bit odd. Semantically the Dequeue IS a stack and it IS a queue. IOW Dequeue is merely a misnomer when it does the same thing as a Destack, they are both data structures that allow manipulation of both ends and nothing in the middle.

I mean, essentially what is trying to be done is that the question is trying to build an ADT that implements both a Stack and a Queue interface, and that is exactly what should have happened in the above question instead of using a concrete class like a stack as a base, there should have been two interfaces (stack and queue) and some kind of general purpose linked data structure (or array based ADT, like Inq says, the backing store shouldn't matter) which is extended and implements the correct interfaces.

I'm not saying my way is the only way of doing it, it's software engineering not an exact science, and yes, these points are prolly moot to the question. I'll cease and desist now, but maybe my points are food for thought on the question.
 
Last edited:
Pulseammo said:
I understand the Is-a Has-a argument. But to say that a Dequeue isn't a stack is a bit odd. Semantically the Dequeue IS a stack and it IS a queue. IOW Dequeue is merely a misnomer when it does the same thing as a Destack, they are both data structures that allow manipulation of both ends and nothing in the middle.

I mean, essentially what is trying to be done is that the question is trying to build an ADT that implements both a Stack and a Queue interface, and that is exactly what should have happened in the above question instead of using a concrete class like a stack as a base, there should have been two interfaces (stack and queue) and some kind of general purpose linked data structure (or array based ADT, like Inq says, the backing store shouldn't matter) which is extended and implements the correct interfaces.

I'm not saying my way is the only way of doing it, it's software engineering not an exact science, and yes, these points are prolly moot to the question. I'll cease and desist now, but maybe my points are food for thought on the question.
Click to expand...

Good explanation, I agree with what your saying. I would not have written the question as it is though as it implies that the deque is based on a stack with the functionality of both a stack and a queue.
 
Thanks again for all the help, i completly agree with it being a confusing question, hell its a confusing exam and isnt gonna be easy to pass :(
 
Pulseammo said:
I understand the Is-a Has-a argument. But to say that a Dequeue isn't a stack is a bit odd. Semantically the Dequeue IS a stack and it IS a queue. IOW Dequeue is merely a misnomer when it does the same thing as a Destack, they are both data structures that allow manipulation of both ends and nothing in the middle.

I mean, essentially what is trying to be done is that the question is trying to build an ADT that implements both a Stack and a Queue interface, and that is exactly what should have happened in the above question instead of using a concrete class like a stack as a base, there should have been two interfaces (stack and queue) and some kind of general purpose linked data structure (or array based ADT, like Inq says, the backing store shouldn't matter) which is extended and implements the correct interfaces.

I'm not saying my way is the only way of doing it, it's software engineering not an exact science, and yes, these points are prolly moot to the question. I'll cease and desist now, but maybe my points are food for thought on the question.
Click to expand...

You're right that it's a question of semantics somewhat, but IMO it's unsemantic say to a deque is a subtype of a stack since although a deque shares the behaviour of a stack, it also has behavioural elements that are completely contrary to the notion of a stack – i.e. it's also a FIFO data structure, which a stack fundamentally isn't. It also implies that a deque is more closely related to a stack than a queue, whereas it's equally related to both.

What you really need to say here in order to be properly semantic is that a deque is both LIFO and FIFO, not that it's both a stack and a queue, as these are mutually incompatible structures. The obvious approach from here it just to use interfaces: ILifoCollection and IFifoCollection.
 
Last edited:
They are not mutually incompatible.. they are the most similar behaviours available anywhere.. they've been called FIFO and LIFO stacks for years, it's only recent that "Queue" has been brought into it. As mentioned earlier, you can only access first or last elements. The *only* difference is that in one you get the first added element in the buffer, in the other you get the last. Both use pop/push - just at differing ends.
 
Dj_Jestar said:
They are not mutually incompatible.. they are the most similar behaviours available anywhere.. they've been called FIFO and LIFO stacks for years, it's only recent that "Queue" has been brought into it. As mentioned earlier, you can only access first or last elements. The *only* difference is that in one you get the first added element in the buffer, in the other you get the last. Both use pop/push - just at differing ends.
Click to expand...

Ive never heard of a FIFO stack. FIFO has always been a pipe or queue.
 
You must log in or register to reply here.
Back
Top Bottom