帮我用c++写一个单调队列模板

### 回答1：
好的，以下是一个简单的单调队列模板的 C 语言代码模板：

#include <stdio.h>

#define MAX_N 100000

int a[MAX_N]; // 存储原始数据
int q[MAX_N]; // 存储队列元素下标
int head = 0, tail = 0; // 队列头尾指针

int main() {
    int n, k; // n 表示数组长度，k 表示窗口长度
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    // 处理前 k 个元素
    for (int i = 0; i < k; i++) {
        while (tail > head && a[q[tail - 1]] >= a[i]) {
            tail--; // 弹出队尾元素
        }
        q[tail++] = i; // 将当前元素下标加入队尾
    }

    // 处理剩余元素
    for (int i = k; i < n; i++) {
        printf("%d ", a[q[head]]); // 输出队头元素
        // 弹出超出窗口范围的队头元素
        if (q[head] == i - k) {
            head++;
        }
        // 弹出队尾元素，直到队列为空或者队尾元素小于当前元素
        while (tail > head && a[q[tail - 1]] >= a[i]) {
            tail--;
        }
        q[tail++] = i; // 将当前元素下标加入队尾
    }
    printf("%d\n", a[q[head]]); // 输出最后一个窗口的最小值

    return 0;
}

这是一个简单的使用单调队列求解滑动窗口最小值的模板。当然，具体实现还需要结合具体问题来进行修改和优化。

### 回答2：
单调队列（Monotonic Queue）是一种在数据结构中常见的一种队列，它支持在队列两端进行元素的插入和删除操作，但新增的元素必须按照一定的顺序排列。

以下是一个用C语言实现的单调队列模板：

#include <stdio.h>
#define MAX_SIZE 100

// 单调队列结构体
typedef struct {
    int arr[MAX_SIZE];  // 存储队列元素的数组
    int front;          // 队列头指针
    int rear;           // 队列尾指针
} MonotonicQueue;

// 初始化单调队列
void initQueue(MonotonicQueue *q) {
    q->front = q->rear = -1;
}

// 判断队列是否为空
int isEmpty(MonotonicQueue *q) {
    return q->front == -1;
}

// 判断队列是否已满
int isFull(MonotonicQueue *q) {
    return (q->rear + 1) % MAX_SIZE == q->front;
}

// 元素入队（从队尾插入）
void enqueue(MonotonicQueue *q, int x) {
    if (isFull(q)) {
        printf("Queue is full.\n");
        return;
    }
    if (isEmpty(q)) {
        q->front = q->rear = 0;
    } else {
        q->rear = (q->rear + 1) % MAX_SIZE;
    }
    q->arr[q->rear] = x;
}

// 元素出队（从队首删除）
void dequeue(MonotonicQueue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty.\n");
        return;
    }
    if (q->front == q->rear) {
        q->front = q->rear = -1;
    } else {
        q->front = (q->front + 1) % MAX_SIZE;
    }
}

// 获取队首元素
int front(MonotonicQueue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty.\n");
        return -1;
    }
    return q->arr[q->front];
}

// 获取队尾元素
int rear(MonotonicQueue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty.\n");
        return -1;
    }
    return q->arr[q->rear];
}

int main() {
    MonotonicQueue q;
    initQueue(&q);

    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);

    printf("Front element: %d\n", front(&q));  // Output: Front element: 1
    printf("Rear element: %d\n", rear(&q));    // Output: Rear element: 3

    dequeue(&q);

    printf("Front element: %d\n", front(&q));  // Output: Front element: 2

    return 0;
}

这个单调队列模板包含了初始化队列、判断队列是否为空、判断队列是否已满、元素入队、元素出队、获取队首元素和获取队尾元素等基本操作。使用时，只需要调用相应的函数即可实现单调队列的各种操作。

### 回答3：
单调队列是一种特殊的队列数据结构，它在插入和删除元素时保持队列中元素的单调性。

以下是一个用C语言编写的单调队列模板：

#include <stdio.h>
#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE]; // 存储数据
    int front, rear; // 队首和队尾指针
} MonotonicQueue;

// 初始化队列
void init(MonotonicQueue* q) {
    q->front = 0;
    q->rear = -1;
}

// 判断队列是否为空
int isEmpty(MonotonicQueue* q) {
    return q->rear < q->front;
}

// 获取队首元素
int front(MonotonicQueue* q) {
    return q->data[q->front];
}

// 在队尾插入元素
void push(MonotonicQueue* q, int x) {
    // 删除队尾小于x的元素，保持队列单调递增
    while (!isEmpty(q) && q->data[q->rear] < x) {
        q->rear--;
    }
    q->rear++;
    q->data[q->rear] = x;
}

// 在队首删除元素
void pop(MonotonicQueue* q, int x) {
    if (!isEmpty(q) && q->data[q->front] == x) {
        q->front++;
    }
}

int main() {
    MonotonicQueue q;
    init(&q);

    // 示例使用
    push(&q, 3);
    push(&q, 1);
    printf("队首元素为：%d\n", front(&q)); // 输出 3
    pop(&q, 3);
    printf("队首元素为：%d\n", front(&q)); // 输出 1

    return 0;
}

这个单调队列模板使用一个数组来存储队列中的数据，并使用front和rear两个指针来记录队首和队尾位置。通过初始化、判断为空、获取队首元素、插入元素和删除元素等基本操作，可以实现一个单调队列。在插入元素时，会删除队列中队尾小于插入元素的元素，从而保持队列的单调性。在删除元素时，会删除队首等于删除元素的元素。