forked from TheAlgorithms/Java
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathPriorityQueues.java
More file actions
129 lines (118 loc) · 3.09 KB
/
PriorityQueues.java
File metadata and controls
129 lines (118 loc) · 3.09 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
package DataStructures.Queues;
/**
* This class implements a PriorityQueue.
* <p>
* A priority queue adds elements into positions based on their priority.
* So the most important elements are placed at the front/on the top.
* In this example I give numbers that are bigger, a higher priority.
* Queues in theory have no fixed size but when using an array
* implementation it does.
*/
class PriorityQueue {
/**
* The max size of the queue
*/
private int maxSize;
/**
* The array for the queue
*/
private int[] queueArray;
/**
* How many items are in the queue
*/
private int nItems;
/**
* Constructor
*
* @param size Size of the queue
*/
public PriorityQueue(int size) {
maxSize = size;
queueArray = new int[size];
nItems = 0;
}
/**
* Inserts an element in it's appropriate place
*
* @param value Value to be inserted
*/
public void insert(int value) {
if (isFull()) {
throw new RuntimeException("Queue is full");
}
if (nItems == 0) {
queueArray[0] = value;
} else {
int j = nItems;
while (j > 0 && queueArray[j - 1] > value) {
queueArray[j] = queueArray[j - 1]; // Shifts every element up to make room for insertion
j--;
}
queueArray[j] = value; // Once the correct position is found the value is inserted
}
nItems++;
}
/**
* Remove the element from the front of the queue
*
* @return The element removed
*/
public int remove() {
return queueArray[--nItems];
}
/**
* Checks what's at the front of the queue
*
* @return element at the front of the queue
*/
public int peek() {
return queueArray[nItems - 1];
}
/**
* Returns true if the queue is empty
*
* @return true if the queue is empty
*/
public boolean isEmpty() {
return (nItems == 0);
}
/**
* Returns true if the queue is full
*
* @return true if the queue is full
*/
public boolean isFull() {
return (nItems == maxSize);
}
/**
* Returns the number of elements in the queue
*
* @return number of elements in the queue
*/
public int getSize() {
return nItems;
}
}
/**
* This class implements the PriorityQueue class above.
*
* @author Unknown
*/
public class PriorityQueues {
/**
* Main method
*
* @param args Command Line Arguments
*/
public static void main(String[] args) {
PriorityQueue myQueue = new PriorityQueue(4);
myQueue.insert(10);
myQueue.insert(2);
myQueue.insert(5);
myQueue.insert(3);
// [2, 3, 5, 10] Here higher numbers have higher priority, so they are on the top
for (int i = 3; i >= 0; i--)
System.out.print(myQueue.remove() + " "); // will print the queue in reverse order [10, 5, 3, 2]
// As you can see, a Priority Queue can be used as a sorting algotithm
}
}