三、队列

0x00 设计循环队列

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

    vector<int> data;
    int len,front,rear;
    MyCircularQueue(int k) {
        len = k+1;
        data = vector<int>(len);
        front = 0,rear = 0; //front指向队头 rear 指向队尾的下一个位置
    }

    /** Insert an element into the circular queue. Return true if the operation is successful. */
    bool enQueue(int value) {
        if((rear+1)%len==front) return false;//此时队列无法插入
        data[rear] = value,rear = (rear+1)%len;
        return true;
    }

    /** Delete an element from the circular queue. Return true if the operation is successful. */
    bool deQueue() {
        if(rear==front) return false;
        front = (front+1)%len;
        return true;
    }

    /** Get the front item from the queue. */
    int Front() {
        if(rear==front) return -1;
        return data[front];
    }

    /** Get the last item from the queue. */
    int Rear() {
        if(rear==front) return -1;
        return data[(rear-1+len)%len];
    }

    /** Checks whether the circular queue is empty or not. */
    bool isEmpty() {
        return rear==front;
    }

    /** Checks whether the circular queue is full or not. */
    bool isFull() {
        return (rear+1)%len==front;
    }
0x01 单调队列-滑动窗口

有一个大小为k的滑动窗口，它从数组的最左边移动到最右边。

您只能在窗口中看到k个数字。

每次滑动窗口向右移动一个位置

您的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

输入格式

输入包含两行。

第一行包含两个整数n和k，分别代表数组长度和滑动窗口的长度。

第二行有n个整数，代表数组的具体数值。

同行数据之间用空格隔开。

输出格式

输出包含两个。

第一行输出，从左至右，每个位置滑动窗口中的最小值。

第二行输出，从左至右，每个位置滑动窗口中的最大值。

输入样例：

8 3

1 3 -1 -3 5 3 6 7

输出样例：

-1 -3 -3 -3 3 3

3 3 5 5 6 7

#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
int a[N];
int q[N],hh,tt=-1;//队列 队头 队尾 注意队列中存的是所代表的数的下标 为了判断是否超出滑动窗口左侧
int main(){
    int n,k;//l,r表示窗口范围表示窗口大小
    scanf("%d %d",&n,&k);
    for(int i = 0; i < n; i++) scanf("%d",&a[i]);
    for(int i = 0; i < n; i++){
       while(hh<=tt && a[i]<=a[q[tt]]) tt--;//如果发现有更小的数入队,那么之前比它大的数就没用了,因为之前的数会先出队,有小的撑着就行
       q[++tt] = i;//入队
       if(hh<=tt&&q[hh]<i-k+1) hh++;//如果发现当前最小值出界了(右边界i-窗口长度+1),那么就出队
       if(i>=k-1) printf("%d ",a[q[hh]]);//当窗口内有k个元素就输出答案了
    }
    puts("");
    hh = 0, tt = -1;
    for(int i = 0; i < n; i++){
       while(hh<=tt && a[i]>=a[q[tt]]) tt--;//去除之前的更小的数即可,留大的撑着
       q[++tt] = i;//入队
       if(hh<=tt&&q[hh]<i-k+1) hh++;
       if(i>=k-1) printf("%d ",a[q[hh]]);
    }
    return 0;
}