Skip to content

Commit c6c6fff

Browse files
iheb1196iheb1196
committed
IntQueue
1 parent a3c111b commit c6c6fff

File tree

2 files changed

+239
-0
lines changed

2 files changed

+239
-0
lines changed

‎src/main/java/com/dataStructures/IntQueue.java

Lines changed: 111 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,111 @@
1+
package com.dataStructures;
2+
3+
/**
4+
* This file contains an implementation of an integer only queue which is extremely quick and
5+
* lightweight. In terms of performance it can outperform java.util.ArrayDeque (Java's fastest queue
6+
* implementation) by a factor of 40+! See the benchmark test below for proof. However, the downside
7+
* is you need to know an upper bound on the number of elements that will be inside the queue at any
8+
* given time for this queue to work.
9+
*
10+
*
11+
*/
12+
13+
14+
public class IntQueue {
15+
16+
private int[] ar;
17+
private int front, end, sz;
18+
19+
// maxSize is the maximum number of items
20+
// that can be in the queue at any given time
21+
public IntQueue(int maxSize) {
22+
front = end = 0;
23+
sz = maxSize + 1;
24+
ar = new int[sz];
25+
}
26+
27+
// Return true/false on whether the queue is empty
28+
public boolean isEmpty() {
29+
return front == end;
30+
}
31+
32+
// Return the number of elements inside the queue
33+
public int size() {
34+
if (front > end) return (end + sz - front);
35+
return end - front;
36+
}
37+
38+
public int peek() {
39+
return ar[front];
40+
}
41+
42+
// Add an element to the queue
43+
public void enqueue(int value) {
44+
ar[end] = value;
45+
if (++end == sz) end = 0;
46+
if (end == front) throw new RuntimeException("Queue too small!");
47+
}
48+
49+
// Make sure you check is the queue is not empty before calling dequeue!
50+
public int dequeue() {
51+
int ret_val = ar[front];
52+
if (++front == sz) front = 0;
53+
return ret_val;
54+
}
55+
56+
// Example usage to check the how fast this implementation is
57+
public static void main(String[] args) {
58+
59+
IntQueue q = new IntQueue(5);
60+
61+
q.enqueue(1);
62+
q.enqueue(2);
63+
q.enqueue(3);
64+
q.enqueue(4);
65+
q.enqueue(5);
66+
67+
System.out.println(q.dequeue()); // 1
68+
System.out.println(q.dequeue()); // 2
69+
System.out.println(q.dequeue()); // 3
70+
System.out.println(q.dequeue()); // 4
71+
72+
System.out.println(q.isEmpty()); // false
73+
74+
q.enqueue(1);
75+
q.enqueue(2);
76+
q.enqueue(3);
77+
78+
System.out.println(q.dequeue()); // 5
79+
System.out.println(q.dequeue()); // 1
80+
System.out.println(q.dequeue()); // 2
81+
System.out.println(q.dequeue()); // 3
82+
83+
System.out.println(q.isEmpty()); // true
84+
85+
benchMarkTest();
86+
}
87+
88+
// BenchMark IntQueue vs ArrayDeque.
89+
private static void benchMarkTest() {
90+
91+
int n = 10000000;
92+
IntQueue intQ = new IntQueue(n);
93+
94+
// IntQueue times at around 0.0324 seconds
95+
long start = System.nanoTime();
96+
for (int i = 0; i < n; i++) intQ.enqueue(i);
97+
for (int i = 0; i < n; i++) intQ.dequeue();
98+
long end = System.nanoTime();
99+
System.out.println("IntQueue Time: " + (end - start) / 1e9);
100+
101+
// ArrayDeque times at around 1.438 seconds
102+
java.util.ArrayDeque<Integer> arrayDeque = new java.util.ArrayDeque<>();
103+
// java.util.ArrayDeque <Integer> arrayDeque = new java.util.ArrayDeque<>(n); // strangely the
104+
// ArrayQueue is slower when you give it an initial capacity.
105+
start = System.nanoTime();
106+
for (int i = 0; i < n; i++) arrayDeque.offer(i);
107+
for (int i = 0; i < n; i++) arrayDeque.poll();
108+
end = System.nanoTime();
109+
System.out.println("ArrayDeque Time: " + (end - start) / 1e9);
110+
}
111+
}

‎src/test/java/com/dataStructures/IntQueueTest.java

