顺序优先队列的两种策略与编程实现及完整代码 c++

顺序优先队列是一种使用数组实现的数据结构，其中元素按照优先级从高到低排列。在顺序优先队列中，插入操作和删除操作都需要考虑元素的优先级。

以下是两种常用的策略以及对应的编程实现：

1. 最大优先级策略

在最大优先级策略中，优先级最高的元素在队列头部。插入操作时，将新元素插入到队列尾部，然后将其与前面元素比较，如果优先级更高，则交换位置。删除操作时，直接删除队列头部元素即可。

C 代码实现如下：

#define MAX_QUEUE_SIZE 100

typedef struct {
    int data[MAX_QUEUE_SIZE];
    int size;
} PriorityQueue;

void init(PriorityQueue* q) {
    q->size = 0;
}

void insert(PriorityQueue* q, int x) {
    if (q->size >= MAX_QUEUE_SIZE) {
        return;
    }
    int i = q->size;
    while (i > 0 && x > q->data[i-1]) {
        q->data[i] = q->data[i-1];
        i--;
    }
    q->data[i] = x;
    q->size++;
}

int delete(PriorityQueue* q) {
    if (q->size == 0) {
        return -1;
    }
    int x = q->data[0];
    for (int i = 1; i < q->size; i++) {
        q->data[i-1] = q->data[i];
    }
    q->size--;
    return x;
}

2. 最小优先级策略

在最小优先级策略中，优先级最低的元素在队列头部。插入操作时，将新元素插入到队列尾部，然后将其与前面元素比较，如果优先级更低，则交换位置。删除操作时，直接删除队列头部元素即可。

C 代码实现如下：

#define MAX_QUEUE_SIZE 100

typedef struct {
    int data[MAX_QUEUE_SIZE];
    int size;
} PriorityQueue;

void init(PriorityQueue* q) {
    q->size = 0;
}

void insert(PriorityQueue* q, int x) {
    if (q->size >= MAX_QUEUE_SIZE) {
        return;
    }
    int i = q->size;
    while (i > 0 && x < q->data[i-1]) {
        q->data[i] = q->data[i-1];
        i--;
    }
    q->data[i] = x;
    q->size++;
}

int delete(PriorityQueue* q) {
    if (q->size == 0) {
        return -1;
    }
    int x = q->data[0];
    for (int i = 1; i < q->size; i++) {
        q->data[i-1] = q->data[i];
    }
    q->size--;
    return x;
}

完整代码如下：