Skip to content

Update PriorityQueues.java #707

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 2 commits into from
Feb 17, 2019
Merged

Update PriorityQueues.java #707

Changes from all commits
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
b73757e
Update PriorityQueues.java
hailK11 Feb 16, 2019
36d6b51
Update PriorityQueues.java
yanglbme Feb 17, 2019
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
203 changes: 104 additions & 99 deletions DataStructures/Queues/PriorityQueues.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,123 +1,128 @@
/**
* 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.
*
* @author Unknown
*
*/
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;
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;
}
/**
* 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(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++;
}
/**
* 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];
}
/**
* 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];
}
/**
* 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 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 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;
}
/**
* 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
*
* @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
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]
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
}
}
// As you can see, a Priority Queue can be used as a sorting algotithm
}
}