Solved

sample code needed

Posted on 1998-08-16
19
239 Views
Last Modified: 2010-03-30
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
Comment
Question by:Soth
19 Comments
 
LVL 3

Expert Comment

by:sailwind
ID: 1219723
When you say a double-ended queue, do you mean a circular queue?

0
 

Author Comment

by:Soth
ID: 1219724
*Not* a circular ended queue.


0
 
LVL 2

Expert Comment

by:threshold
ID: 1219725
What's the double-ended queue?
Is it the first-in-first-out buffer?
0
 
LVL 6

Accepted Solution

by:
gadio earned 590 total points
ID: 1219726
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
 
LVL 4

Expert Comment

by:evijay
ID: 1219727
You can find dqueues and many other useful stuff at this page

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


0
 

Author Comment

by:Soth
ID: 1219728
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
 
LVL 6

Expert Comment

by:gadio
ID: 1219729
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
 

Author Comment

by:Soth
ID: 1219730
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
 

Author Comment

by:Soth
ID: 1219731
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
Top 6 Sources for Identifying Threat Actor TTPs

Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

 

Author Comment

by:Soth
ID: 1219732
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
 

Author Comment

by:Soth
ID: 1219733
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
 

Author Comment

by:Soth
ID: 1219734
I really need this answered now..
I'll give u another day b4 i'll have to move on.
0
 
LVL 6

Expert Comment

by:gadio
ID: 1219735
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
 

Author Comment

by:Soth
ID: 1219736
ok thanx
sorry to be impatient..
i'm on a "learn java in a week or die" campaign...
and interfaces really confuse me
:)
0
 
LVL 6

Expert Comment

by:gadio
ID: 1219737
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
 
LVL 6

Expert Comment

by:gadio
ID: 1219738
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
 

Author Comment

by:Soth
ID: 1219739
Yes!

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

0
 

Author Comment

by:Soth
ID: 1219740
Works like a charm!
Thanks HEAPS for ya help!
0
 
LVL 6

Expert Comment

by:gadio
ID: 1219741
You welcome. I would still recomend you to improve the implementation for better time performance.
Good luck,
G.

0

Featured Post

Better Security Awareness With Threat Intelligence

See how one of the leading financial services organizations uses Recorded Future as part of a holistic threat intelligence program to promote security awareness and proactively and efficiently identify threats.

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
array6 challenfge 6 63
allStar challenge 1 41
word0 challenge 3 58
unix in java example 9 43
For customizing the look of your lightweight component and making it look opaque like it was made of plastic.  This tip assumes your component to be of rectangular shape and completely opaque.   (CODE)
Java Flight Recorder and Java Mission Control together create a complete tool chain to continuously collect low level and detailed runtime information enabling after-the-fact incident analysis. Java Flight Recorder is a profiling and event collectio…
Viewers will learn about basic arrays, how to declare them, and how to use them. Introduction and definition: Declare an array and cover the syntax of declaring them: Initialize every index in the created array: Example/Features of a basic arr…
This tutorial covers a practical example of lazy loading technique and early loading technique in a Singleton Design Pattern.

760 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

17 Experts available now in Live!

Get 1:1 Help Now