隊列優先級

優先級隊列比隊列更專業的數據結構。像普通隊列，優先級隊列中有相同的方法，但在使用上是有比較大的區別的。在優先級隊列數據項都受到鍵值排序，以便與最低鍵的值，數據項在前方，鍵的最高值的數據項在後方，反之亦然。因此，我們根據它的鍵值分配的優先項。數值越低，優先級越高。以下是優先級隊列的主要方法。

基本操作

• 插入/入隊 − 增加數據項到隊列的後部。

• 刪除/出隊 − 從隊列的前面刪除一個數據項。

優先級隊列表示

我們將在本文中使用數組來實現隊列。還有一些通過隊列支持更多的操作如下。

• Peek − 獲得在隊列前面的元素。

• isFull − 檢查隊列是否已滿。

• isEmpty − 檢查隊列是否爲空。

插入/入隊操作

每當一個元素被插入隊列時，優先級隊列根據其順序插入對應的數據項。在這裏，我們假設高值的數據具有低優先級。

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

}
}

刪除/解列操作

每當一個元素是從隊列中刪除，隊列使用項目計數得到元素。一旦元素被移除，項目計數減一。

int removeData(){
return intArray[--itemCount];
}

演示程序

PriorityQueueDemo.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 6

int intArray[MAX];
int itemCount = 0;

int peek(){
return intArray[itemCount - 1];
}

bool isEmpty(){
return itemCount == 0;
}

bool isFull(){
return itemCount == MAX;
}

int size(){
return itemCount;
}

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

}
}

int removeData(){
return intArray[--itemCount];
}

int main() {
/* insert 5 items */
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);

// ------------------
// index : 0 1 2 3 4
// ------------------
// queue : 12 9 5 3 1
insert(15);

// ---------------------
// index : 0 1 2 3 4 5
// ---------------------
// queue : 15 12 9 5 3 1

if(isFull()){
printf("Queue is full!\n");
}

// remove one item
int num = removeData();
printf("Element removed: %d\n",num);

// ---------------------
// index : 0 1 2 3 4
// ---------------------
// queue : 15 12 9 5 3

// insert more items
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.
insert(17);
insert(18);

// ----------------------
// index : 0 1 2 3 4 5
// ----------------------
// queue : 16 15 12 9 5 3
printf("Element at front: %d\n",peek());

printf("----------------------\n");
printf("index : 5 4 3 2 1 0\n");
printf("----------------------\n");
printf("Queue: ");

while(!isEmpty()){
int n = removeData();
printf("%d ",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