数据结构-队列小结

数据结构之队列

对比学习法:通过对比A和B的不同和差异来学习A和B

前置知识

数组和链表的知识

1. 先进先出队列(FIFO QUEUE)

1.1 理论知识

只允许头出,尾进。像排队一样。

如果是先进后出.则是栈。

对数组和链表可以随机存取,对队列只能尾存头取,是随机存取的一个操作子集。所以,队列其实是数组和链表就可以实现

1.2 实现

基于数组实现:

数组头部移出,尾部插入,只需要一个数组和头尾两个指针即可实现。

效率:

• 头取效率 O(1)
• 尾存效率 O(1)

缺点:

• 假溢出: 数组长度有限,尾部不断添加,导致头部有大量空白的情况下,数组越界。

因此: 引入循环队列的概念。

基于链表实现:

链表本身就是队列的父集合,单向链表+头尾指针就可以实现队列，所以java中没有链表队列实现，直接链表就可以起到相同作用

效率:

• 头取效率 O(1)
• 尾存效率 O(1)

小结:

单向链表可以替代队列实现

数组实现有假溢出的问题。

2.循环队列

因为链表不存在容量问题,所以循环链表只针对数组实现

数组实现的先进先出链表存在假溢出问题,为了解决假溢出问题,提出循环链表概念。

1.头指针表示出队位置。

2.尾指针表示入队位置。

3.当尾指针达到数组最后的位置的时候,跳到数组开头的位置,头指针也相同处理。

缺点: 容量有限,和数组容量相同,如果队列同时容纳的人超过了数组长度,则首尾碰撞,出现异常。

解决办法: 自动扩容机制

小结:

数组可以通过循环链表+扩容机制,实现先进先出队列。

注: 为什么要这么实现而不使用链表

答: 对于普通的先进先出队列,链表实现更合适。

3.双向队列

单向先进先出队列=头出尾插

双向先进先出队列=头出尾插+头插尾出=头插头出+尾插尾出

双向队列 天然包括 单向队列

因此,实现双向队列就代表实现了单向队列。

数组实现

数组本身就带有前后的概念,所以头尾指针的前后移动即可表示双向。

因此: 循环数组队列 = 双向队列 > 单向队列

链表实现

双向链表即可天然实现双向队列

小结:

java中的队列类：

ArrayDeque 循环数组实现的双向队列

LinkedList: 双向链表实现的双向队列

在不影响效率的情况下,天然包括了单向队列,因此,无须重复实现单向队列。

4.优先级队列

优先级队列表示,在队列中等待的成员,并不按照时间进行出队,而是按照指定的优先级进行出队。

优先级队列天然包括普通的先进先出队列。

因为先进先出队列 = 按时间优先级进出的队列 < 优先级队列

优先级队列的实现原理是: 最大堆,最小堆

数组实现

数组实现堆

链表实现

链表实现堆

小结:

java中的PriorityQueue是 自动扩容+数组+最小堆实现

java 队列

java中的队列

• java.util 这里是线程不安全的队列
  • Queue 单向先进先出队列接口定义
  • Deque 双向先进先出队列接口定义
  • ArrayDeque 数组实现的双向队列 自动扩容+数组实现
  • LinkedList: 双向链表 可以替代 链表实现的双向队列
  • PriorityQueue 数组+自动扩容+最小堆实现的优先级队列
• java.util.concurrent 下面是线程安全的队列
  • BlockingQueue 阻塞(线程安全)队列接口定义
  • LinkedBlockingQueue 单向链表实现的单向队列
  • ArrayBlockingQueue 自动扩容+数组实现的单向队列
  • PriorityBlockingQueue 数组+自动扩容+最小堆实现的优先级队列