Skip to content

Instantly share code, notes, and snippets.

@mourjo
Last active July 10, 2017 06:36
Show Gist options
  • Save mourjo/ded2acddff3ac86a5855df04a263e4f4 to your computer and use it in GitHub Desktop.
Save mourjo/ded2acddff3ac86a5855df04a263e4f4 to your computer and use it in GitHub Desktop.
Array backed queue
package arraybackedqueue;
import java.util.LinkedList;
import java.util.Random;
public class Queue {
private int head;
private int tail;
private int data[];
private int capacity;
public Queue(int capacity) {
head = 0;
tail = 0;
// Handle usage of wrapping-around head and tail by using n+1 size
data = new int[capacity+1];
this.capacity = capacity;
}
public int dequeue() throws IllegalAccessException {
if (isEmpty())
throw new IllegalAccessException("Underflow");
int itemIdx = tail;
tail = (tail + 1) % data.length;
return data[itemIdx];
}
public void enqueue(int item) throws IllegalAccessException {
if (isFull())
throw new IllegalAccessException("Overflow");
data[head] = item;
head = (head + 1) % data.length;
}
public int capacity() {
return capacity;
}
public int length() {
if (tail <= head)
return head - tail;
return data.length - tail + head;
}
public boolean isEmpty() {
return head == tail;
}
public boolean isFull() {
return length() == capacity;
}
public int get(int idx) throws IllegalAccessException {
if (idx >= length())
throw new IllegalAccessException("Out of bounds");
return data[(tail+idx) % data.length];
}
@Override
public String toString() {
StringBuffer s = new StringBuffer();
try {
s.append("[");
for(int i = 0; i < length(); i++) {
s.append(get(i));
s.append(" ");
}
s.append("]");
} catch (IllegalAccessException e) {}
return s.toString();
}
public static void main(String[] args) throws IllegalAccessException {
// test : compare with the queue interface of Java's collection library
for (int k = 100000; k >= 0; k--) {
Random r = new Random();
int c = r.nextInt(10000);
java.util.Queue<Integer> control = new LinkedList<Integer>();
Queue test = new Queue(c);
// perform some operations ...
for (int i = 0; i < r.nextInt(10000); i++)
{
try {
if (r.nextBoolean()) {
test.enqueue(i);
control.add(i);
}
else {
if (test.dequeue() != control.remove())
throw new AssertionError();
}
}
catch (IllegalAccessException e)
{
// if the test was an underflow, then the control must be empty
if (e.getMessage().equals("Underflow") && !control.isEmpty())
throw new AssertionError();
// if the test was an overflow, number of elements in the control must be full
if (e.getMessage().equals("Overflow") && control.size() != c)
throw new AssertionError();
}
}
// validate contents in test with control
for (int item : control){
if (item != test.dequeue())
throw new AssertionError();
}
if (!test.isEmpty())
throw new AssertionError();
}
System.out.println("Tests passed!");
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment