队列Queue的认识

发表于 分类于 阅读次数：

队列Queue

  • 队列也是一种线性结构
  • 相比数组，队列对应的操作是数组的子集
  • 只能从一端（队尾）添加元素，只能从另一端（队首）取出元素
  • 队列是一种 先进先出FIFO (First In First Out) 的数据结构

队列的实现

1
2
3
4
5
6
Queue<E>
void enqueue(E e); //入队
E dequeue();  //出队
E getFront();  //获取队首元素
int getSize();
boolean isEmpty();

源码

数组队列的复杂度分析

ArrayQueue

  • void enqueue(E e) O(1) 均摊
  • E dequeue() O(n)
  • E getFront() O(1)
  • int getSize() O(1)
  • boolean isEmpty() O(1)

出队操作时，所有元素都向前移动一位，所以复杂度是O(n)，当所需处理的数据达到百万条时，处理速度就会慢到普通家用计算机都需要等很久才能处理完成。解决方法是：循环队列

循环队列

循环队列的示意图

  • front 标记队首元素
  • tail 标记队尾元素
  • 当 front == tail 时，队列为空
  • 当 ( tail + 1 ) % capacity == front时， 队列为满
  • 在capacity中，有意识地浪费一个空间（队列还有一个空间时，再插入一个元素会使tail == front，这与队列为空条件相冲）

循环队列的实现

实现Queue接口的方法，具体在这 源码

循环队列的复杂度分析

LoopQueue

  • void enqueue(E e) O(1) 均摊
  • E dequeue() O(1) 均摊
  • E getFront() O(1)
  • int getSize() O(1)
  • boolean isEmpty() O(1)

数组队列和循环队列的性能比较

具体比较看 这里