AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

Java实现队列——顺序队列、链式队列

2023-01-07 109
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： #### 概念先进者先出，这就是典型的“队列”。(First In, First Out，FIFO)。我们知道，栈只支持两个基本操作：入栈push()和出栈pop()。队列跟栈非常相似，支持的操作也很有限，最基本的操作也是两个：入队和出队。入队 `enqueue()`，让一个数据到队列尾部；出队 `dequeue()`，从队列头部取一个元素。

Java实现队列——顺序队列、链式队列

概念

先进者先出，这就是典型的“队列”。(First In, First Out，FIFO)。

我们知道，栈只支持两个基本操作：入栈push()和出栈pop()。队列跟栈非常相似，支持的操作也很有限，最基本的操作也是两个：入队和出队。入队 enqueue()，让一个数据到队列尾部；出队 dequeue()，从队列头部取一个元素。

栈和队列

所以，队列跟栈一样，也是一种操作受限的线性表数据结构。

跟栈类似，用数组实现的队列叫做顺序队列，用链表实现的队列叫做链式队列。下面我们看下如何用Java代码如何实现。

顺序队列

代码如下：

public class QueueBasedArray implements QueueInterface {
    private String[] values;// 数组
    private int capacity = 0;// 数组容量
    private int head = 0;// 头部下标
    private int tail = 0;// 尾部下标

    public QueueBasedArray(int capacity) {
        values = new String[capacity];
        this.capacity = capacity;
    }

    @Override
    public Boolean enqueue(String value) {
        // tail == capacity 表示队列末尾没有空间了
        if (tail == capacity) {
            // tail == capacity && head == 0 表示整个队列都占满了。
            if (head == 0) {
                return false;
            }
            // 数据搬移
            for (int i = head; i < tail; i++) {
                values[i - head] = values[i];
            }
            // 搬移完成后更新 head 和 tail
            tail -= head;
            head = 0;
        }
        values[tail] = value;
        tail++;
        return true;
    }

    @Override
    public String dequeue() {
        // 如果 head == tail 表示队列为空
        if (0 == tail) {
            return null;
        }
        String result = values[head];
        head++;
        return result;
    }

    @Override
    public String toString() {
        return "QueueBasedArray{" +
                "values=" + Arrays.toString(values) +
                ", capacity=" + capacity +
                ", head=" + head +
                ", tail=" + tail +
                '}';
    }
}

测试代码：

    QueueBasedArray qba = new QueueBasedArray(10);
    System.out.println(qba);

    for (int i = 0; i < 10; i++) {
        qba.enqueue("" + i + i + i);
    }
    System.out.println(qba);

    for (int i = 0; i < 10; i++) {
        qba.dequeue();
        System.out.println(qba);
    }

    for (int i = 11; i < 20; i++) {
        qba.enqueue("" + i + i + i);
    }
    System.out.println(qba);

输出结果：符合预期

QueueBasedArray{values=[null, null, null, null, null, null, null, null, null, null], capacity=10, head=0, tail=0}
QueueBasedArray{values=[000, 111, 222, 333, 444, 555, 666, 777, 888, 999], capacity=10, head=0, tail=10}
QueueBasedArray{values=[000, 111, 222, 333, 444, 555, 666, 777, 888, 999], capacity=10, head=1, tail=10}
QueueBasedArray{values=[000, 111, 222, 333, 444, 555, 666, 777, 888, 999], capacity=10, head=2, tail=10}
QueueBasedArray{values=[000, 111, 222, 333, 444, 555, 666, 777, 888, 999], capacity=10, head=3, tail=10}
QueueBasedArray{values=[000, 111, 222, 333, 444, 555, 666, 777, 888, 999], capacity=10, head=4, tail=10}
QueueBasedArray{values=[000, 111, 222, 333, 444, 555, 666, 777, 888, 999], capacity=10, head=5, tail=10}
QueueBasedArray{values=[000, 111, 222, 333, 444, 555, 666, 777, 888, 999], capacity=10, head=6, tail=10}
QueueBasedArray{values=[000, 111, 222, 333, 444, 555, 666, 777, 888, 999], capacity=10, head=7, tail=10}
QueueBasedArray{values=[000, 111, 222, 333, 444, 555, 666, 777, 888, 999], capacity=10, head=8, tail=10}
QueueBasedArray{values=[000, 111, 222, 333, 444, 555, 666, 777, 888, 999], capacity=10, head=9, tail=10}
QueueBasedArray{values=[000, 111, 222, 333, 444, 555, 666, 777, 888, 999], capacity=10, head=10, tail=10}
QueueBasedArray{values=[111111, 121212, 131313, 141414, 151515, 161616, 171717, 181818, 191919, 999], capacity=10, head=0, tail=9}