Lines changed: 128 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,128 @@
1+
package com.dataStructures;
2+
3+
import static org.junit.Assert.*;
4+
5+
import java.util.*;
6+
import org.junit.Before;
7+
import org.junit.Test;
8+
9+
public class IntQueueTest {
10+
11+
@Before
12+
public void setup() {}
13+
14+
@Test
15+
public void testEmptyQueue() {
16+
IntQueue queue = new IntQueue(0);
17+
assertTrue(queue.isEmpty());
18+
assertEquals(queue.size(), 0);
19+
}
20+
21+
22+
23+
@Test
24+
public void testEnqueueOneElement() {
25+
IntQueue queue = new IntQueue(1);
26+
queue.enqueue(77);
27+
assertEquals(queue.size(), 1);
28+
}
29+
30+
@Test
31+
public void testAll() {
32+
int n = 5;
33+
IntQueue queue = new IntQueue(10);
34+
assertTrue(queue.isEmpty());
35+
for (int i = 1; i <= n; i++) {
36+
queue.enqueue(i);
37+
assertFalse(queue.isEmpty());
38+
}
39+
for (int i = 1; i <= n; i++) {
40+
assertEquals(i, queue.peek());
41+
assertEquals(i, queue.dequeue());
42+
assertEquals(queue.size(), n - i);
43+
}
44+
assertTrue(queue.isEmpty());
45+
n = 8;
46+
for (int i = 1; i <= n; i++) {
47+
queue.enqueue(i);
48+
assertFalse(queue.isEmpty());
49+
}
50+
for (int i = 1; i <= n; i++) {
51+
assertEquals(i, queue.peek());
52+
assertEquals(i, queue.dequeue());
53+
assertEquals(queue.size(), n - i);
54+
}
55+
assertTrue(queue.isEmpty());
56+
n = 9;
57+
for (int i = 1; i <= n; i++) {
58+
queue.enqueue(i);
59+
assertFalse(queue.isEmpty());
60+
}
61+
for (int i = 1; i <= n; i++) {
62+
assertEquals(i, queue.peek());
63+
assertEquals(i, queue.dequeue());
64+
assertEquals(queue.size(), n - i);
65+
}
66+
assertTrue(queue.isEmpty());
67+
n = 10;
68+
for (int i = 1; i <= n; i++) {
69+
queue.enqueue(i);
70+
assertFalse(queue.isEmpty());
71+
}
72+
for (int i = 1; i <= n; i++) {
73+
assertEquals(i, queue.peek());
74+
assertEquals(i, queue.dequeue());
75+
assertEquals(queue.size(), n - i);
76+
}
77+
assertTrue(queue.isEmpty());
78+
}
79+
80+
@Test
81+
public void testPeekOneElement() {
82+
IntQueue queue = new IntQueue(1);
83+
queue.enqueue(77);
84+
assertTrue(queue.peek() == 77);
85+
assertEquals(queue.size(), 1);
86+
}
87+
88+
@Test
89+
public void testDequeueOneElement() {
90+
IntQueue queue = new IntQueue(1);
91+
queue.enqueue(77);
92+
assertTrue(queue.dequeue() == 77);
93+
assertEquals(queue.size(), 0);
94+
}
95+
96+
@Test
97+
public void testRandom() {
98+
99+
for (int qSize = 1; qSize <= 50; qSize++) {
100+
101+
IntQueue intQ = new IntQueue(qSize);
102+
ArrayDeque<Integer> javaQ = new ArrayDeque<>(qSize);
103+
104+
assertEquals(javaQ.isEmpty(), intQ.isEmpty());
105+
assertEquals(javaQ.size(), intQ.size());
106+
107+
for (int operations = 0; operations < 5000; operations++) {
108+
109+
double r = Math.random();
110+
111+
if (r < 0.60) {
112+
int elem = (int) (1000 * Math.random());
113+
if (javaQ.size() < qSize) {
114+
javaQ.offer(elem);
115+
intQ.enqueue(elem);
116+
}
117+
} else {
118+
if (!javaQ.isEmpty()) {
119+
assertEquals((int) javaQ.poll(), (int) intQ.dequeue());
120+
}
121+
}
122+
123+
assertEquals(javaQ.isEmpty(), intQ.isEmpty());
124+
assertEquals(javaQ.size(), intQ.size());
125+
}
126+
}
127+
}
128+
}

0 commit comments

Comments
 (0)