Soth
asked on
sample code needed
I would like to see some code which models a double-ended queue. This might seem simple at first but the queue must be able to support int, char and boolean types all at once within the queue. I do not want the queue of Object. Utilising interfaces would be preferable to abstract classes...
I have made this worth many points because i want code.. not explanation :)
Thanks!
Chris
I have made this worth many points because i want code.. not explanation :)
Thanks!
Chris
When you say a double-ended queue, do you mean a circular queue?
ASKER
*Not* a circular ended queue.
What's the double-ended queue?
Is it the first-in-first-out buffer?
Is it the first-in-first-out buffer?
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
You can find dqueues and many other useful stuff at this page
www.acme.com/resources/classes/Acme.tar.Z
www.acme.com/resources/classes/Acme.tar.Z
ASKER
Ok, I tried that and it worked great!
*BUT*
Below I have two files (GenNode.java and GenDEQueue.java).
Now, I have been told that I can make an
interface called Thing which has a show method
(but no data members). I would then have to write
a class called ThingNode which extends GenNode.
I would then write a ThingDEQueue class which
contains ThingNodes and which extends GenDEQueue.
Now i would implement Thing as int, char and boolean
and insert them into ThingDEQueue.
Could you write some code to show me
how this is done and how it works.
I have added the rest of my points in my a/c for this question.
thanx!
Chris.
**************************
/* GenNode.java */
package GenDEQueue;
public class GenNode
{
GenNode next;
}
**************************
GenDEQueue.java
package GenDEQueue;
public class GenDEQueue
{
private GenNode start = null;
private GenNode end = null;
public boolean isEmpty()
{
return(start == null);
}
public void addStart(GenNode ls)
{
ls.next = start;
if(start == null)
{
end = ls;
}
start = ls;
}
public GenNode removeStart(GenNode ls)
{
ls = start;
if(start == end)
{
start = null;
end = null;
}
else
{
start = start.next;
}
return(ls);
}
public void addEnd(GenNode ls)
{
ls.next = null;
if(start == null)
{
start = ls;
}
else
{
end.next = ls;
}
end = ls;
}
public GenNode removeEnd(GenNode ls)
{
ls = end;
if (start == end)
{
start = null;
end = null;
}
else
{
end = start;
while(end.next != ls)
{
end = end.next;
}
end.next = null;
}
return(ls);
}
public GenNode nextNode(GenNode ls)
{
if(ls==null)
{
return start;
}
return ls.next;
}
}
*BUT*
Below I have two files (GenNode.java and GenDEQueue.java).
Now, I have been told that I can make an
interface called Thing which has a show method
(but no data members). I would then have to write
a class called ThingNode which extends GenNode.
I would then write a ThingDEQueue class which
contains ThingNodes and which extends GenDEQueue.
Now i would implement Thing as int, char and boolean
and insert them into ThingDEQueue.
Could you write some code to show me
how this is done and how it works.
I have added the rest of my points in my a/c for this question.
thanx!
Chris.
**************************
/* GenNode.java */
package GenDEQueue;
public class GenNode
{
GenNode next;
}
**************************
GenDEQueue.java
package GenDEQueue;
public class GenDEQueue
{
private GenNode start = null;
private GenNode end = null;
public boolean isEmpty()
{
return(start == null);
}
public void addStart(GenNode ls)
{
ls.next = start;
if(start == null)
{
end = ls;
}
start = ls;
}
public GenNode removeStart(GenNode ls)
{
ls = start;
if(start == end)
{
start = null;
end = null;
}
else
{
start = start.next;
}
return(ls);
}
public void addEnd(GenNode ls)
{
ls.next = null;
if(start == null)
{
start = ls;
}
else
{
end.next = ls;
}
end = ls;
}
public GenNode removeEnd(GenNode ls)
{
ls = end;
if (start == end)
{
start = null;
end = null;
}
else
{
end = start;
while(end.next != ls)
{
end = end.next;
}
end.next = null;
}
return(ls);
}
public GenNode nextNode(GenNode ls)
{
if(ls==null)
{
return start;
}
return ls.next;
}
}
Soth, I'd like to comment that your implementation of DQueue is a bit less efficient, because the queue is held in a one directional list. This causes asymetric performace for nodes that are added/removed to the start and to the end. While adding and removing nodes from the start will allways be o(1) (order of one operation), the adding/removing of node from the end will be o(N) where N is the amount of nodes in the queue. In simple words: if you have 1000 nodes in the queue, adding node to the end will be 1000 times slower than adding to the start! This is why my sample code is a bi-directional list implementation.
ASKER
Yes I can understand that..
I want to see *my* example work though (even though i know it is inefficient :) .. I'm having problems with interfaces and this is a good introduction to working it. If you could show how to make an interface which has a show method and then implement that interface for int char and boolean that would be excellent..
Please find time to show me.
Thanx so far!
Chris.
I want to see *my* example work though (even though i know it is inefficient :) .. I'm having problems with interfaces and this is a good introduction to working it. If you could show how to make an interface which has a show method and then implement that interface for int char and boolean that would be excellent..
Please find time to show me.
Thanx so far!
Chris.
ASKER
OK, above I gave u GenDEQueue.java and GenNode.java
now I'll give u ThingNode and ThingDEQueue...
All I have to do is implement Thing as int char and boolean and insert them into ThingDEQueue..
Using an interface called thing which has a show method how would i do this????
***************
// ThingNode.java
public class ThingNode extends GenNode
{
ThingNode item;
}
******
// ThingDEQueue.java
import java.io.*;
public class ThingDEQueue extends GenDEQueue
{
public boolean isEmpty()
{
return super.isEmpty();
}
public void putStart(ThingNode value)
{
ThingNode ls = new ThingNode();
ls.item = value;
addStart(ls);
}
public ThingNode getStart()
{
GenNode ls = null;
ThingNode val;
ls = removeStart(ls);
val = ((ThingNode)ls).item;
return val;
}
public void putEnd(ThingNode value)
{
ThingNode ls = new ThingNode();
ls.item = value;
addEnd(ls);
}
public ThingNode getEnd()
{
GenNode ls = null;
ThingNode val;
ls = removeEnd(ls);
val = ((ThingNode)ls).item;
return val;
}
public void display()
{
GenNode ls = null;
ls = nextNode(ls);
while(ls != null)
{
System.out.print(((ThingNo
ls = nextNode(ls);
}
}
}
now I'll give u ThingNode and ThingDEQueue...
All I have to do is implement Thing as int char and boolean and insert them into ThingDEQueue..
Using an interface called thing which has a show method how would i do this????
***************
// ThingNode.java
public class ThingNode extends GenNode
{
ThingNode item;
}
******
// ThingDEQueue.java
import java.io.*;
public class ThingDEQueue extends GenDEQueue
{
public boolean isEmpty()
{
return super.isEmpty();
}
public void putStart(ThingNode value)
{
ThingNode ls = new ThingNode();
ls.item = value;
addStart(ls);
}
public ThingNode getStart()
{
GenNode ls = null;
ThingNode val;
ls = removeStart(ls);
val = ((ThingNode)ls).item;
return val;
}
public void putEnd(ThingNode value)
{
ThingNode ls = new ThingNode();
ls.item = value;
addEnd(ls);
}
public ThingNode getEnd()
{
GenNode ls = null;
ThingNode val;
ls = removeEnd(ls);
val = ((ThingNode)ls).item;
return val;
}
public void display()
{
GenNode ls = null;
ls = nextNode(ls);
while(ls != null)
{
System.out.print(((ThingNo
ls = nextNode(ls);
}
}
}
ASKER
Ok,
I now have an interface Thing with a empty show method
I have ThingNode, ThingDEQueue
I now make IntNode, CharNode, BoolNode which all implement Thing
how do I do a putStart(2), putstart("x"), putstart(false) ???
it is looking for a ThingNode... i tried casting but that doesnt
work ( (ThingNode) false )
ahhhhh!.. im just a confused newbie
I now have an interface Thing with a empty show method
I have ThingNode, ThingDEQueue
I now make IntNode, CharNode, BoolNode which all implement Thing
how do I do a putStart(2), putstart("x"), putstart(false) ???
it is looking for a ThingNode... i tried casting but that doesnt
work ( (ThingNode) false )
ahhhhh!.. im just a confused newbie
ASKER
Let me rephrase what I'm looking for to try and make it easier:
I have GenDEQueue.java and GenNode.java
I then made a ThingDEQueue.java (all these r above)
Now I need a ThingNode.
So, just using ints for example:
I have the file Thing.java (interface)
***
// Thing.java
public interface Thing
{
public void show();
}
***
Now i want to implement Thing in IntThing
***
// IntThing.java
public class IntThing implements Thing
{
int Thing???
public void show()
{
// show
}
}
***
is int Thing right here???
Now i need a ThingNode
***
// ThingNode.java
public clas ThingNode extends GenNode
{
Thing item; ???
}
See what I want??
this doesnt work though
I have GenDEQueue.java and GenNode.java
I then made a ThingDEQueue.java (all these r above)
Now I need a ThingNode.
So, just using ints for example:
I have the file Thing.java (interface)
***
// Thing.java
public interface Thing
{
public void show();
}
***
Now i want to implement Thing in IntThing
***
// IntThing.java
public class IntThing implements Thing
{
int Thing???
public void show()
{
// show
}
}
***
is int Thing right here???
Now i need a ThingNode
***
// ThingNode.java
public clas ThingNode extends GenNode
{
Thing item; ???
}
See what I want??
this doesnt work though
ASKER
I really need this answered now..
I'll give u another day b4 i'll have to move on.
I'll give u another day b4 i'll have to move on.
Soth, sorry about the slow response. I just came back from a long weekend :-) ...
I'll try to answer you in a short time. I just have to go through all your sources.
I'll try to answer you in a short time. I just have to go through all your sources.
ASKER
ok thanx
sorry to be impatient..
i'm on a "learn java in a week or die" campaign...
and interfaces really confuse me
:)
sorry to be impatient..
i'm on a "learn java in a week or die" campaign...
and interfaces really confuse me
:)
soth hi.
I hope that you will make it learning it all in a week. I think its worth the effort (better then die, surely...).
As I understand the main issue here is to learn how to use interfaces. I'm not sure that this example is the best that you may use and I'll explain why. In java the base class of all object the Object class as you know. This enables you to unify the interface to a class in the case of different types of data that should be passed to it (where in C/C++ you would use the less elegant void pointer). That is one of the reasons why in java there is a class envelope to all the basic types (like Integer for int, Float for float, Double, Boolean etc.). This is not the only reason, but it is definatly a magor one. Now, by insisting not to use an objects dqueue, and not to use Object as a data passed through interface, you prevent from your interface to include all the methods. For example the reading and writing of the different types through the same interface is not possible (like you written putStart(2), putStart("helo") - this can't be done through the same interface).
We can advance on two paths: one is to stick to your definitions, and one the design it using Objects. What would you prefer?
I hope that you will make it learning it all in a week. I think its worth the effort (better then die, surely...).
As I understand the main issue here is to learn how to use interfaces. I'm not sure that this example is the best that you may use and I'll explain why. In java the base class of all object the Object class as you know. This enables you to unify the interface to a class in the case of different types of data that should be passed to it (where in C/C++ you would use the less elegant void pointer). That is one of the reasons why in java there is a class envelope to all the basic types (like Integer for int, Float for float, Double, Boolean etc.). This is not the only reason, but it is definatly a magor one. Now, by insisting not to use an objects dqueue, and not to use Object as a data passed through interface, you prevent from your interface to include all the methods. For example the reading and writing of the different types through the same interface is not possible (like you written putStart(2), putStart("helo") - this can't be done through the same interface).
We can advance on two paths: one is to stick to your definitions, and one the design it using Objects. What would you prefer?
Chris, I'll try and give you the answer according to your spec:
------------
public interface Thing {
public String show();
}
-----------
public class intThing extends GenNode implements Thing {
int data;
public intThing( int data ) {
this.data = data;
}
public String show() {
return Integer.toString(data);
}
}
--------------
and when you add, use
ThingDEQueue t = new ThingDEQueue();
t.putStart( new intThing(32) );
-------------
Is that what you ment?
------------
public interface Thing {
public String show();
}
-----------
public class intThing extends GenNode implements Thing {
int data;
public intThing( int data ) {
this.data = data;
}
public String show() {
return Integer.toString(data);
}
}
--------------
and when you add, use
ThingDEQueue t = new ThingDEQueue();
t.putStart( new intThing(32) );
-------------
Is that what you ment?
ASKER
Yes!
i think i've got it now... i'll get back to u soon
i think i've got it now... i'll get back to u soon
ASKER
Works like a charm!
Thanks HEAPS for ya help!
Thanks HEAPS for ya help!
You welcome. I would still recomend you to improve the implementation for better time performance.
Good luck,
G.
Good luck,
G.