Queue implementation using circular array

Question

I am trying to implement the queue using an array. But my implementation is not working. I couldn't find the mistake. My implementations are as follows:

class ArrayQueue[T: ClassManifest] extends Queue[T] {
private var A = new Array[T](2) // array for storing the queue elements
private var front = 0           // index of the front element in the array
private var rear = 0            // index of the rear element in the array
private var item_num = 0        // number of elements that are in the array


// when an array overflows we double the size of the array
private def grow() {            
    val B = A
    A = new Array[T](2 * B.length)
    if (front < rear) {
        for ( i <- 0 until B.length)
            A(i) = B(i)
            }
    else {
        System.arraycopy(B, rear, A, 0, B.length - rear)
        System.arraycopy(B, 0, A, B.length-rear, front)
        front = B.length - (rear - front)
        rear = 0
        }
}



def clear(): Unit = {     
    A = new Array[T](22)
    front = 0
    rear = 0
    item_num = 0 
    }


def isEmpty: Boolean = (item_num == 0) 


def head = { 
    if (isEmpty)
        throw new NoSuchElementException
    A(front)
    }


def dequeue(): T = {    
    if (isEmpty)
        throw new NoSuchElementException    
    front += 1  
    item_num = item_num - 1
    A(front - 1)


}

def enqueue(elem: T): Unit = {  

    A(rear) = elem
    rear += 1
    item_num += 1 
    if (rear == A.length - 1 && item_num != A.length)
        rear = 0
    if (item_num == A.length || rear == front - 1) {
        grow()
        }
    if (item_num == 0) {
        front = 0 
        rear = 0 }


    }

Queue has 5 methods including enqueue, dequeue, isEmpty, clear, head.
In my code head method returns the element at front position
isEmpty returns true if item_num = 0
Clear method clears the queue
Method enqueue must add elements after rear and increase the rear by 1. I think I have some mistake here
Method dequeue returns the first element and removes it. However, I am having an error. Can you please tell me some hints? Thank you in advance.

The best way to confirm that code is working/not-working is to write and run a unit test.. — denis.solonenko
– denis.solonenko, Commented Oct 19, 2011 at 11:27
I think that I am having some problem with enqueue, but I cannot figure out where exactly it is. I am trying unit test. The problem occurs whenever I try to enqueue elements after dequeueing. — user1002579
– user1002579, Commented Oct 19, 2011 at 11:39
Why do you think you have an error? What do you think should work that is not working? And what are your test cases, and what result are they returning? — Daniel C. Sobral
– Daniel C. Sobral, Commented Oct 19, 2011 at 11:43
I think the main problem with my code is in enqueue, because may be I am not updating the item_num correctly and def enqueue is not enqueueing elements in the circular style. — user1002579
– user1002579, Commented Oct 19, 2011 at 11:55

Daniel C. Sobral · Accepted Answer · 2011-10-19 11:51:16Z

3

To put it simply, in a circular array, whenever a pointer moves, you have to check it and fix it if necessary. You don't do that in dequeue.

The logic inside enqueue is not correct either.

Finally, you have two pointers and a counter. You shouldn't need three things, only two.

answered Oct 19, 2011 at 11:51

Daniel C. Sobral

298k88 gold badges508 silver badges688 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Abhinav · Accepted Answer · 2011-10-19 12:05:39Z

3

There are lots of logical errors. Its hard to find any correct thing implemented in your code.

trying answering following

(1) do you really need to do front = B.length - (rear - front) inside grow() when you already know that grow()is called when the array/queue is full
(2) in case if the if() condition evaluates to true, what are you doing?
let say initially A=[1 2 3 4], front =3, rear =2, then your new array will be [1 2 3 4 0 0 0 0] with same front and rear values. Is it valid?
(3) check the enque and deque logics also.
(4) consider serialization of the queue data otherwise it will go in an inconsistent state.
(5) to ease, you can simply use rear = (rear+1)%length no need to check,no ifs needed.

answered Oct 19, 2011 at 12:05

Abhinav

1,4903 gold badges15 silver badges32 bronze badges

Comments

VIKASH SINHA · Accepted Answer · 2014-09-13 01:34:20Z

I am posting the complete code here to implement circular queue using array in java. trim(): trim the size of array.

package com.java.util.collection.advance.datastructure.queue;

public interface Queue<E>{


