Dsa Using Java 简明教程

DSA using Java - Priority Queue

Overview

优先队列是一种比队列更专业的データ结构。与普通队列一样,优先队列具有相同的方法,但有一个主要区别。在优先队列中,项目按键值排序,因此键值最小的项目在前面,键值最大的项目在后面,反之亦然。因此,我们将优先级分配给项目的键值。值越低,优先级越高。以下是优先队列的主要方法。

Priority Queue is more specilized data structure than Queue. Like ordinary queue, priority queue has same method but with a major difference. In Priority queue items are ordered by key value so that item with the lowest value of key is at front and item with the highest value of key is at rear or vice versa. So we’re assigned priority to item based on its key value. Lower the value, higher the priority. Following are the principal methods of a Priority Queue.

Basic Operations

  1. insert / enqueue − add an item to the rear of the queue.

  2. remove / dequeue − remove an item from the front of the queue.

Priority Queue Representation

queue

在本文中,我们将使用数组实现队列。队列支持以下更多操作。

We’re going to implement Queue using array in this article. There is few more operations supported by queue which are following.

  1. Peek − get the element at front of the queue.

  2. isFull − check if queue is full.

  3. isEmpty − check if queue is empty.

Insert / Enqueue Operation

每当将元素插入队列时,优先队列会根据其顺序插入项目。在此处,我们假设具有高值的具有低优先级。

Whenever an element is inserted into queue, priority queue inserts the item according to its order. Here we’re assuming that data with high value has low priority.

queue insert
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

每当要从队列中移除一个元素时,队列使用项目计数获取元素。一旦移除元素。项目计数减少一。

Whenever an element is to be removed from queue, queue get the element using item count. Once element is removed. Item count is reduced by one.

queue remove
public int remove(){
    return intArray[--itemCount];
}

Priority Queue Implementation

PriorityQueue.java

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

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 +" ");
      }
   }
}

如果我们编译并运行上述程序,它将生成以下结果 -

If we compile and run the above program then it would produce following result −

Queue is full!
Element removed: 1
Element at front: 3
----------------------
index : 5 4 3 2  1  0
----------------------
Queue:  3 5 9 12 15 16