c语言写单调队列

### 单调队列的C语言实现 单调队列是一种特殊的队列，其中元素按照某种特定的顺序排列（通常是递增或递减）。为了在C语言中实现单调队列，可以借助数组模拟队列的操作，并通过维护前后指针来控制队列的行为。 以下是基于循环队列的思想实现的一个单调递增队列的例子： ```c #include <stdio.h> #define MAX_SIZE 1000 // 队列的最大容量 typedef struct { int data[MAX_SIZE]; // 存储队列中的元素 int front; // 队头指针 int rear; // 队尾指针 } MonotonicQueue; // 初始化队列 void init(MonotonicQueue *mq) { mq->front = mq->rear = 0; } // 判断队列是否为空 int is_empty(MonotonicQueue *mq) { return mq->front == mq->rear; } // 判断队列是否已满 int is_full(MonotonicQueue *mq) { return (mq->rear + 1) % MAX_SIZE == mq->front; } // 入队操作，保持队列为单调递增 void push(MonotonicQueue *mq, int value) { while (!is_empty(mq) && mq->data[(mq->rear - 1 + MAX_SIZE) % MAX_SIZE] >= value) { mq->rear--; // 移除不符合条件的元素 } if (!is_full(mq)) { // 如果未满，则入队 mq->data[mq->rear++] = value; mq->rear %= MAX_SIZE; // 循环队列特性 } else { printf("Error: Queue is full.\n"); } } // 出队操作 void pop(MonotonicQueue *mq) { if (!is_empty(mq)) { mq->front++; mq->front %= MAX_SIZE; // 循环队列特性 } else { printf("Error: Queue is empty.\n"); } } // 获取队首元素 int get_front(MonotonicQueue *mq) { if (!is_empty(mq)) { return mq->data[mq->front]; } else { printf("Error: Queue is empty.\n"); return -1; // 返回错误码 } } int main() { MonotonicQueue mq; init(&mq); push(&mq, 3); push(&mq, 1); push(&mq, 2); printf("Front element: %d\n", get_front(&mq)); // 输出最小值 1 pop(&mq); printf("Front element after pop: %d\n", get_front(&mq)); // 输出次小值 2 return 0; } ``` 上述代码实现了一个简单的单调递增队列。它利用了循环队列的概念[^2]，并通过调整`push`函数逻辑确保队列内的元素始终满足单调性要求[^3]。 #### 关键点解析 - **初始化**：定义了一个结构体用于表示队列，包含存储数据的数组以及前後指针。 - **单调性维持**：在`push`方法中加入判断逻辑，当新元素小于等于当前队尾元素时，删除队尾元素直到恢复单调性为止[^4]。 - **边界处理**：考虑到了队列可能溢出的情况，在实际应用中可以根据需求动态扩展大小。 ### 注意事项 由于此实现采用了固定长度的数组作为底层容器，因此需要提前设定好最大容量(MAX_SIZE)，并注意防止越界访问等问题的发生。