    boolean addR(E e);


    E removeL();


    E element();


    boolean isFull();


    boolean isEmpty();

    void trim();
}



package com.java.util.collection.advance.datastructure.queue;

public interface CircularQueue<E> extends Queue<E>{

}


package com.java.util.collection.advance.datastructure.queue;

import java.util.Arrays;

public class MyCircularQueue<E> implements CircularQueue<E>{

    private int front = 0;
    private int rear =-1;
    private E[] elements =null;
    private static final int DEFAULT_INTIAL_CAPACITY =100; 
    private int size =0;

    public MyCircularQueue(){
        this(DEFAULT_INTIAL_CAPACITY);
    }
    @SuppressWarnings("unchecked")
    public MyCircularQueue(int intialCapacity){
        if(intialCapacity < 0){
            throw new IllegalArgumentException("intial capacity can't be null");
        }
        elements =(E[]) new Object[intialCapacity];
    }
    @Override
    public boolean addR(E e) {
        if(! isFull()) {
            rear = (rear+1)%elements.length;
            elements[rear] = e;
            size++;
            return true;
        }
        return false;
    }



    @Override
    public E removeL() {
        E element =null;
        if(!isEmpty()){
            if(front == elements.length-1)
            {
                front =(front+1)%elements.length;
            } 
            element=elements[front];
            // Nullify the reference
            elements[front] =null;
            front++;
            --size;
        }
        return element;
    }

    @Override
    public E element() {
        E element =null;
        if(!isEmpty()){
            element=elements[front];
        }
        return element;
    }

    @Override
    public boolean isFull() {
        return size == elements.length;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    // Do Nothing
    public void trim() {
        @SuppressWarnings("unchecked")
        E[]dest =(E[]) new Object[size];
        if(front < rear) {
            System.arraycopy(elements, front, dest, front-1,rear);
        } else {
            System.arraycopy(elements, front, dest, 0, size-front+1);
            System.arraycopy(elements, 0, dest, size-front+1, front-rear);
            front =0;
            rear = size;
        }
        elements =dest;
    }
    @Override
    public String toString() {
        return "MyCircularQueue [front=" + front + ", rear=" + rear
                + ", elements=" + Arrays.toString(elements) + ", size=" + size
                + "]";
    }



}

Test class:

package com.java.util.collection.advance.datastructure.queue;

import java.util.Random;

public class MyCircularQueueApp<E> {

    public static void main(String[] args) {

        CircularQueue<Integer> cirQueue =new MyCircularQueue<Integer>(11);
        Random random =new Random();
        for(int i=0;i<10;i++){
            cirQueue.addR(random.nextInt(3));
        }

        System.out.println(cirQueue);
        cirQueue.removeL();
        System.out.println("Before triming: "+cirQueue);
        cirQueue.trim();
        System.out.println("After triming: "+cirQueue);
        cirQueue.removeL();

        System.out.println(cirQueue);
        cirQueue.addR(1000);
        System.out.println(cirQueue);
        cirQueue.addR(10000);
        cirQueue.addR(100000);
        System.out.println(cirQueue);
        System.out.println(cirQueue.element());
    }
}

Output:

MyCircularQueue [front=0, rear=9, elements=[1, 2, 2, 2, 1, 2, 2, 1, 2, 1, null], size=10]
Before triming: MyCircularQueue [front=1, rear=9, elements=[null, 2, 2, 2, 1, 2, 2, 1, 2, 1, null], size=9]
After triming: MyCircularQueue [front=1, rear=9, elements=[2, 2, 2, 1, 2, 2, 1, 2, 1], size=9]
MyCircularQueue [front=2, rear=9, elements=[2, null, 2, 1, 2, 2, 1, 2, 1], size=8]
MyCircularQueue [front=2, rear=1, elements=[2, 1000, 2, 1, 2, 2, 1, 2, 1], size=9]
MyCircularQueue [front=2, rear=1, elements=[2, 1000, 2, 1, 2, 2, 1, 2, 1], size=9]

Your code formatting is off. Put four spaces in front of all code to get it into the code blocks, and try putting ">" in front of output to format the text there too.
Control-Shift-F to format code in Eclipse. But DanM is talking about SO formatting, not Eclipse. Bummi has done it for you though.

Collectives™ on Stack Overflow

Queue implementation using circular array

3 Answers 3

Comments

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related