factordva's Profile User Rating: -----

Reputation: 2 Apprentice
Group:
New Members
Active Posts:
8 (0.01 per day)
Joined:
08-September 12
Profile Views:
1,806
Last Active:
User is offline Jan 01 2014 11:19 AM
Currently:
Offline

Previous Fields

Dream Kudos:
0
Icon   factordva has not set their status

Posts I've Made

  1. In Topic: Queues- Arrays and Linked Lists

    Posted 28 Dec 2013

    First off, I know this is a late reply, but this post came up right away when I did a Google search for ArrayQueue implementations.
    I just started learning data structures in Java myself and found this quite helpful. I would like to add an extra feature to your queue, resizing. I find that this would be a better alternative to simply throwing a FullQueueException when enqueue-ing an item.


    Here is the portion of code I am referring to
    //Enqueue a new item in the array queue
    public void enqueue(E newItem) {
    	 //Check if the ArrayQueue is full
    	 if(this.isFull())
    		 throw new FullQueueException("Cannot enqueue, ArrayQueue is full");
    ...
    }
    
    



    Resizing can be tricky though since the queue array is circular. This is best explained through example:

    Say our array is size 5 and our front and rear are 3,2 respectively:
      0   1   2   3   4
    [10][20][40][60][90]
    


    Now, if we were to resize our queue to add another element our desired array would be

      0   1   2   3   4      5
    [60][90][10][20][40][newElement] , this way we keep the circular order of elements.
    


    Here is a solution that is actually quite simple, but requires some tricky organization. The idea is to create two variables, one that will loop over a temporary array and another looping over the circular array. We then reassign the new array to reference the old array.

    private void resize(int newCapacity){
            int j = front;
            E[] newData = (E[]) new Object[newCapacity]; //create temporary array
            for(int i=0; i<capacity-1; i++){
                newData[i]=elements[j];
                j=(j+1)%capacity;
            }
            //now all is left to do is reassign the queue variables
            front = 0;
            rear = capacity; //important to assign rear before updating for newCapacity
            capacity = newCapacity;
            elements = newData; //elements array reference newData array which has the correct order plus the new capacity
    }
    
    

    And finally, implementing the resize() method
    //Enqueue a new item in the array queue
    public void enqueue(E newItem) {
    	 //Check if the ArrayQueue is full
    	 if(this.isFull()) resize(elements.length * 2); //I double the array. Really depends on situation though. 
    		 
    ...
    }
    
    


    Thanks for your post, I know how much effort you put into it and want to thank you for that.

    Happy coding, and happy new years!

My Information

Member Title:
New D.I.C Head
Age:
Age Unknown
Birthday:
Birthday Unknown
Gender:

Contact Information

E-mail:
Click here to e-mail me

Friends

Comments

factordva has no profile comments yet. Why not say hello?