链式队列

代码如下：

public class QueueBasedLinkedList implements QueueInterface {
    private Node head;
    private Node tail;

    /**
     * 入队
     *
     * @param value
     * @return
     */
    @Override
    public Boolean enqueue(String value) {
        Node newNode = new Node(value, null);

        // tail为null，表示队列中没有数据
        if (null == tail) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }

        return true;
    }

    /**
     * 出队
     *
     * @return
     */
    @Override
    public String dequeue() {
        // head == null,表示队列为空。
        if (null == head) {
            return null;
        }

        // 获取数据
        String value = head.getItem();
        // 移除头结点，让head指向下一个结点。
        head = head.next;
        // 如果此时的头结点指向null，说明队列已空，需要将tail指向null.
        if (null == head) {
            tail = null;
        }

        return value;
    }

    @Override
    public String toString() {
        return "QueueBasedLinkedList{" +
                "head=" + head +
                ", tail=" + tail +
                '}';
    }

    private static class Node {
        String item;
        private Node next;

        public Node(String item, Node next) {
            this.item = item;
            this.next = next;
        }

        public String getItem() {
            return item;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "item='" + item + '\'' +
                    ", next=" + next +
                    '}';
        }
    }
}

测试代码：

    // 空队列
    QueueBasedLinkedList qbll = new QueueBasedLinkedList();
    System.out.println("空队列 " + qbll);
    System.out.println();

    // 入队一个数据
    System.out.println("数据入队是否成功：" + qbll.enqueue("0000"));
    System.out.println("入队一个数据后：" + qbll);
    System.out.println();

    // 出队一个数据
    System.out.println("出队的数据是：" + qbll.dequeue());
    System.out.println("出队一个数据后：" + qbll);
    System.out.println();

    // 异常测试：从空队列中出队，看结果
    System.out.println("出队的数据是1：" + qbll.dequeue());
    System.out.println("出队一个数据后1：" + qbll);
    System.out.println();

    // 入队十条数据
    for (int i = 0; i < 10; i++) {
        System.out.println("数据入队是否成功：" + qbll.enqueue("" + i + i + i));
        System.out.println(qbll);
    }

输出结果：符合预期

空队列 QueueBasedLinkedList{head=null, tail=null}

数据入队是否成功：true
入队一个数据后：QueueBasedLinkedList{head=Node{item='0000', next=null}, tail=Node{item='0000', next=null}}

出队的数据是：0000
出队一个数据后：QueueBasedLinkedList{head=null, tail=null}

出队的数据是1：null
出队一个数据后1：QueueBasedLinkedList{head=null, tail=null}

