Java数据结构与算法——队列

简介: Java数据结构与算法——队列

1.简介


队列是一个有序列表,可以用数组或是链表来实现。遵循先入先出的原则。即:先存入队列的数据,要先取出。后存入的要后取出。

队列本身是有序列表,若使用数组的结构来存储队列的数据,则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量。

因为队列的输出、输入是分别从前后端来处理,因此需要两个变量 front rear分别记录队列前后端的下标,front 会随着数据输出而改变,而 rear则是随着数据输入而改变,如图所示:


2.数组模拟普通队列


当我们将数据存入队列时称为”addQueue”addQueue 的处理需要有两个步骤:思路分析

将尾指针往后移:rear+1 , front == rear 【空】

若尾指针 rear 小于队列的最大下标 maxSize-1,则将数据存入 rear所指的数组元素中,否则无法存入数据。 rear  == maxSize - 1[队列满]

package com.szh.queue;
import java.util.Scanner;
/**
 *
 */
class ArrayQueue {
    private Integer maxSize; //队列的最大容量
    private Integer front;   //队列头
    private Integer rear;    //队列尾
    private Integer[] arr;   //数组模拟队列
    public ArrayQueue(Integer maxSize) {
        this.maxSize = maxSize;
        arr = new Integer[this.maxSize]; //创建队列
        this.front = -1; //指向队列头的前一个位置
        this.rear = -1;  //指向队列尾的当前位置
    }
    //判断队列是否已满
    public boolean isFull() {
        return rear == maxSize - 1;
    }
    //判断队列是否为空
    public boolean isEmpty() {
        return rear == front;
    }
    //向队列中添加数据
    public void addQueue(int n) {
        if (isFull()) {
            System.out.println("队列已满,无法继续添加数据。");
            return;
        }
        arr[++rear] = n;
    }
    //从队列中取出数据
    public int getQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列已空,无法继续取出数据。");
        }
        return arr[++front];
    }
    //显示队列中所有的数据
    public void showQueue() {
        if (isEmpty()) {
            System.out.println("队列空的,没有数据....");
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("arr[%d]=%d\n", i, arr[i]);
        }
    }
    //显示队列的头数据
    public int headQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列空的,没有数据....");
        }
        return arr[front + 1];
    }
}
public class ArrayQueueDemo {
    public static void main(String[] args) {
        //创建一个队列
        ArrayQueue arrayQueue = new ArrayQueue(3);
        Scanner input = new Scanner(System.in);
        char key = ' ';
        boolean loop = true;
        //菜单循环
        while (loop) {
            System.out.println("s(show): 显示队列");
            System.out.println("e(exit): 退出程序");
            System.out.println("a(add): 添加数据到队列");
            System.out.println("g(get): 从队列取出数据");
            System.out.println("h(head): 查看队列头的数据");
            key = input.next().charAt(0); //从控制台接收一个字符
            switch (key) {
                case 's':
                    arrayQueue.showQueue();
                    break;
                case 'a':
                    System.out.print("请输入要添加的数据:");
                    int value = input.nextInt();
                    arrayQueue.addQueue(value);
                    break;
                case 'g':
                    int res = arrayQueue.getQueue();
                    System.out.println("取出的数据是:" + res);
                    break;
                case 'h':
                    int ans = arrayQueue.headQueue();
                    System.out.printf("队列头的数据是%d\n", ans);
                    break;
                case 'e':
                    input.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出....");
    }
}

3.数组模拟环形队列


对前面的数组模拟队列的优化,充分利用数组. 因此将数组看做是一个环形的。(通过取模的方式来实现即可)

分析说明:尾索引的下一个为头索引时表示队列满,即将队列容量空出一个作为约定,这个在做判断队列满的时候需要注意 (rear + 1) % maxSize == front ]

rear == front []

package com.szh.queue;
import java.util.Scanner;
/**
 *
 */
class CircleArrayQueue {
    private int maxSize; // 表示数组的最大容量
    //front 变量的含义做一个调整: front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素
    //front 的初始值 = 0
    private int front;
    //rear 变量的含义做一个调整:rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定.
    //rear 的初始值 = 0
    private int rear; // 队列尾
    private int[] arr; // 该数据用于存放数据, 模拟队列
    public CircleArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        arr = new int[maxSize];
        this.front = 0;
        this.rear = 0;
    }
    //判断队列是否已满
    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }
    //判断队列是否为空
    public boolean isEmpty() {
        return rear == front;
    }
    //向队列中添加数据
    public void addQueue(int n) {
        if (isFull()) {
            System.out.println("队列已满,无法继续添加数据。");
            return;
        }
        //直接将数据加入
        arr[rear] = n;
        //将 rear 后移, 这里必须考虑取模
        rear = (rear + 1) % maxSize;
    }
    //从队列中取出数据
    public int getQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列已空,无法继续取出数据。");
        }
        //这里需要分析出 front 是指向队列的第一个元素
        //先把 front 对应的值保留到一个临时变量
        int res = arr[front];
        //将 front 后移, 考虑取模
        front = (front + 1) % maxSize;
        //将临时保存的变量返回
        return res;
    }
    //显示队列中所有的数据
    public void showQueue() {
        if (isEmpty()) {
            System.out.println("队列空的,没有数据....");
            return;
        }
        int num = size();
        for (int i = front; i < front + num; i++) {
            System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
        }
    }
    //显示队列的头数据
    public int headQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列空的,没有数据....");
        }
        return arr[front];
    }
    // 求出当前队列有效数据的个数
    public int size() {
        return (rear + maxSize - front) % maxSize;
    }
}
public class CircleArrayQueueDemo {
    public static void main(String[] args) {
        //创建一个队列, 说明设置4, 其队列的有效数据最大是3
        CircleArrayQueue arrayQueue = new CircleArrayQueue(4);
        Scanner input = new Scanner(System.in);
        char key = ' ';
        boolean loop = true;
        //菜单循环
        while (loop) {
            System.out.println("s(show): 显示队列");
            System.out.println("e(exit): 退出程序");
            System.out.println("a(add): 添加数据到队列");
            System.out.println("g(get): 从队列取出数据");
            System.out.println("h(head): 查看队列头的数据");
            key = input.next().charAt(0); //从控制台接收一个字符
            switch (key) {
                case 's':
                    arrayQueue.showQueue();
                    break;
                case 'a':
                    System.out.print("请输入要添加的数据:");
                    int value = input.nextInt();
                    arrayQueue.addQueue(value);
                    break;
                case 'g':
                    int res = arrayQueue.getQueue();
                    System.out.println("取出的数据是:" + res);
                    break;
                case 'h':
                    int ans = arrayQueue.headQueue();
                    System.out.printf("队列头的数据是%d\n", ans);
                    break;
                case 'e':
                    input.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出....");
    }
}

相关文章
|
5月前
|
负载均衡 算法 关系型数据库
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
本文聚焦 MySQL 集群架构中的负载均衡算法,阐述其重要性。详细介绍轮询、加权轮询、最少连接、加权最少连接、随机、源地址哈希等常用算法,分析各自优缺点及适用场景。并提供 Java 语言代码实现示例,助力直观理解。文章结构清晰,语言通俗易懂,对理解和应用负载均衡算法具有实用价值和参考价值。
大数据大厂之MySQL数据库课程设计:揭秘MySQL集群架构负载均衡核心算法:从理论到Java代码实战,让你的数据库性能飙升!
|
5月前
|
存储 缓存 监控
上网行为监控系统剖析:基于 Java LinkedHashMap 算法的时间序列追踪机制探究
数字化办公蓬勃发展的背景下,上网行为监控系统已成为企业维护信息安全、提升工作效能的关键手段。该系统需实时记录并深入分析员工的网络访问行为,如何高效存储和管理这些处于动态变化中的数据,便成为亟待解决的核心问题。Java 语言中的LinkedHashMap数据结构,凭借其独有的有序性特征以及可灵活配置的淘汰策略,为上网行为监控系统提供了一种兼顾性能与功能需求的数据管理方案。本文将对LinkedHashMap在上网行为监控系统中的应用原理、实现路径及其应用价值展开深入探究。
111 3
|
5月前
|
人工智能 算法 NoSQL
LRU算法的Java实现
LRU(Least Recently Used)算法用于淘汰最近最少使用的数据,常应用于内存管理策略中。在Redis中,通过`maxmemory-policy`配置实现不同淘汰策略,如`allkeys-lru`和`volatile-lru`等,采用采样方式近似LRU以优化性能。Java中可通过`LinkedHashMap`轻松实现LRUCache,利用其`accessOrder`特性和`removeEldestEntry`方法完成缓存淘汰逻辑,代码简洁高效。
209 0
|
6月前
|
前端开发 Java
java实现队列数据结构代码详解
本文详细解析了Java中队列数据结构的实现,包括队列的基本概念、应用场景及代码实现。队列是一种遵循“先进先出”原则的线性结构,支持在队尾插入和队头删除操作。文章介绍了顺序队列与链式队列,并重点分析了循环队列的实现方式以解决溢出问题。通过具体代码示例(如`enqueue`入队和`dequeue`出队),展示了队列的操作逻辑,帮助读者深入理解其工作机制。
169 1
|
4月前
|
存储 算法 安全
Java中的对称加密算法的原理与实现
本文详细解析了Java中三种常用对称加密算法(AES、DES、3DES)的实现原理及应用。对称加密使用相同密钥进行加解密,适合数据安全传输与存储。AES作为现代标准,支持128/192/256位密钥,安全性高;DES采用56位密钥,现已不够安全;3DES通过三重加密增强安全性,但性能较低。文章提供了各算法的具体Java代码示例,便于快速上手实现加密解密操作,帮助用户根据需求选择合适的加密方案保护数据安全。
353 58
|
3月前
|
存储 负载均衡 算法
我们来说一说 Java 的一致性 Hash 算法
我是小假 期待与你的下一次相遇 ~
118 1
|
3月前
|
存储 监控 算法
企业上网监控场景下布隆过滤器的 Java 算法构建及其性能优化研究
布隆过滤器是一种高效的数据结构,广泛应用于企业上网监控系统中,用于快速判断员工访问的网址是否为违规站点。相比传统哈希表,它具有更低的内存占用和更快的查询速度,支持实时拦截、动态更新和资源压缩,有效提升系统性能并降低成本。
78 0
|
4月前
|
存储 安全 Java
Java 集合面试题从数据结构到 HashMap 源码剖析详解及长尾考点梳理
本文深入解析Java集合框架,涵盖基础概念、常见集合类型及HashMap的底层数据结构与源码实现。从Collection、Map到Iterator接口,逐一剖析其特性与应用场景。重点解读HashMap在JDK1.7与1.8中的数据结构演变,包括数组+链表+红黑树优化,以及put方法和扩容机制的实现细节。结合订单管理与用户权限管理等实际案例,展示集合框架的应用价值,助你全面掌握相关知识,轻松应对面试与开发需求。
201 3
232.用栈实现队列,225. 用队列实现栈
在232题中,通过两个栈(`stIn`和`stOut`)模拟队列的先入先出(FIFO)行为。`push`操作将元素压入`stIn`,`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列(`que`)模拟栈的后入先出(LIFO)特性。通过多次调整队列头部元素的位置,确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素,`empty`判断队列是否为空。 两题均仅使用基础数据结构操作,展示了栈与队列之间的转换逻辑。
|
6月前
|
存储 机器学习/深度学习 监控
如何监控员工的电脑——基于滑动时间窗口的Java事件聚合算法实现探析​
在企业管理场景中,如何监控员工的电脑操作行为是一个涉及效率与合规性的重要课题。传统方法依赖日志采集或屏幕截图,但数据量庞大且实时性不足。本文提出一种基于滑动时间窗口的事件聚合算法,通过Java语言实现高效、低资源占用的监控逻辑,为如何监控员工的电脑提供一种轻量化解决方案。
138 3

热门文章

最新文章