队列的应用问题：缓存问题

原题链接： https://www.acwing.com/problem/content/498/

队列最常见的就是考缓存，内存的缓存都是以队列的数据结构来实现的，这道题直接手动模拟了队列问题，写法有很多，我提供两种方法，一种自定义队列写法，一种在此基础上哈希表优化写法，因为这道题的数据量不大，你可以用数据结构队列的操作或者循环队列的操作，来实现练习你的数据结构能力

#include <iostream>
#include <cstring>
#include <algorithm>
#define N 1010
using namespace std;

int a[N],q[N];
int tt = -1;
int n, m;

int main()
{
    memset(q, -1, sizeof q);
    cin >> m >> n;
    for (int i = 0; i < n; i ++ )   cin>>a[i];
    int count = 0;
    for (int i = 0; i < n; i ++ )
    {
        bool flag = false;
        for (int j = 0; j < m && j < i; j ++ )
            if(a[i] == q[j])
                flag = true;
        if(!flag)
        {
            if(tt+1 < m)     //查看长度多少
                q[++ tt] = a[i];
            else
            {
                tt = -1;
                q[++ tt] = a[i];
            }
            count ++;
        }
    }

    cout << count <<endl;
    return 0;
}

用哈希表优化：只需要把中间遍历队列的部分全部换成hash就行了

数据结构目录：

https://www.acwing.com/file_system/file/content/whole/index/content/5394132/