数据入队是否成功：true
QueueBasedLinkedList{head=Node{item='000', next=null}, tail=Node{item='000', next=null}}
数据入队是否成功：true
QueueBasedLinkedList{head=Node{item='000', next=Node{item='111', next=null}}, tail=Node{item='111', next=null}}
数据入队是否成功：true
QueueBasedLinkedList{head=Node{item='000', next=Node{item='111', next=Node{item='222', next=null}}}, tail=Node{item='222', next=null}}
数据入队是否成功：true
QueueBasedLinkedList{head=Node{item='000', next=Node{item='111', next=Node{item='222', next=Node{item='333', next=null}}}}, tail=Node{item='333', next=null}}
数据入队是否成功：true
QueueBasedLinkedList{head=Node{item='000', next=Node{item='111', next=Node{item='222', next=Node{item='333', next=Node{item='444', next=null}}}}}, tail=Node{item='444', next=null}}
数据入队是否成功：true
QueueBasedLinkedList{head=Node{item='000', next=Node{item='111', next=Node{item='222', next=Node{item='333', next=Node{item='444', next=Node{item='555', next=null}}}}}}, tail=Node{item='555', next=null}}
数据入队是否成功：true
QueueBasedLinkedList{head=Node{item='000', next=Node{item='111', next=Node{item='222', next=Node{item='333', next=Node{item='444', next=Node{item='555', next=Node{item='666', next=null}}}}}}}, tail=Node{item='666', next=null}}
数据入队是否成功：true
QueueBasedLinkedList{head=Node{item='000', next=Node{item='111', next=Node{item='222', next=Node{item='333', next=Node{item='444', next=Node{item='555', next=Node{item='666', next=Node{item='777', next=null}}}}}}}}, tail=Node{item='777', next=null}}
数据入队是否成功：true
QueueBasedLinkedList{head=Node{item='000', next=Node{item='111', next=Node{item='222', next=Node{item='333', next=Node{item='444', next=Node{item='555', next=Node{item='666', next=Node{item='777', next=Node{item='888', next=null}}}}}}}}}, tail=Node{item='888', next=null}}
数据入队是否成功：true
QueueBasedLinkedList{head=Node{item='000', next=Node{item='111', next=Node{item='222', next=Node{item='333', next=Node{item='444', next=Node{item='555', next=Node{item='666', next=Node{item='777', next=Node{item='888', next=Node{item='999', next=null}}}}}}}}}}, tail=Node{item='999', next=null}}

完整代码请查看

项目中搜索SingleLinkedList即可。

github传送门 https://github.com/tinyvampirepudge/DataStructureDemo

gitee传送门 https://gitee.com/tinytongtong/DataStructureDemo

参考：
队列：队列在线程池等有限资源池中的应用

文章标签：
Java
关键词：
Java队列
Java实现
tinyvvampirepudge
目录
相关文章
GuGuStudy
|
1月前
|
存储 安全 Java
【用Java学习数据结构系列】探索栈和队列的无尽秘密
【用Java学习数据结构系列】探索栈和队列的无尽秘密
GuGuStudy
29 2
过。
|
6月前
|
算法 Java
Java数据结构——队列
Java数据结构——队列
过。
47 4
拉丁解牛说技术
|
2月前
|
Java API 容器
JAVA并发编程系列(10)Condition条件队列-并发协作者
本文通过一线大厂面试真题，模拟消费者-生产者的场景，通过简洁的代码演示，帮助读者快速理解并复用。文章还详细解释了Condition与Object.wait()、notify()的区别，并探讨了Condition的核心原理及其实现机制。
拉丁解牛说技术
55 11
GuGuStudy
|
1月前
|
存储 算法 Java
【用Java学习数据结构系列】用堆实现优先级队列
【用Java学习数据结构系列】用堆实现优先级队列
GuGuStudy
29 0
热爱技术的小郑
|
3月前
|
Java
java中的队列
这篇文章通过Java代码示例介绍了使用数组实现队列操作，包括队列的初始化、入队、出队、判断队列满和空以及遍历队列的方法。
热爱技术的小郑
25 1
java中的队列
杰哥在此
|
4月前
|
设计模式 安全 Java
Java面试题：请解释Java中的线程池以及为什么要使用线程池？请解释Java中的内存模型以及如何避免内存泄漏？请解释Java中的并发工具包以及如何实现一个简单的线程安全队列？
Java面试题：请解释Java中的线程池以及为什么要使用线程池？请解释Java中的内存模型以及如何避免内存泄漏？请解释Java中的并发工具包以及如何实现一个简单的线程安全队列？
杰哥在此
43 1
土木林森
|
5月前
|
Java 开发者
揭秘！LinkedList是如何华丽变身成为Java队列之王的？
【6月更文挑战第18天】Java的`LinkedList`既是列表也是队列之星，实现`Queue`接口，支持FIFO操作。其内部的双向链表结构确保了添加/移除元素的高效性（O(1)），适合作为队列使用。它线程不安全，但可通过同步包装用于多线程环境。此外，`LinkedList`还能灵活变身栈或双端队列，提供多种数据结构功能。
土木林森
56 11
多多!
|
5月前
|
Java
2023蓝桥杯大赛软件类省赛Java大学B组G题 买二增一 队列的简单应用
2023蓝桥杯大赛软件类省赛Java大学B组G题 买二增一 队列的简单应用
多多!
36 1
土木林森
|
5月前
|
安全 Java
Java Queue新玩法：用LinkedList打造高效队列，让你的代码飞起来！
【6月更文挑战第18天】Java集合框架中的`LinkedList`不仅是列表，还可作为高效队列。由于其在链表两端进行添加/移除操作的时间复杂度为O(1)，故适合实现并发环境下的任务队列。通过案例展示了如何创建、添加任务及确保线程安全，揭示了`LinkedList`提升代码性能的秘密，特别是在多线程应用中的价值。
土木林森
50 4
土木林森
|
5月前
|
安全 Java 调度
Java Queue深度解析：LinkedList为何成为队列的最佳实践？
【6月更文挑战第18天】Java的`LinkedList`适合作为队列，因其双向链表结构支持O(1)的头尾操作。非线程安全的`LinkedList`在单线程环境下效率高，多线程时可通过`Collections.synchronizedList`封装。此外，它还可兼做栈和双端队列，提供任务调度的高效解决方案。
土木林森
61 3

