循环队列 bug

1. 题目描述

spfa判断负环

LC 设计循环队列

2. 普通单队列

int q[N];
int hh = 0, tt = -1;
while(hh <= tt) // empty
{int t = q[ hh ++ ];	// push/* do something */q[ ++ tt ] = j;	// pop
}

3. 错误的循环队列

int q[N];
int hh = 0, tt = -1;
while(hh != (tt + 1) % N) // 非空
{int t = q[ hh ++ ];	// 出队hh %= N;/* do something */tt = (tt + 1) % N;q[tt] = j;	// 入队
}

但这种方法无法区分队空的情况和队满的情况。

例如 N=5，初始时 hh=0,tt=-1，连续 push 5 个元素，hh=0,tt=4，此时有 hh=(tt+1)%N，但此时是队满。

但值得注意的是，这种可发可以过上面 spfa 那一题，不知道是因为数据太弱，还是队满的情况几乎不会发生。

4. 正确写法（带一个空位置）

// N = q.capacity()
int q[N];
int hh = 0, tt = 0;bool isEmpty()return hh == tt;bool isFull()return (tt + 1) % N == hh;size_t length()return (tt - hh + N) % N;void push(int val)assert(!isFull());q[tt ++ ] = val;tt %= N;void pop()assert(!isEmpty());int val = q[hh ++ ];hh %= N;

例如，N=5，连续 push 4 个元素，此时 hh=0,tt=4，如果我们再 push，由于 (tt+1)%N==hh，队满，push 失败，因此不会出现队满时 hh==tt 的情况。