循环队列的边界判定

引言

循环队列通常使用数组来实现，需要定义队头head和队尾tail两个指针，在每次入队时tail++出队时head++。但是在判断队列空和满时总是想不明白，这里记录一下。

指针初始化

在初始化头尾指针时，有两种初始化方式：

1. 头指针和尾指针分别指向对应的头尾节点

int head=0, tail=-1;

2. 头指针指向头节点，尾指针指向尾节点的下一个结点

int head=0, tail=0;

可以看到，不管是哪种初始化方式，队列空时和队列满时的头尾指针相对位置都是一样的。

判断空、满

在这种情况下怎么判断队列到底是空还是满呢？也有两种方式：

1. 引入size字段，表示队列长度

此时不论使用哪种初始化方式，都可以完全不管头尾指针的位置，直接使用size来判断。

• 判断队列空：size==0;
• 判断队列满：size==maxLength;

2. head和tail只增不减

与上面在入队（或出队）后需要tail=(tail+1)%maxLength不同，每次入队（或出队）后只需要tail++，而不用取余。
这样的好处就是可以通过相减得到当前队列大小size，然后再通过size来判断队列的空和满。

不同初始化方式的size计算

• 对于第一种初始化方式：int head=0, tail=-1;，size=tail-head+1;
• 对于第二种初始化方式：int head=0, tail=0;，size=tail-head。

LeetCode链接

622. 设计循环队列