循环队列

机器翻译

#include <algorithm>
#include <fstream>
#include <iostream>
#include <map>
#include <memory>
#include <set>
#include <string>
#include <vector>

#define DEBUG
using namespace std;

template <typename T>
class CircularQueue {
 private:
  T *arr;
  int front;
  int rear;
  int maxSize;

 public:
  CircularQueue(int size) : maxSize(size + 1), front(0), rear(0) {
    arr = new T[maxSize];
  }

  ~CircularQueue() { delete[] arr; }

  bool isEmpty() const { return front == rear; }

  bool isFull() const { return (rear + 1) % maxSize == front; }

  void enqueue(const T &item) {
    if (isFull()) {
      std::cout << "Queue is full. Cannot enqueue." << std::endl;
      return;
    }
    arr[rear] = item;
    rear = (rear + 1) % maxSize;
  }

  void dequeue() {
    if (isEmpty()) {
      std::cout << "Queue is empty. Cannot dequeue." << std::endl;
      return;
    }
    front = (front + 1) % maxSize;
  }

  int size() { return (rear - front + maxSize) % maxSize; }

  T &frontItem() {
    if (isEmpty()) {
      throw std::runtime_error("Queue is empty.");
    }
    return arr[front];
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
#ifdef DEBUG
  ifstream inputFile("in.txt");
  if (inputFile.is_open()) {
    cin.rdbuf(inputFile.rdbuf());
  }
#endif
  using i64 = long long;

  int m, n;
  cin >> m >> n;
  int cnt = 0;
  vector<bool> st(1001);
  CircularQueue<int> Q(m);
  while (n--) {
    int x;
    cin >> x;
    if (!st[x]) {
      cnt++;
      if (Q.size() == m) {
        int tmp = Q.frontItem();
        Q.dequeue();
        st[tmp] = false;
      }
      Q.enqueue(x);
      st[x] = true;
    }
  }
  cout << cnt << '\n';
}