trjhtr

I found a tutorial on implementing a deque using a circular array. I changed the implementation but I am not sure if it is correct or not.

So I have one question:

1. I wrote code that uses an addCount field to record whether there are any additions, but I'm not sure if it's correct? If not, please tell me where I made an error.

class Deque 
 static final int MAX = 100;
 int arr;
 int front;
 int rear;
 int size;
 int addCount;

 public Deque(int size) 
 arr = new int[size];
 front = 0;
 rear = 0;
 this.size = size;
 addCount = 0;
 

 // Checks whether Deque is full or not.
 boolean isFull() 

 return front == rear && !isEmpty();
 

 // Checks whether Deque is empty or not.
 boolean isEmpty() 
 return front == rear && addCount == 0;
 

 // Inserts an element at front
 void insertfront(int key) 
 if (isFull())
 return;

 addCount++;
 arr[front] = key;
 front = front + 1;
 front %= this.size;
 

 // function to inset element at rear end
 // of Deque.
 void insertrear(int key) 
 if (isFull())
 return;
 addCount++;
 rear = (rear - 1) % this.size;
 arr[rear + this.size] = key;

 

 // Deletes element at front end of Deque
 void deletefront() 
 if (isEmpty())
 return;
 addCount--;
 front = (front - 1) % this.size;
 

 // Delete element at rear end of Deque
 void deleterear() 
 if (isEmpty())
 return;
 addCount--;
 rear = (rear + 1) % this.size;
 

 // Returns front element of Deque
 int getFront() 
 int getFront = front-1;

 if (getFront < 0)
 getFront += this.size;
 return arr[getFront % this.size];
 

 // function return rear element of Deque
 int getRear() 
 int getRearIndex = rear + this.size;
 return arr[getRearIndex % this.size];
 

 // Driver program to test above function
 public static void main(String args) 
 Deque dq = new Deque(5);
 System.out.println("Insert element at rear end : 5 ");
 dq.insertrear(5);

 System.out.println("insert element at rear end : 10 ");
 dq.insertrear(10);

 System.out.println("get rear element : " + dq.getRear());

 dq.deleterear();
 System.out.println("After delete rear element new rear become : " + dq.getRear());

 System.out.println("inserting element at front end");
 dq.insertfront(15);

 System.out.println("get front element: " + dq.getFront());

 dq.deletefront();

 System.out.println("After delete front element new front become : " + +dq.getFront());

 

I do not see any problems with addCount as long as we add a disclaimer that this solution is not thread safe.

The presented solution is a collection that can only accept int items. You can expand this if you add generic parameter to the class. Note that in this case, the internal array is of Object type and you let the compiler enforce type safety and also do auto-boxing to support primitive data items, just like in Java collections library. And while we mentioned that, you might want to consider making your solution implement the Deque interface from Java collections so that clients will work with a familiar API (of course you will want to change the name of the class to reflect that it is a concrete implementation of a Deque)

Bugs

If you call insertrear() and deletefront() repeatedly, you will eventually get an array out of bounds exception. There are at least two problems:

This code in insertrear() can index past the end of the array:

 rear = (rear - 1) % this.size;
 arr[rear + this.size] = key;

If the first statement results in rear being 0, the second statement will try to access an element out of bounds.

This code in deletefront() can cause front to become negative:

 front = (front - 1) % this.size;

which will cause the next addfront() call to throw an exception because it will try to use front as an array index without fixing it.

I would recommend never letting front and rear go negative. First, this fixes your array bounds issues. Second, it also fixes an additional bug when you check front == rear and it should return true but it doesn't because one index is positive and one index is negative.

Poor testing

If you had exercised your code more, you would have caught these bugs. When writing tests for your code, you should make sure to stress it, not just do the bare minimum. For example, you should fill your queue to capacity and see what happens if you try to overfill it. You should also try every combination of filling from the front/rear with removing from the front/rear (4 separate tests at least).

With a circular buffer, you only need to keep track of two variables: writeIndex and itemCount.

• Both items are incremented when you write an item to the buffer


• 
  itemCount is decremented when you read an item from the buffer


• You calculate the read index by subtracting the itemCount from the writeIndex
  


• You transition from the bottom of the buffer to the top by using modulus math

Here are the details:

Add data to the buffer:

writeIndex = ((writeIndex + 1) % BUFFER_SIZE)
if (itemCount < BUFFER_SIZE) itemCount++;
write data to buffer[writeIndex]

Remove data from the buffer:

if (itemCount > 0) 
 readIndex = ((BUFFER_SIZE + writeIndex - itemCount + 1) % BUFFER_SIZE)
 read data from the buffer[readIndex]
 itemCount--;
}

Example:

BUFFER_SIZE = 6
writeIndex = 4
itemCount = 3

add item, new writeIndex = (4 + 1) % 6 = 5 % 6 = 5 new itemCount = 4
add item, new writeIndex = (5 + 1) % 6 = 6 % 6 = 0 new itemCount = 5
read item, new readIndex = (6+0-5+1) % 6 = 2%6 = 2 new itemCount = 4
read item, new readIndex = (6+0-4+1) % 6 = 3%6 = 3 new itemCount = 3

• % = modulus ... returns the remainder of a division


• 5%6 = 5/6, remainder 5


• 6%6 = 6/6, remainder 0

This example allows the overwriting of unread data.

Overwriting can be disabled by:

if (itemCount<BUFFER_SIZE) write logic

This example is not thread-safe. If you read and write in different threads, you'll need to add a locking mechanism to assure reading and writing operations do not occur at the same time.