Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 2 of 2

Thread: help with deque implementation using arrays in java

  1. #1
    Junior Member
    Join Date
    May 2011
    Posts
    3
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default help with deque implementation using arrays in java

    I did an implementation of a double ended queue using arrays. I thought everything works but it stops working correctly when I removeRight() and then insertleft() it gives me bad out put.
    this is my main :

    dqueue mydq = new dqueue();
            mydq.insertRight(1);
            mydq.insertRight(2);
            mydq.insertRight(3);
            mydq.insertRight(4);
            mydq.insertRight(5);
            mydq.display();
            mydq.insertLeft(0);
            mydq.insertLeft(-1);
            mydq.display();
            mydq.removeLeft();
            mydq.display();
            mydq.insertLeft(-1);
            mydq.display();

    this is the output:
    1 2 3 4 5
    -1 0 1 2 3 4 5
    0 1 2 3 4 5
    -1 0 1 2 3 4 -1

    if I only insert from left it works fine but when I remove from left and insert from left again thats when it stops working right.

    my code is:

    private int theSize;                  //Number of elements in the array.
        private int front;                    //Index of the front element.    
        private int rear;                     //Index of the rear element.
        private AnyType [] items;             //Array dequeue
     
        public dqueue()                       //Constructor
        {
            items = (AnyType[]) new Object[5];
            front = 0;
            rear = -1;
            theSize = 0; 
        }
     
        //Insert an item from the rear of the dequeque.
        public void insertRight(AnyType x)
        {   
            if(theSize == items.length)
            {
                grow();
            }
            rear = increment(rear);
            items[ rear ] = x;
            theSize++;
        }
     
        //Insert an item from the front of the dequeque.
        public void insertLeft(AnyType x)
        {   
            if(theSize == items.length)
            {
                grow();
            }
            rear = increment(rear);
            theSize++;
            AnyType[] temp =(AnyType[]) new Object[theSize];
     
            for(int i = 0; i < theSize - 1; i++)
            {
                    temp[i + 1] = items[i];
                    for(int j = i + 1; j < theSize; j++)
                    {
                        temp[j] = items[j - 1];
                    }
                    items = temp;
                    break;
            }
            items[0]=x;
        } 
     
        public void grow()    //Method to double the array. 
        {
            AnyType[] temp = (AnyType[]) new Object[items.length * 2];
              //Copy elements that are in the dequeue
            for(int i = 0; i < theSize; i++, front = increment( front ))
            {
                temp[i] = items[front];
            }
            items = temp;
            front = 0;
            rear = theSize - 1;
        }
     
       public AnyType removeLeft()   //Take item from front of queue
       {
            AnyType temp = items[front++]; // get value and incr front
            if(front == items.length) 
            front = 0;
            theSize --; // one less item
            return temp;
       }
     
       public AnyType removeRight() //Take item from rear of queue
       {
            AnyType temp = items[rear--]; // get value and decr rear
            if(rear == -1)  
            rear = theSize -1;
            theSize --; // one less item
            return temp;
       }
     
       public void display()  //Display the elements in the dequeue.
       {
            int j = front;
            for (int count = 0; count < theSize; count++) 
            {
                System.out.print(items[j] + "  ");
                j = increment(j);
            }
            System.out.println();
        }
     
        private int increment(int i) //Internal method to increment.
        {
            if (i == items.length - 1)
            return 0;
            return ++i;
        }
     
        public AnyType first()      //The first item in the front of the dequeue.          
        {
            if(isEmpty())
            {
               System.err.println("Dequeue empty");
            }
            return items[front];
        }
     
        public AnyType last()       //The last item inserted from rear of dequeue. 
        {
            if(isEmpty())
            {
               System.err.println("Dequeue empty");
            }
            return items[rear];
        }
     
        public int size()           //Number of items in dequeue.
        {
            return theSize;
        }
     
        public boolean isEmpty()    // True if dequeue is empty.
        {
            return (theSize ==0);
        }

    please I really need help... working a long time on this and cant figure it


  2. #2
    Grand Poobah
    Join Date
    Mar 2011
    Posts
    1,514
    My Mood
    Grumpy
    Thanks
    0
    Thanked 165 Times in 156 Posts

    Default Re: help with deque implementation using arrays in java

    Personally I would dump the front and rear variables. Variable theSize should be keeping track of the next available slot when inserting on the right and inserting on the left is always at 0. So i see no need for them, especially in the grow method where each time around the loop you increment front and then at the end you reset it back to 0. Totally pointless.

    As far as I can see your removeLeft method doesn't actually remove the value at index 0. You need to have all the elements after the first copied down one index.

Similar Threads

  1. New To Java (Help with arrays)
    By SilentPirate in forum What's Wrong With My Code?
    Replies: 6
    Last Post: September 16th, 2010, 05:48 AM
  2. java newbie..simple mail server implementation
    By saurabh4dudes in forum Java Networking
    Replies: 0
    Last Post: March 12th, 2010, 07:53 AM
  3. Interface Implementation
    By Samyx in forum Object Oriented Programming
    Replies: 1
    Last Post: December 2nd, 2009, 02:46 AM
  4. Help wih implementation...
    By Frank_nor in forum What's Wrong With My Code?
    Replies: 4
    Last Post: November 24th, 2009, 04:43 PM
  5. B+ Tree implementation
    By programmer in forum Java Theory & Questions
    Replies: 2
    Last Post: November 15th, 2009, 04:47 PM