Skip to content

Commit d5f4fab

Browse files
ttskymttskym
authored
Add Array Queue Implementation and refactor IntQueue (williamfiset#190)
* add array stack * add array stack * verify google java format * array stack * array stack * fix IntQueue bugs and re-implement IntQueue, add ArrayQueue * add comment for ArrayQueue * modify the comment * fix the mod problem * fix the mod problem
1 parent bfcd6de commit d5f4fab

File tree

8 files changed

+272
-146
lines changed

8 files changed

+272
-146
lines changed

‎src/main/java/com/williamfiset/algorithms/datastructures/queue/ArrayQueue.java

Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
1+
package com.williamfiset.algorithms.datastructures.queue;
2+
3+
/**
4+
* Besides the Generics, the loss of property of size is another difference between ArrayQueue and
5+
* IntQueue. The size of ArrayQueue is calculated by the formula, as are empty status and full
6+
* status.
7+
*
8+
* <p>ArrayQueue maximum size is data.length - 1. The place of the variable rear is always in front
9+
* of the variable front logistically if regard the data array as circular. so the number of states
10+
* of the combination of rear and front is the length of the data array. And one of the total states
11+
* is used to be the judge if the queue is empty or full.
12+
*
13+
* @author liujingkun, liujkon@gmail.com
14+
*/
15+
public class ArrayQueue<T> implements Queue<T> {
16+
private Object[] data;
17+
private int front;
18+
private int rear;
19+
20+
public ArrayQueue(int capacity) {
21+
// ArrayQueue maximum size is data.length - 1.
22+
data = new Object[capacity + 1];
23+
front = 0;
24+
rear = 0;
25+
}
26+
27+
@Override
28+
public void offer(T elem) {
29+
if (isFull()) {
30+
throw new RuntimeException("Queue is full");
31+
}
32+
data[rear++] = elem;
33+
rear = adjustIndex(rear, data.length);
34+
}
35+
36+
@Override
37+
@SuppressWarnings("unchecked")
38+
public T poll() {
39+
if (isEmpty()) {
40+
throw new RuntimeException("Queue is empty");
41+
}
42+
front = adjustIndex(front, data.length);
43+
return (T) data[front++];
44+
}
45+
46+
@Override
47+
@SuppressWarnings("unchecked")
48+
public T peek() {
49+
if (isEmpty()) {
50+
throw new RuntimeException("Queue is empty");
51+
}
52+
front = adjustIndex(front, data.length);
53+
return (T) data[front];
54+
}
55+
56+
@Override
57+
public int size() {
58+
return adjustIndex(rear + data.length - front, data.length);
59+
}
60+
61+
@Override
62+
public boolean isEmpty() {
63+
return rear == front;
64+
}
65+
66+
public boolean isFull() {
67+
return (front + data.length - rear) % data.length == 1;
68+
}
69+
70+
private int adjustIndex(int index, int size) {
71+
return index >= size ? index - size : index;
72+
}
73+
}

‎src/main/java/com/williamfiset/algorithms/datastructures/queue/IntQueue.java

Lines changed: 56 additions & 40 deletions
Original file line numberDiff line numberDiff line change
@@ -5,82 +5,98 @@
55
* is you need to know an upper bound on the number of elements that will be inside the queue at any
66
* given time for this queue to work.
77
*
8-
* @author William Fiset, william.alexandre.fiset@gmail.com
8+
* @author William Fiset, william.alexandre.fiset@gmail.com, liujingkun, liujkon@gmail.com
99
*/
1010
package com.williamfiset.algorithms.datastructures.queue;
1111

12-
public class IntQueue {
12+
public class IntQueue implements Queue<Integer> {
1313

14-
private int[] ar;
15-
private int front, end, sz;
14+
private int[] data;
15+
private int front, end;
16+
private int size;
1617

1718
// maxSize is the maximum number of items
1819
// that can be in the queue at any given time
1920
public IntQueue(int maxSize) {
20-
front = end = 0;
21-
sz = maxSize + 1;
22-
ar = new int[sz];
21+
front = end = size = 0;
22+
data = new int[maxSize];
2323
}
2424

2525
// Return true/false on whether the queue is empty
2626
public boolean isEmpty() {
27-
return front == end;
27+
return size == 0;
2828
}
2929

3030
// Return the number of elements inside the queue
3131
public int size() {
32-
if (front > end) return (end + sz - front);
33-
return end - front;
32+
return size;
3433
}
3534

36-
public int peek() {
37-
return ar[front];
35+
@Override
36+
public Integer peek() {
37+
if (isEmpty()) {
38+
throw new RuntimeException("Queue is empty");
39+
}
40+
front = front % data.length;
41+
return data[front];
42+
}
43+
44+
public boolean isFull() {
45+
return size == data.length;
3846
}
3947

4048
// Add an element to the queue
41-
public void enqueue(int value) {
42-
ar[end] = value;
43-
if (++end == sz) end = 0;
44-
if (end == front) throw new RuntimeException("Queue too small!");
49+
@Override
50+
public void offer(Integer value) {
51+
if (isFull()) {
52+
throw new RuntimeException("Queue too small!");
53+
}
54+
data[end++] = value;
55+
size++;
56+
end = end % data.length;
4557
}
4658

47-
// Make sure you check is the queue is not empty before calling dequeue!
48-
public int dequeue() {
49-
int ret_val = ar[front];
50-
if (++front == sz) front = 0;
51-
return ret_val;
59+
// Make sure you check is the queue is not empty before calling poll!
60+
@Override
61+
public Integer poll() {
62+
if (size == 0) {
63+
throw new RuntimeException("Queue is empty");
64+
}
65+
size--;
66+
front = front % data.length;
67+
return data[front++];
5268
}
5369

5470
// Example usage
5571
public static void main(String[] args) {
5672

5773
IntQueue q = new IntQueue(5);
5874

59-
q.enqueue(1);
60-
q.enqueue(2);
61-
q.enqueue(3);
62-
q.enqueue(4);
63-
q.enqueue(5);
75+
q.offer(1);
76+
q.offer(2);
77+
q.offer(3);
78+
q.offer(4);
79+
q.offer(5);
6480

65-
System.out.println(q.dequeue()); // 1
66-
System.out.println(q.dequeue()); // 2
67-
System.out.println(q.dequeue()); // 3
68-
System.out.println(q.dequeue()); // 4
81+
System.out.println(q.poll()); // 1
82+
System.out.println(q.poll()); // 2
83+
System.out.println(q.poll()); // 3
84+
System.out.println(q.poll()); // 4
6985

7086
System.out.println(q.isEmpty()); // false
7187

72-
q.enqueue(1);
73-
q.enqueue(2);
74-
q.enqueue(3);
88+
q.offer(1);
89+
q.offer(2);
90+
q.offer(3);
7591

76-
System.out.println(q.dequeue()); // 5
77-
System.out.println(q.dequeue()); // 1
78-
System.out.println(q.dequeue()); // 2
79-
System.out.println(q.dequeue()); // 3
92+
System.out.println(q.poll()); // 5
93+
System.out.println(q.poll()); // 1
94+
System.out.println(q.poll()); // 2
95+
System.out.println(q.poll()); // 3
8096

8197
System.out.println(q.isEmpty()); // true
8298

83-
benchMarkTest();
99+
// benchMarkTest();
84100
}
85101

86102
// BenchMark IntQueue vs ArrayDeque.
@@ -91,8 +107,8 @@ private static void benchMarkTest() {
91107

92108
// IntQueue times at around 0.0324 seconds
93109
long start = System.nanoTime();
94-
for (int i = 0; i < n; i++) intQ.enqueue(i);
95-
for (int i = 0; i < n; i++) intQ.dequeue();
110+
for (int i = 0; i < n; i++) intQ.offer(i);
111+
for (int i = 0; i < n; i++) intQ.poll();
96112
long end = System.nanoTime();
97113
System.out.println("IntQueue Time: " + (end - start) / 1e9);
98114

‎src/main/java/com/williamfiset/algorithms/datastructures/queue/LinkedQueue.java

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
/**
2+
* A simple queue implementation with a linkedlist
3+
*
4+
* @author William Fiset, william.alexandre.fiset@gmail.com
5+
*/
6+
package com.williamfiset.algorithms.datastructures.queue;
7+
8+
public class LinkedQueue<T> implements Iterable<T>, Queue<T> {
9+
10+
private java.util.LinkedList<T> list = new java.util.LinkedList<T>();
11+
12+
public LinkedQueue() {}
13+
14+
public LinkedQueue(T firstElem) {
15+
offer(firstElem);
16+
}
17+
18+
// Return the size of the queue
19+
public int size() {
20+
return list.size();
21+
}
22+
23+
// Returns whether or not the queue is empty
24+
public boolean isEmpty() {
25+
return size() == 0;
26+
}
27+
28+
// Peek the element at the front of the queue
29+
// The method throws an error is the queue is empty
30+
public T peek() {
31+
if (isEmpty()) throw new RuntimeException("Queue Empty");
32+
return list.peekFirst();
33+
}
34+
35+
// Poll an element from the front of the queue
36+
// The method throws an error is the queue is empty
37+
public T poll() {
38+
if (isEmpty()) throw new RuntimeException("Queue Empty");
39+
return list.removeFirst();
40+
}
41+
42+
// Add an element to the back of the queue
43+
public void offer(T elem) {
44+
list.addLast(elem);
45+
}
46+
47+
// Return an iterator to alow the user to traverse
48+
// through the elements found inside the queue
49+
@Override
50+
public java.util.Iterator<T> iterator() {
51+
return list.iterator();
52+
}
53+
}

‎src/main/java/com/williamfiset/algorithms/datastructures/queue/Queue.java

Lines changed: 10 additions & 46 deletions
Original file line numberDiff line numberDiff line change
@@ -1,53 +1,17 @@
1-
/**
2-
* A simple queue implementation with a linkedlist
3-
*
4-
* @author William Fiset, william.alexandre.fiset@gmail.com
5-
*/
61
package com.williamfiset.algorithms.datastructures.queue;
72

8-
public class Queue<T> implements Iterable<T> {
9-
10-
private java.util.LinkedList<T> list = new java.util.LinkedList<T>();
11-
12-
public Queue() {}
13-
14-
public Queue(T firstElem) {
15-
offer(firstElem);
16-
}
17-
18-
// Return the size of the queue
19-
public int size() {
20-
return list.size();
21-
}
22-
23-
// Returns whether or not the queue is empty
24-
public boolean isEmpty() {
25-
return size() == 0;
26-
}
3+
/**
4+
* @author liujingkun, liujkon@gmail.com
5+
* @param <T> the type of element held int the queue
6+
*/
7+
public interface Queue<T> {
8+
public void offer(T elem);
279

28-
// Peek the element at the front of the queue
29-
// The method throws an error is the queue is empty
30-
public T peek() {
31-
if (isEmpty()) throw new RuntimeException("Queue Empty");
32-
return list.peekFirst();
33-
}
10+
public T poll();
3411

35-
// Poll an element from the front of the queue
36-
// The method throws an error is the queue is empty
37-
public T poll() {
38-
if (isEmpty()) throw new RuntimeException("Queue Empty");
39-
return list.removeFirst();
40-
}
12+
public T peek();
4113

42-
// Add an element to the back of the queue
43-
public void offer(T elem) {
44-
list.addLast(elem);
45-
}
14+
public int size();
4615

47-
// Return an iterator to alow the user to traverse
48-
// through the elements found inside the queue
49-
@Override
50-
public java.util.Iterator<T> iterator() {
51-
return list.iterator();
52-
}
16+
public boolean isEmpty();
5317
}

‎src/main/java/com/williamfiset/algorithms/datastructures/stack/IntStack.java

Lines changed: 7 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@
99
*/
1010
package com.williamfiset.algorithms.datastructures.stack;
1111

12-
public class IntStack {
12+
public class IntStack implements Stack<Integer> {
1313

1414
private int[] ar;
1515
private int pos = 0;
@@ -31,17 +31,20 @@ public boolean isEmpty() {
3131
}
3232

3333
// Returns the element at the top of the stack
34-
public int peek() {
34+
@Override
35+
public Integer peek() {
3536
return ar[pos - 1];
3637
}
3738

3839
// Add an element to the top of the stack
39-
public void push(int value) {
40+
@Override
41+
public void push(Integer value) {
4042
ar[pos++] = value;
4143
}
4244

4345
// Make sure you check that the stack is not empty before calling pop!
44-
public int pop() {
46+
@Override
47+
public Integer pop() {
4548
return ar[--pos];
4649
}
4750

0 commit comments

Comments
 (0)