热门文章

最新文章

  • 1
    java集成opencv(不踩坑),实现人脸检测小demo(含上传人像图片识别接口),windows,IDEA,Springboot
  • 2
    java Redis工具类
  • 3
    JAVA SERVLET 属性范围样例
  • 4
    Java一分钟之-JavaMail：发送电子邮件
  • 5
    2024年全新基于Java爬取微博数据（完整版）
  • 6
    Java的几种创建实例方法的性能对比
  • 7
    Java杂记9—NIO
  • 8
    16.2. jps - Java Virtual Machine Process Status Tool
  • 9
    Java多线程初学者指南（9）：为什么要进行数据同步
  • 10
    Java——基于java自身包实现消息系统间的通信（TCP/IP+BIO）
  • 1
    java接口防爬虫
    127
  • 2
    day14：Java零基础-条件运算符
    40
  • 3
    Java并发编程中的锁机制与性能优化
    50
  • 4
    深入理解Java虚拟机：垃圾收集机制的演变与最佳实践
    49
  • 5
    《手把手教你》系列基础篇（九十五）-java+ selenium自动化测试-框架之设计篇-java实现自定义日志输出（详解教程）
    293
  • 6
    Java并发编程之线程池深度解析
    61
  • 7
    Java中的并发编程：从基础到高级
    62
  • 8
    Java并发编程中的线程安全性与性能优化
    53
  • 9
    《手把手教你》系列基础篇（九十四）-java+ selenium自动化测试-框架设计基础-POM设计模式实现-下篇（详解教程）
    46
  • 10
    Spring Boot框架在java领域的优势
    74

    • 相关课程

    更多
  • Java面试疑难点解析 - 面试技巧及语言基础
  • Java面试疑难点解析 - Java Web开发
  • Java面试疑难点解析 - 系统架构及项目设计
  • Java编程入门
  • Java面向对象编程
  • Java高级编程

    • 相关电子书

    更多
  • Spring Cloud Alibaba - 重新定义 Java Cloud-Native
  • The Reactive Cloud Native Arch
  • JAVA开发手册1.5.0

    • 相关实验场景

    更多
  • 阿里云平台上进行Java程序的编译与运行
  • 使用Java面向对象编写网络通信程序应用
  • 手动部署Java Web环境（Alibaba Cloud Linux 2）
  • 搭建Java Web开发环境（Anolis OS）
  • RocketMQ中使用Java客户端发送消息和消费的应用
  • 部署基于Dragonwell的Java运行环境
    • 下一篇
    阿里云OSS设置跨域访问