?
Solved

sample code needed

Posted on 1998-08-16
19
Medium Priority
?
280 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
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
Get 15 Days FREE Full-Featured Trial

Benefit from a mission critical IT monitoring with Monitis Premium or get it FREE for your entry level monitoring needs.
-Over 200,000 users
-More than 300,000 websites monitored
-Used in 197 countries
-Recommended by 98% of users

 
LVL 6

Accepted Solution

by:
gadio earned 2360 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
 

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

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Java functions are among the best things for programmers to work with as Java sites can be very easy to read and prepare. Java especially simplifies many processes in the coding industry as it helps integrate many forms of technology and different d…
In this post we will learn different types of Android Layout and some basics of an Android App.
Viewers learn about the scanner class in this video and are introduced to receiving user input for their programs. Additionally, objects, conditional statements, and loops are used to help reinforce the concepts. Introduce Scanner class: Importing…
This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.
Suggested Courses
Course of the Month15 days, 15 hours left to enroll

743 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