Priority queue
If we assign each element a number to mark its priority, we might as well make smaller numbers have higher priority so that we can access the highest priority element in a collection and search and delete it. In this way, we introduce a data structure like priority queue. A priority queue is a collection of 0 or more elements, each element has a priority. The operations performed on the priority queue include (1) search (2) insert a new element (3) deletion. Generally, the search operation is used to search for the element with the greatest priority, and the delete operation is used to delete the element. For elements with the same priority, they can be processed in first-in-first-out order or in any priority.
Java array simulation queue
A queue is a special linear table that only allows deletion operations at the front end of the table and insert operations at the back end of the table. The end that performs the insertion operation is called the tail of the team, and the end that performs the deletion operation is called the head of the team. This is the first-in-first-out principle (FIFO) we often use. List in Java can be used as a queue. If you add elements at the end of the queue, use the list.add method, and if you delete elements from the head of the queue, use the list.remove method.
Java array simulation priority queue structure example:
package datastruct; import java.util.Arrays; import java.util.Comparator; /** * Use arrays to simulate the first-rank and first-outline linear table structure with high priority.* Similar to TreeSet and TreeMap using comparator */ public class SimulatePriorityQueue { public static void main(String[] args) { SimulatePriorityQueue queue = new SimulatePriorityQueue(4); // SimulateQueue queue = new SimulateQueue(); // System.out.println("Fetch out the element:" + queue.remove()); queue.insert(1); queue.insert(3); queue.insert(2); queue.insert(5); queue.insert(4); System.out.println("size:" + queue.size()); System.out.println("peek:" + queue.peek()); System.out.println("take out element:" + queue.peek()); System.out.println("take out element:" + queue.remove()); System.out.println("take out element:" + queue.remove()); System.out.println("Extract element: " + queue.remove()); // System.out.println("Extract element: " + queue.remove()); System.out.println("Size:" + queue.size()); System.out.println(); } private int mSize = 3; //Size private int[] mArray; //Array private int mNextItem; //Next position, can also be regarded as the current number of elements public SimulatePriorityQueue() { mArray = new int[mSize]; mNextItem = 0; } public SimulatePriorityQueue(int size) { this.mSize = size; mArray = new int[mSize]; mNextItem = 0; } /** * Insert element* @param item */ public void insert(int item) { if (!isFull()) { mArray[mNextItem++] = item; for (int i = 0; i < mNextItem; i++) {//Bubblestone for (int j = 0; j < mNextItem - 1; j++) { if (mArray[j] > mArray[j + 1]) { mArray[j] = mArray[j + 1] + 0 * (mArray[j + 1] = mArray[j]); System.out.println(Arrays.toString(mArray)); } } System.out.println(Arrays.toString(mArray)); } else { System.out.println("----------------"); } } /** * Remove element first-in first-out* @return */ public int remove() { if (!isEmpty()) { return mArray[--mNextItem]; } else { throw new IllegalArgumentException("No element can be taken out"); } } /** * Check the previous element* @return */ public int peek() { return mArray[mNextItem - 1]; } /** * Is it empty* @return */ public boolean isEmpty() { return mNextItem == 0; } /** * Is it full* @return */ public boolean isFull() { return mNextItem == mSize; } /** * size * @return */ public int size() { return mNextItem; } } Output result:
[1, 0, 0, 0][1, 3, 0, 0][1, 2, 3, 0][1, 2, 3, 0][1, 2, 3, 5]---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------