http://www.cs.nyu.edu/faculty/davise/DataStructures/SampleCode/CircularArray/CircularArray.java
[CC150v5] 14.6 Implement CircularArray in Java
http://oppansource.com/queue-implementation-in-java-using-circular-array/
http://www.geeksforgeeks.org/implementation-deque-using-circular-array/
public class CircularArray<T> {
private T[] elements;
int start;
int end;
public CircularArray(T[] elts) {
elements = elts;
start = 0;
end = 0;
}
public boolean empty() { return end==start; }
public boolean full() {
return (((start==0) && end==elements.length-1) || end == start-1); }
public void add(T x) {
if (!full()) {
elements[end] = x;
end++;
if (end==elements.length) end=0;
}
}
public T first() { return elements[start]; }
public T pop() {
if (!empty()) {
T x = elements[start];
start = start+1;
if (start==elements.length) start=0;
return x;
}
else return null;
}
public String toString() {
String S = "[";
for (int i = start; i!=end; ) {
S = S + elements[i].toString() + " ";
i++;
if (i==elements.length) i=0;
}
return S+"]";
}
}
Implement a CircularArray class that supports an array-like data structure which can be efficiently rotated.
The class should use a generic type, and should support iteration via the standard for (Object : circuLarArray) notation.
public class MyCircularArray<T> implements Iterable<T> {
T[] items;
int head;
int cur;
public MyCircularArray(int size) {
// this is really important (casting the type)
items = (T[]) new Object[size];
head = 0;
cur = 0;
}
public void put(T item) {
items[cur++] = item;
cur = cur % items.length;
}
public T get(int i) {
int newIndex = (i + head) % items.length;
return items[newIndex];
}
public void rotate(int shiftRight) {
head += shiftRight;
head = head % items.length;
}
@Override
public Iterator<T> iterator() {
return new MyIterator<T>(this);
}
class MyIterator<T> implements Iterator<T> {
T[] items;
int head;
int count;
public MyIterator(MyCircularArray<T> array) {
this.items = array.items;
this.head = array.head;
this.count = 0;
}
@Override
public boolean hasNext() {
return this.count != items.length;
}
@Override
public T next() {
if (hasNext()) {
return items[(head + count++) % items.length];
}
return null;
}
@Override
public void remove() {
}
}
}http://oppansource.com/queue-implementation-in-java-using-circular-array/
public class CircularArrayQueue implements Queue{ private static final int capacity = 5; private Object[] Q; private final int N; // capacity private int f = 0; private int r = 0; public CircularArrayQueue(){ this(capacity); } public CircularArrayQueue(int capacity){ N = capacity; Q = new Object[N]; } public int size() { if(r > f) return r - f; return N - f + r; } public boolean isEmpty() { return (r == f) ? true : false; } public boolean isFull() { int diff = r - f; if(diff == -1 || diff == (N -1)) return true; return false; } public void enqueue(Object obj) throws QueueFullException { if(isFull()){ throw new QueueFullException("Queue is Full."); }else{ Q[r] = obj; r = (r + 1) % N; } } public Object dequeue() throws QueueEmptyException { Object item; if(isEmpty()){ throw new QueueEmptyException(); }else{ item = Q[f]; Q[f] = null; f = (f + 1) % N; } return item; }}class Deque{ int arr[MAX]; int front; int rear; int size;public : Deque(int size) { front = -1; rear = 0; this->size = size; } // Operations on Deque: void insertfront(int key); void insertrear(int key); void deletefront(); void deleterear(); bool isFull(); bool isEmpty(); int getFront(); int getRear();};// Checks whether Deque is full or not.bool Deque::isFull(){ return ((front == 0 && rear == size-1)|| front == rear+1);}// Checks whether Deque is empty or not.bool Deque::isEmpty (){ return (front == -1);}// Inserts an element at frontvoid Deque::insertfront(int key){ // check whether Deque if full or not if (isFull()) { cout << "Overflow\n" << endl; return; } // If queue is initially empty if (front == -1) { front = 0; rear = 0; } // front is at first position of queue else if (front == 0) front = size - 1 ; else // decrement front end by '1' front = front-1; // insert current element into Deque arr[front] = key ;}// function to inset element at rear end// of Deque.void Deque ::insertrear(int key){ if (isFull()) { cout << " Overflow\n " << endl; return; } // If queue is initially empty if (front == -1) { front = 0; rear = 0; } // rear is at last position of queue else if (rear == size-1) rear = 0; // increment rear end by '1' else rear = rear+1; // insert current element into Deque arr[rear] = key ;}// Deletes element at front end of Dequevoid Deque ::deletefront(){ // check whether Deque is empty or not if (isEmpty()) { cout << "Queue Underflow\n" << endl; return ; } // Deque has only one element if (front == rear) { front = -1; rear = -1; } else // back to initial position if (front == size -1) front = 0; else // increment front by '1' to remove current // front value from Deque front = front+1;}// Delete element at rear end of Dequevoid Deque::deleterear(){ if (isEmpty()) { cout << " Underflow\n" << endl ; return ; } // Deque has only one element if (front == rear) { front = -1; rear = -1; } else if (rear == 0) rear = size-1; else rear = rear-1;}// Returns front element of Dequeint Deque::getFront(){ // check whether Deque is empty or not if (isEmpty()) { cout << " Underflow\n" << endl; return -1 ; } return arr[front];}// function return rear element of Dequeint Deque::getRear(){ // check whether Deque is empty or not if(isEmpty() || rear < 0) { cout << " Underflow\n" << endl; return -1 ; } return arr[rear];}}