Dsa Using Java 简明教程
DSA using Java - Priority Queue
Overview
优先队列是一种比队列更专业的データ结构。与普通队列一样,优先队列具有相同的方法,但有一个主要区别。在优先队列中,项目按键值排序,因此键值最小的项目在前面,键值最大的项目在后面,反之亦然。因此,我们将优先级分配给项目的键值。值越低,优先级越高。以下是优先队列的主要方法。
Priority Queue Representation
在本文中,我们将使用数组实现队列。队列支持以下更多操作。
-
Peek − 获取队列前部的元素。
-
isFull − 检查队列是否已满。
-
isEmpty − 检查队列是否为空。
Insert / Enqueue Operation
每当将元素插入队列时,优先队列会根据其顺序插入项目。在此处,我们假设具有高值的具有低优先级。
public void insert(int data){
int i =0;
if(!isFull()){
// if queue is empty, insert the data
if(itemCount == 0){
intArray[itemCount++] = data;
}else{
// start from the right end of the queue
for(i = itemCount - 1; i >= 0; i-- ){
// if data is larger, shift existing item to right end
if(data > intArray[i]){
intArray[i+1] = intArray[i];
}else{
break;
}
}
// insert the data
intArray[i+1] = data;
itemCount++;
}
}
}
Remove / Dequeue Operation
每当要从队列中移除一个元素时,队列使用项目计数获取元素。一旦移除元素。项目计数减少一。
public int remove(){
return intArray[--itemCount];
}
Priority Queue Implementation
PriorityQueue.java
package com.tutorialspoint.datastructure;
public class PriorityQueue {
private final int MAX;
private int[] intArray;
private int itemCount;
public PriorityQueue(int size){
MAX = size;
intArray = new int[MAX];
itemCount = 0;
}
public void insert(int data){
int i =0;
if(!isFull()){
// if queue is empty, insert the data
if(itemCount == 0){
intArray[itemCount++] = data;
}else{
// start from the right end of the queue
for(i = itemCount - 1; i >= 0; i-- ){
// if data is larger, shift existing item to right end
if(data > intArray[i]){
intArray[i+1] = intArray[i];
}else{
break;
}
}
// insert the data
intArray[i+1] = data;
itemCount++;
}
}
}
public int remove(){
return intArray[--itemCount];
}
public int peek(){
return intArray[itemCount - 1];
}
public boolean isEmpty(){
return itemCount == 0;
}
public boolean isFull(){
return itemCount == MAX;
}
public int size(){
return itemCount;
}
}
Demo Program
PriorityQueueDemo.java
package com.tutorialspoint.datastructure;
public class PriorityQueueDemo {
public static void main(String[] args){
PriorityQueue queue = new PriorityQueue(6);
//insert 5 items
queue.insert(3);
queue.insert(5);
queue.insert(9);
queue.insert(1);
queue.insert(12);
// ------------------
// index : 0 1 2 3 4
// ------------------
// queue : 12 9 5 3 1
queue.insert(15);
// ---------------------
// index : 0 1 2 3 4 5
// ---------------------
// queue : 15 12 9 5 3 1
if(queue.isFull()){
System.out.println("Queue is full!");
}
//remove one item
int num = queue.remove();
System.out.println("Element removed: "+num);
// ---------------------
// index : 0 1 2 3 4
// ---------------------
// queue : 15 12 9 5 3
//insert more items
queue.insert(16);
// ----------------------
// index : 0 1 2 3 4 5
// ----------------------
// queue : 16 15 12 9 5 3
//As queue is full, elements will not be inserted.
queue.insert(17);
queue.insert(18);
// ----------------------
// index : 0 1 2 3 4 5
// ----------------------
// queue : 16 15 12 9 5 3
System.out.println("Element at front: "+queue.peek());
System.out.println("----------------------");
System.out.println("index : 5 4 3 2 1 0");
System.out.println("----------------------");
System.out.print("Queue: ");
while(!queue.isEmpty()){
int n = queue.remove();
System.out.print(n +" ");
}
}
}
如果我们编译并运行上述程序,它将生成以下结果 -
Queue is full!
Element removed: 1
Element at front: 3
----------------------
index : 5 4 3 2 1 0
----------------------
Queue: 3 5 9 12 15 16