AI 助理
备案控制台
开发者社区 人工智能 文章 正文

4.[数据结构和算法分析笔记]队列 Queue

2017-11-09 1124
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：

1.队列Queue

定义

队列又叫做FIFO（先进先出）表，即first-in，first-out

现实中的队列

——排队

队列的接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public  interface  QueueInterface<T> {
     /**
      * 将新元素插入队列后端
      * @param newEntry 待插入的对象 */
     public  void  enqueue(T newEntry);
     /**
      * 删除并返回队列前端对象
      * @return 位于队列前端的对象，如果队列为空则返回null */
     public  T dequeue();
     /**
      * 检索队列前端对象
      * @return 位于队列前端的对象，如果队列为空则返回null */
     public  T getFront();
     /**
      * 检查队列是否为空
      * @return 如果队列为空则返回true */
     public  boolean  isEmpty();
     /**
      * 从队列中删除所有元素 */
     public  void  clear();
}

Java类库：Queue接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public  interface  Queue<T> {
     // 在对象的末端插入一个新元素，如果插入成功则返回true，否则抛出一个异常
     public  boolean  add(T newEntry);
     // 在对象的末端插入一个新元素，根据此操作成功与否返回true或false
     public  boolean  offer(T newEntry);
     // 在队列的前端检索并删除元素，如果在此操作之前队列已为空，则抛出异常NoSuchElementException
     public  T remove();
     // 在队列的前对检索并删除元素，如果在此操作之前队列已为空，则返回null
     public  T poll();
     // 检索队列前端的元素，如果队列为空，则抛出异常NoSuchelementException
     public  T element();
     // 检索队列前端的元素，如果队列为空，则返回null
     public  T peek();
     // 检索队列是否为空
     public  boolean  isEmpty();
     // 删除队列的所有元素
     public  void  clear();
     // 获得当前队列中的元素数据
     public  int  size();
     // 返回作用于队列的元素的迭代期器
     public  Iterator<T> iterator();
}

双端队列接口描述

1
2
3
4
5
6
7
8
9
10
11
public  interface  DequeInterface<T> {
                                 
     public  void  addToFront(T newEntry);
     public  void  addToBack(T newEntry);
     public  T removeFront();
     public  T removeBack();
     public  T getFront();
     public  T getBack();
     public  boolean  isEmpty();
     public  void  clear();  
}

优先队列的接口描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public  interface  PriorityQueueInterface<T  extends  Comparable<?  super  T>> {
     /**
      * 将新元素插入优先队列
      * @param newEntry newEntry一个对象 */
     public  void  add(T newEntry);
     /**
      * 删除并返回优先队列最高的元素
      * @return 优先级最高的对象，如果优先队列为空则返回null */
     public  T remove();
     /**
      * 检索优先级最高的元素
      * @return 优先级最高的对象，如果优先队列为空则返回null */
     public  T peek();
     /**
      * 检索优先队列是否为空
      * @return 如果优先队列为空则返回true */
     public  boolean  isEmpty();
     /**
      * 缺德优先队列的长度
      * @return 当前优先队列中的元素数据 */
     public  int  getSize();
     /**
      * 从优先队列中删除所有元素 */
     public  void  clear();
}

2.基于(双端)链表的队列实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public  class  LinkedQueue<T>  implements  QueueInterface<T>, Serializable {
     private  Node firstNode;  // 引用队列前端的结点
     private  Node lastNode;  // 引用队列后端的结点
     public  LinkedQueue() {
         firstNode =  null ;
         lastNode =  null ;
     }
     private  class  Node  implements  Serializable {
         private  T data;  // entry in queue
         private  Node next;  // link to next queue
     }
     // 在后端插入
     public  void  enqueue(T newEntry) {
         Node newNode =  new  Node(newEntry,  null );
         if  (isEmpty())
             firstNode = newNode;
         else
             lastNode.setNext(newNode);
         lastNode = newNode;
     }
     // 删除前端元素
     public  T dequeue() {
         T front =  null ;
         if  (!isEmpty()) {
             front = firstNode.getData();
             firstNode = firstNode.getNext();
             if  (firstNode ==  null )
                 lastNode =  null ;
         }
         return  front;
     }
     // 检索前端元素
     public  T getFront() {
         T front =  null ;
         if  (!isEmpty())
             front = firstNode.getData();
         return  front;
     }
     public  boolean  isEmpty() {
         return  firstNode ==  null ;
     }
     public  void  clear() {
         firstNode =  null ;
         lastNode =  null ;
     }
}

