Last active
July 10, 2017 06:36
-
-
Save mourjo/ded2acddff3ac86a5855df04a263e4f4 to your computer and use it in GitHub Desktop.
Array backed queue
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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