C語言實現的資料結構 - 優先佇列

概述

優先佇列比普通佇列更加專業。與普通佇列一樣，優先佇列具有相同的方法，但有一個主要區別。在優先佇列中，專案按鍵值排序，以便鍵值最低的專案位於最前面，鍵值最高的專案位於最後面，反之亦然。因此，我們根據專案的鍵值分配優先順序。值越低，優先順序越高。以下是優先佇列的主要方法。

基本操作

• 插入/入隊 − 將專案新增到佇列的末尾。

• 移除/出隊 − 從佇列的開頭移除一個專案。

優先隊列表示

在本文中，我們將使用陣列實現佇列。佇列還支援一些其他操作，如下所示。

• 檢視 − 獲取佇列開頭處的元素。

• 是否已滿 − 檢查佇列是否已滿。

• 是否為空 − 檢查佇列是否為空。

插入/入隊操作

每當將元素插入佇列時，優先佇列會根據其順序插入該專案。這裡我們假設資料值越高，優先順序越低。

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

示例

#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