基本算法和数据结构

对自己在学习基础算法和数据结构之中的一些个人问题的记录

Posted by Haiming on May 5, 2019

在给自己弥补算法和数据结构基础时候,作为小白经常有一些问题,或者是质疑算法,或者是质疑数据结构的设计,但是最后总是被自己打脸……开一个post,将这些“奇思妙想”记录下来,也防止自己以后再犯一样的错误。

1. 循环队列

循环队列,使用两个指针进行判断,一个是front队首,指向的就是队列之中的第一个元素,一个是tail队尾,指向的是队列之中的最后一个元素的后一位。这就导致了,如果只想使用一个队列,不加上任何的辅助信息(比如单独设置一个bit位确认其是否已满),如果队列长度为N,那么其容量只可以是(N-1),因为要留一个位置判断其是否为空。

如果将队尾元素不指向最后一个之后的空位置,而是指向最后一个元素,是否就可以省掉这个空元素了呢?答案是否定的。因为这种情况没法区分队列为空和队列之中有一个元素(二者都是front==tail),所以这一个循环队列之中的空位置是省略不掉的。