3.基于(循环)数组的队列实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public  class  ArrayQueue<T>  implements  QueueInterface<T>, Serializable {
     private  T[] queue;  // 存放队列元素的循环数组
     private  int  frontIndex;
     private  int  backIndex;
     private  static  final  int  DEFAULT_INITIAL_CAPACITY =  50 ;
     public  ArrayQueue() {
         this (DEFAULT_INITIAL_CAPACITY);
     }
     public  ArrayQueue( int  initialCapacity) {
         queue = (T[])  new  Object[DEFAULT_INITIAL_CAPACITY +  1 ];
         frontIndex =  0 ;
         backIndex = initialCapacity;
     }
     // 在后端插入
     public  void  enqueue(T newEntry) {
         if  (isArrayFull()) {
             // 扩建数组
         }
         backIndex = (backIndex +  1 ) % queue.length;  // 由于数组是循环的，需要使用取余（%）操作符，以使backIndex达到其最大值之后变回0
         queue[backIndex] = newEntry;
     }
     // 删除前端元素
     public  T dequeue() {
         T front =  null ;
         if  (!isEmpty()) {
             front = queue[frontIndex];
             queue[frontIndex] =  null ;
             frontIndex = (frontIndex +  1 ) % queue.length;
         }
         return  front;
     }
     // 检索前端元素
     public  T getFront() {
         T front =  null ;
         if  (!isEmpty())
             front = queue[frontIndex];
         return  front;
     }
     public  boolean  isEmpty() {
         return  frontIndex == ((backIndex +  1 ) % queue.length);
     }
     private  boolean  isArrayFull() {
         return  frontIndex == ((backIndex +  2 ) % queue.length);
     }
}

4.基于双端链表的双端队列实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public  class  LinkedDeque<T>  implements  DequeInterface<T>, Serializable {
     private  DLNode firstNode;  // 引用双端队列的前端结点
     private  DLNode lastNode;  // 引用双端队列的后端结点
     public  LinkedDeque() {
         firstNode =  null ;
         lastNode =  null ;
     }
     private  class  DLNode  implements  Serializable {
         private  T data;
         private  DLNode next;
         private  DLNode previous;
     }
     // 插入元素
     public  void  addToBack(T newEntry) {
         DLNode newNode =  new  DLNode(newEntry, lastNode,  null );
         if (isEmpty())
             firstNode = newNode;
         else
             lastNode.setNext(newNode);
         lastNode = newNode;
     }
     public  void  addToFront(T newEntry) {
         DLNode newNode =  new  DLNode(newEntry,  null , firstNode);
         if (isEmpty())
             lastNode = newNode;
         else
             firstNode.setPrevious(newNode);
         firstNode = newNode;
     }
     // 删除元素
     public  T removeFront() {
         T front =  null ;
         if (!isEmpty()) {
             front = firstNode.getData();
             firstNode = firstNode.getNext();
             if (firstNode ==  null )
                 lastNode =  null ;
             else  firstNode.setPrevious( null );
         }
         return  front;
     }
     public  T removeBack() {
         T back =  null ;
         if (!isEmpty()) {
             back = lastNode.getData();
             lastNode = lastNode.getPrevious();
             if (lastNode ==  null )
                 firstNode =  null ;
             else
                 lastNode.setNext( null );
         }
         return  back;
     }
}

5.实现优先队列的方法

可以使用数组或链表实现优先队列。

但使用堆实现优先队列是一种更高效的方法。










