[TOC]

队列-Queue

又叫先进先出表；先进先出结构、只允许在一端进行插入操作、而在另一端进行删除操作的线性表。
插入数据的一端是队尾，取数据的一端则是队头

Queue接口主要方法

• boolean add(E e);：增加
• boolean offer(E e);：增加，不会抛IllegalStateException异常(队列满，无法添加)而是返回false
• E remove();：移除
• E poll();：移除，调用空队列时不会抛异常NoSuchElementException，而是返回null
• E element();：取队头数据但不移除
• E peek();：取队头数据但不移除 调用空队列时不会抛异常NoSuchElementException，而是返回null

顺序存储队列

普通队列

数组实现，空队列时，队头、队尾下标均为0，添加元素时，队尾向后移动一位，移除元素时，队头向后移动一位。因为下标一直在往后移动，所以之前释放的元素位置无法再被利用，这样就导致了假溢出现象(无法添加，但队列并不是满的)

循环队列

队列的头尾相接的顺序存储结构。用于解决假溢出现象。

假设循环队列总容量为N，预留一个空的位置(rear永远指向为空的位置)，front为头节点下标，rear为尾节点下标

• 队列空：front==rear;
• 队列满：(rear+1)%N==front;
• 队列元素个数：（rear – front + N)%N 若rear能存放数据：rear>front时：(rear-front)%N+1 rear<front: (rear-front+N)%N+1
• 移除：front = (front+1)%N
• 增加：rear =(rear+1)%N

链式存储队列

其实就是线性表的单链表 ，只不过只能尾进头出

双端队列 Deque

Deque：是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行

• LinkedList
• ArrayDeque
  用数组实现执行效率高
• linkedBlockingDeque

优先级队列

优先级队列和通常的栈和队列一样，只不过里面的每一个元素都有一个”优先级”，在处理的时候，首先处理优先级最高的。如果两个元素具有相同的优先级，则按照他们插入到队列中的先后顺序处理。

• MessageQueue：消息执行时间越早，插入位置越前

• PriorityQueue：重要程度排序

相关算法题

• 手写实现双端队列
• 优先级队列完成CPU调度