cpp八股3

这里我们主要手撕一些面试里可能让你手撕的轮子（？

队列

首先看看环形队列，就是固定大小的缓冲区上维护两个指针：

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
48
49
50
51
template<typename T>
class CircleQueue
{
public:
    CircleQueue(int capacity=5)
        : cap(capacity), nxt(0), head(0)
    {
        buf.resize(cap);
    }

    T& Front()
    {
        if(Empty())
            throw std::runtime_error("Queue is empty");
        return buf[head];
    }

    T& Back()
    {
        if(Empty())
            throw std::runtime_error("Queue is empty");
        return buf[(nxt - 1 + cap) % cap];
    }

    bool Push(const T& val)
    {
        if((nxt + 1) % cap == head)
            return false; // Queue is full
        buf[nxt] = val;
        nxt = (nxt + 1) % cap;
        return true;
    }

    void Pop()
    {
        if(Empty())
            throw std::runtime_error("Queue is empty");
        head = (head + 1) % cap;
    }

    bool Empty() const
    {
        return head == nxt;
    }

private:
    std::vector<T> buf;
    int nxt;
    int head;
    int cap;
};

这时候面试官可能会让你想怎么支持无限扩容的，我这里想到的就是使用链表和 std::deque 类似的实现。