本文转自 LinkedKeeper 51CTO博客，原文链接：http://blog.51cto.com/sauron/1226594，如需转载请自行联系原作者
文章标签：
算法
前端开发
关键词：
算法分析
数据结构算法
数据结构队列
数据结构分析
算法队列
余二五
目录
相关文章
陌陌谣
|
3月前
|
运维 监控 JavaScript
基于 Node.js 图结构的局域网设备拓扑分析算法在局域网内监控软件中的应用研究
本文探讨图结构在局域网监控系统中的应用，通过Node.js实现设备拓扑建模、路径分析与故障定位，提升网络可视化、可追溯性与运维效率，结合模拟实验验证其高效性与准确性。
陌陌谣
242 3
天隆金
|
6月前
|
机器学习/深度学习 边缘计算 算法
NOMA和OFDMA优化算法分析
NOMA和OFDMA优化算法分析
天隆金
338 127
Echo_Wish
|
8月前
|
数据采集 机器学习/深度学习 算法
别急着上算法，咱先把数据整明白：大数据分析的5个基本步骤，你都搞对了吗？
别急着上算法，咱先把数据整明白：大数据分析的5个基本步骤，你都搞对了吗？
Echo_Wish
490 4
大数据文摘
|
8月前
|
前端开发 Java
java实现队列数据结构代码详解
本文详细解析了Java中队列数据结构的实现，包括队列的基本概念、应用场景及代码实现。队列是一种遵循“先进先出”原则的线性结构，支持在队尾插入和队头删除操作。文章介绍了顺序队列与链式队列，并重点分析了循环队列的实现方式以解决溢出问题。通过具体代码示例（如`enqueue`入队和`dequeue`出队），展示了队列的操作逻辑，帮助读者深入理解其工作机制。
大数据文摘
265 1
荔枝科研社
|
3月前
|
存储 边缘计算 算法
【太阳能学报EI复现】基于粒子群优化算法的风-水电联合优化运行分析（Matlab代码实现）
【太阳能学报EI复现】基于粒子群优化算法的风-水电联合优化运行分析（Matlab代码实现）
荔枝科研社
82 0
荔枝科研社
|
4月前
|
机器学习/深度学习 算法 5G
【MUSIC、最大似然与克拉美-罗下界】MUSIC与ESPRIT 算法来估计到达角(AoA)，并尝试推导克拉美-罗下界(CRLB)以分析其性能研究（Matlab代码实现）
【MUSIC、最大似然与克拉美-罗下界】MUSIC与ESPRIT 算法来估计到达角(AoA)，并尝试推导克拉美-罗下界(CRLB)以分析其性能研究（Matlab代码实现）
荔枝科研社
183 0
哈你真皮
|
5月前
|
编解码 算法 5G
MIMO雷达空间谱估计中Capon算法与MUSIC算法的对比分析及实现
MIMO雷达空间谱估计中Capon算法与MUSIC算法的对比分析及实现
哈你真皮
383 2
陌陌谣
|
5月前
|
存储 监控 安全
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据，传统数据结构存在性能瓶颈。红黑树通过自平衡机制，确保查找、插入、删除操作的时间复杂度稳定在 O(log n)，适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现，并探讨其在企业监控系统中的实践价值，提升系统性能与稳定性。
陌陌谣
169 1
老赵聊算法备案、大模型备案
|
5月前
|
人工智能 自然语言处理 算法
2025 年 7 月境内深度合成服务算法备案情况分析报告
2025年7月，中央网信办发布第十二批深度合成算法备案信息，全国389款产品通过备案，服务提供者占比超七成。截至7月14日，全国累计备案达3834款，覆盖文本、图像、音视频等多模态场景，广泛应用于生活服务、医疗、金融等领域。广东以135款居首，数字人、AI客服等C端应用主导，民营企业成主力，国企聚焦公共服务。随着AI政策推动，备案已成为AI产品合规上线关键环节。
老赵聊算法备案、大模型备案
323 1
陌陌谣
|
5月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表（Skip List）是一种基于概率的数据结构，适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作，时间复杂度为 $O(\log n)$，优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色，具备实现简单、支持范围查询等优势，是企业网络监控中动态数据管理的理想选择。
陌陌谣
158 0

热门文章

最新文章

  • 1
    当“爆款书”遇上大数据：出版业的老路，正在被算法改写
  • 2
    （Python基础）新时代语言！一起学习Python吧！（一）：认识Python、Py解释器作用；编写第一个Python程序；Python中的基本数据结构
  • 3
    （Pandas）Python做数据处理必选框架之一！（一）：介绍Pandas中的两个数据结构；刨析Series：如何访问数据；数据去重、取众数、总和、标准差、方差、平均值等；判断缺失值、获取索引...
  • 4
    【机器学习算法篇】K-近邻算法
  • 5
    要不要做算法、大模型备案？看这个流程图就明白了！
  • 6
    别再用均值填充了！MICE算法教你正确处理缺失数据
  • 7
    《数据之美》：图结构的精妙世界与算法实践
  • 8
    从零掌握贪心算法Java版：LeetCode 10题实战解析（上）
  • 9
    企业上网监控系统的恶意 URL 过滤 Node.js 布隆过滤器算法
  • 10
    【水下图像增强融合算法】基于融合的水下图像与视频增强研究（Matlab代码实现）
  • 1
    当“爆款书”遇上大数据：出版业的老路，正在被算法改写
    168
  • 2
    当AI成为航天员的“大脑外设”：智能算法如何优化人类的长期太空旅行
    140
  • 3
    电脑监控管理中的 C# 哈希表进程资源索引算法
    173
  • 4
    HNSW算法实战：用分层图索引替换k-NN暴力搜索
    165
  • 5
    基于python智能推荐算法的全屋定制系统
    176
  • 6
    使用哈里斯角Harris和SIFT算法来实现局部特征匹配（Matlab代码实现）
    158
  • 7
    基于导向滤波的暗通道去雾算法在灰度与彩色图像可见度复原中的研究（Matlab代码实现）
    168
  • 8
    【水下图像增强融合算法】基于融合的水下图像与视频增强研究（Matlab代码实现）
    231
  • 9
    结合多种启发式解码方法的混合多目标进化算法，用于解决带工人约束的混合流水车间调度问题（Matlab代码实现）
    148
  • 10
    【基于TTNRBO优化DBN回归预测】基于瞬态三角牛顿-拉夫逊优化算法（TTNRBO）优化深度信念网络（DBN）数据回归预测研究（Matlab代码实现）
    139

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 基于深度学习的广告CTR预估算法
  • 解密阿里内部人工智能算法迭代工具AI Boost
  • Apache Flink 流式应用中状态的数据结构定义升级
    • 下一篇
    对象存储OSS快速上手——如何使用ossbrower2