天天看点

Java数据结构之何为队列

          没有java数据结构的基础,如何优化Android应用的性能?在实际生活中,队列有着广泛的应用,例如排队购物,文章打印,都遵循着队列先进先出的原则。队列queue在我们Handel looper thread那章中我们讲解过,今天我们重点解析下Queue的性质。

          队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入,而在另一端进行删除。允许删除的一端称为队头(front),允许插入的一端称为队尾(rear)。

        顺序  queue的相关概念

        ?进行插入操作的端称为队尾,进行删除操作的端称为队头。

        ?队列中没有元素时,称为空队列。

        ?队列空的条件:  front = rear

        ?队列满的条件:  rear = MAXSIZE

       从上述相关概念中,顺序队列有一个很大的问题,容易出现假溢,如下图所示。

Java数据结构之何为队列

          因此,我们设计了循环队列,将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。注意循环队列 的队列满的条件为(rear+1)%MaxSize=front,为了避免与队空条件冲突,预留了一个空间。

Java数据结构之何为队列

 下面我们来看一下如何实现上述的循环队列。

继续阅读