标签:FIFO

队列java实现

发表于3年前(Dec 24, 2014 10:24:48 AM)  阅读 480  评论 0

分类: Java 数据结构

标签: FIFO queue 先进先出 队列

队列和栈相反,是先进先出(FIFO,first in first out)的数据集合。就跟排队打饭一样,最先进入队伍的总是最先离开。

队列元素的操作一般由入列(enQueue)和出列(deQueue)组成。 按照通常理解,如果队首的人离开,队伍中所有的人将往前挪一个位置,在下面的代码里,我没有这么做,因为如果每次出列都进行一次平移,就造成了多次元素交换,影响效率,当然如果你不在乎可以进行平移。取而代之的是,用两个索引head跟tail来标记当前队首跟队尾元素的索引,避免了移位。在这里,没有实现队列的自动增长,使用索引来标记队首队尾元素,增加了自动增长的难度,其实也很简单,只是暂时觉得没有必要实现。