循环数组和循环队列

发表于 更新于 分类于 Valine： 本文字数： 1.2k 阅读时长 ≈ 1 分钟

实现比较简单直接看代码，说几点：

  1. (i%MAX_SIZE+MAX_SIZE)%MAX_SIZE 是为了支持负数下标，如果不需要负下标可以直接i%MAX_SIZE
  2. 循环队列中，因为begin、end一直增加，所以不需要full标志仍然可以把空间用足，不存在队满和队空条件相同。
  3. 如果限定MAX_SIZE是2的幂，可以用 i&(MAX_SIZE-1) 来代替取模，而且同样支持负数下标，真是又快又好 _
  4. CircularArray的主要用途是在DP循环的时候如果状态仅依赖前N项，那么可以简单地把空间节省到N。
  5. Queue的用途是为了替代std::queue，但实际上std::queue已经相当快了。

总的来说这两个数据结构在比赛中基本用不到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
template<typename T, int MAX_SIZE>
class CircularArray {
    T data[MAX_SIZE];
public:
    CircularArray(const T& t=T()) {fill(data, data+MAX_SIZE, t);}
    T& operator [] (int i) {
        return data[(i%MAX_SIZE+MAX_SIZE)%MAX_SIZE];
    }
};

template<typename T, int MAX_SIZE>
class Queue {
    CircularArray<T, MAX_SIZE> data;
    int begin = 0;
    int end = 0;
public:
    void push(const T& t) {
        assert(!full());
        data[end++] = t;
    }

    T pop() {
        assert(!empty());
        return data[begin++];
    }

    T& peek() {
        assert(!empty());
        return data[begin];
    }

    const T& peek() const {
        return const_cast<Queue*>(this)->peek();
    }

    bool empty() const {
        return end == begin;
    }

    size_t size() const {
        return end-begin;
    }

    bool full() const {
        return size() == MAX_SIZE;
    }
};