データ構造 - 優先度付きキュー

#include <stdio.h>

#define MAX 100

/* 順序なし配列に基づく優先度付きキュー（最大優先度付きキュー：値が大きいほど優先度が高い） */
struct PriorityQueue {
    int items[MAX];
    int size;  /* 現在の要素数 */
};

void initPQ(struct PriorityQueue* pq) { pq->size = 0; }

/* エンキュー：末尾に直接追加，O(1) */
void enqueue(struct PriorityQueue* pq, int value) {
    if (pq->size >= MAX) return;
    pq->items[pq->size++] = value;
}

/* デキュー：走査して最大値を検索、O(n)
見つかったら最後の要素を削除位置に移動し、size を 1 減らす */
int dequeue(struct PriorityQueue* pq) {
    if (pq->size == 0) return -1;

    /* 最大値のインデックスを検索する */
    int maxIdx = 0;
    for (int i = 1; i < pq->size; i++) {
        if (pq->items[i] > pq->items[maxIdx]) {
            maxIdx = i;
        }
    }
    int maxVal = pq->items[maxIdx];
    /* 最後の要素を削除位置に移動する（大量の移動を避けるため） */
    pq->items[maxIdx] = pq->items[--pq->size];
    return maxVal;
}

int main() {
    struct PriorityQueue pq;
    initPQ(&pq);

    enqueue(&pq, 5);
    enqueue(&pq, 9);
    enqueue(&pq, 3);
    enqueue(&pq, 7);

    printf("デキュー（優先度最高）: %d\n", dequeue(&pq));  /* 出力: 9 */
    printf("デキュー（優先度最高）: %d\n", dequeue(&pq));  /* 出力: 7 */
    printf("デキュー（優先度最高）: %d\n", dequeue(&pq));  /* 出力: 5 */
    printf("デキュー: %d\n", dequeue(&pq));                /* 出力: 3 */
    return 0;
}

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    int priority;       /* 優先度（値が大きいほど優先度が高い） */
    struct Node* next;
};

/* エンキュー：優先度の降順で挿入、O(n) */
struct Node* enqueue(struct Node* head, int data, int priority) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->priority = priority;
    newNode->next = NULL;

    /* 空の連結リスト、または新しいノードの優先度が最高 → 先頭に挿入 */
    if (head == NULL || head->priority < priority) {
        newNode->next = head;
        return newNode;
    }

    /* 走査して適切な位置を見つける（降順を維持） */
    struct Node* cur = head;
    while (cur->next != NULL && cur->next->priority >= priority) {
        cur = cur->next;
    }
    newNode->next = cur->next;
    cur->next = newNode;
    return head;
}

/* デキュー：先頭ノードを削除（優先度が最高）、O(1) */
struct Node* dequeue(struct Node* head) {
    if (head == NULL) return NULL;
    struct Node* temp = head;
    printf("デキュー: data=%d, priority=%d\n", temp->data, temp->priority);
    head = head->next;
    free(temp);
    return head;
}

int main() {
    struct Node* pq = NULL;

    pq = enqueue(pq, 10, 1);  /* データ 10、優先度 1 */
    pq = enqueue(pq, 20, 5);  /* データ 20、優先度 5 */
    pq = enqueue(pq, 30, 3);  /* データ 30、優先度 3 */

    pq = dequeue(pq);  /* デキュー: data=20, priority=5 (最高優先度) */
    pq = dequeue(pq);  /* デキュー: data=30, priority=3 */
    pq = dequeue(pq);  /* デキュー: data=10, priority=1 */
    return 0;
}