• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 290
  • Last Modified:

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
0
Soth
Asked:
Soth
1 Solution
 
sailwindCommented:
When you say a double-ended queue, do you mean a circular queue?

0
 
SothAuthor Commented:
*Not* a circular ended queue.


0
 
thresholdCommented:
What's the double-ended queue?
Is it the first-in-first-out buffer?
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
gadioCommented:
heres a piece of code for you. Hope it helps, feel free to ask and questions. Note that the main runs a test program.
Regards, G.

--- file: dqueue.java ----


public class dqueue {
    item first;
    item last;

    /**
     * Constructor.
     */
    public dqueue () {
        first = null;
        last = null;
    }

    public void insert( item i, boolean at_start ) {
        if( at_start ) {
            i.attach( null, first );
            first = i;
            if( last == null ) last = i;
        }
        else {
            i.attach( last, null );
            last = i;
            if( first == null ) first = i;
        }
    }

    item pop( boolean from_start ) {
        item res;
        if( from_start ) {
            res = first;
            first = res.next;
            res.detach();
        }
        else {
            res = last;
            last = res.prev;
            res.detach();
        }
        if( first == null || last == null ) {
            first = null;
            last = null;
        }
        return res;
    }

    public boolean isEmpty() {
        return (first == null && last == null);
    }

    public void show() {

        for( item i = first; i != null; i = i.next ) {
            System.out.println( "Item: "+i );
        }
    }

    public static void main(String args[]) {
        dqueue dq = new dqueue();
        System.out.println("Test prog");
        System.out.println("empty:");
        dq.show();
        dq.insert( new intItem(101), true );
        dq.insert( new intItem(102), true );
        dq.insert( new intItem(103), true );
        dq.insert( new intItem(104), false );
        dq.insert( new intItem(105), false );
        System.out.println("Numbers:");
        dq.show();
        dq.insert( new charItem('A'), false );
        dq.insert( new charItem('B'), false );
        dq.insert( new charItem('C'), false );
        dq.insert( new charItem('D'), true );
        dq.insert( new charItem('E'), true );
        System.out.println("Numbers and chars:");
        dq.show();
        dq.insert( new boolItem(true), false );
        dq.insert( new boolItem(false), true );
        System.out.println("Numbers, chars and booleans:");
        dq.show();
        while( !dq.isEmpty() ) {
            item i = dq.pop( true );
            if(i instanceof intItem) System.out.println( "Poped int: "+((intItem)i).getValue() );
            if(i instanceof charItem) System.out.println( "Poped char: "+((charItem)i).getValue() );
            if(i instanceof boolItem) System.out.println( "Poped boolean: "+((boolItem)i).getValue() );
        }
    }
}


class item {
    item prev;
    item next;

    public void attach( item prev, item next ) {
        this.prev = prev;
        this.next = next;
        if( prev != null ) prev.next = this;
        if( next != null ) next.prev = this;
    }

    public void detach() {
        if( prev != null ) prev.next = this.next;
        if( next != null ) next.prev = this.prev;
    }
}

class intItem extends item {
    int data;

    public intItem( int data ) {
        setValue( data );
    }

    public void setValue( int data ) {
        this.data = data;
    }

    public int getValue() {
        return data;
    }

    public String toString() {
        return String.valueOf(data);
    }
}

class boolItem extends item {
    boolean data;

    public boolItem( boolean data ) {
        setValue( data );
    }

    public void setValue( boolean data ) {
        this.data = data;
    }

    public boolean getValue() {
        return data;
    }

    public String toString() {
        return String.valueOf(data);
    }
}

class charItem extends item {
    char data;

    public charItem( char data ) {
        setValue( data );
    }

    public void setValue( char data ) {
        this.data = data;
    }

    public char getValue() {
        return data;
    }

    public String toString() {
        return String.valueOf(data);
    }
}


0
 
evijayCommented:
You can find dqueues and many other useful stuff at this page

www.acme.com/resources/classes/Acme.tar.Z


0
 
SothAuthor Commented:
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;
            
      }
      
      
}

0
 
gadioCommented:
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.

0
 
SothAuthor Commented:
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.
0
 
SothAuthor Commented:
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(((ThingNode)ls).item);
                  ls = nextNode(ls);
                  
            }
            
      }

}


0
 
SothAuthor Commented:
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


0
 
SothAuthor Commented:
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
0
 
SothAuthor Commented:
I really need this answered now..
I'll give u another day b4 i'll have to move on.
0
 
gadioCommented:
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.
0
 
SothAuthor Commented:
ok thanx
sorry to be impatient..
i'm on a "learn java in a week or die" campaign...
and interfaces really confuse me
:)
0
 
gadioCommented:
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?

0
 
gadioCommented:
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?
0
 
SothAuthor Commented:
Yes!

i think i've got it now... i'll get back to u soon

0
 
SothAuthor Commented:
Works like a charm!
Thanks HEAPS for ya help!
0
 
gadioCommented:
You welcome. I would still recomend you to improve the implementation for better time performance.
Good luck,
G.

0

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now