Java数据结构队列

队列(Queue)
 

概念

队列的使用

注意:Queue是个接口,在实例化时必须实例化LinkedList的对象,因为LinkedList实现了Queue接口。

import java.util.LinkedList;
import java.util.Queue;

public class Test {
    public static void main(String[] args) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        q.offer(2);
        q.offer(3);
        q.offer(4);
        q.offer(5); // 从队尾入队列
        System.out.println(q.size());
        System.out.println(q.peek()); // 获取队头元素
        q.poll();
        System.out.println(q.poll()); // 从队头出队列,并将删除的元素返回
        if (q.isEmpty()) {
            System.out.println("队列空");
        } else {
            System.out.println(q.size());
        }
    }
}

队列的模拟实现

队列中既然可以存储元素,那底层肯定要有能够保存元素的空间,通过前面线性表的学习了解到常见的空间类型有两种:顺序结构(数组) 和 链式结构

队列的实现使用顺序结构还是链式结构好?

public class MyQueue {
    static class ListNode {
        public int val;
        public ListNode prev;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head;
    public ListNode last;

    //尾插
    public void offer(int val) {
        ListNode node = new ListNode(val);
        if (head == null) {
            head = last = node;
        } else {
            last.next = node;
            node.prev = last;
            last = last.next;
        }
    }

    //头删
    public int poll() {
        if (head == null) {
            return -1;
        }
        int ret = head.val;
        if (head.next == null) {
            head = null;
            last = null;
        } else {
            head = head.next;
            head.prev = null;
        }
        return ret;
    }

    public int peek() {
        if (head == null) {
            return -1;
        }
        int ret = head.val;
        return ret;
    }
}

循环队列

实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列通常使用数组实现。

如何区分空与满

1. 通过添加 size 属性记录

空:size=0    满:us=数组长度

2. 保留一个位置(浪费一个空间)(下面的设计循环队列用的就是此方法)

相遇就是空 满:last的下一个是first
3. 使用标记

Boolean flag

数组下标循环的小技巧

1. 下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length

 

2. 下标最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length

设计循环队列

class MyCircularQueue {

    public int[] elem;
    public int first;
    public int last;

    public MyCircularQueue(int k) {
        elem = new int[k];
    }

    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }
        elem[last] = value;
        last = (last + 1) % elem.length;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }
        first = (first + 1) % elem.length;
        return true;
    }

    //得到队头元素
    public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return elem[first];
    }

    //得到队尾元素
    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        int index = (last == 0) ? elem.length - 1 : last - 1;
        return elem[index];
    }

    public boolean isEmpty() {
        return first == last;
    }

    public boolean isFull() {
        return (last + 1) % elem.length == first;
    }
}

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue obj = new MyCircularQueue(k);
 * boolean param_1 = obj.enQueue(value);
 * boolean param_2 = obj.deQueue();
 * int param_3 = obj.Front();
 * int param_4 = obj.Rear();
 * boolean param_5 = obj.isEmpty();
 * boolean param_6 = obj.isFull();
 */

将elem = new int[k];改为elem = new int[k+1];即可

双端队列

双端队列(deque)是指允许两端都可以进行入队和出队操作的队列,deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队,也可以从队尾出队和入队

Deque是一个接口,使用时必须创建LinkedList的对象。

在实际工程中,使用Deque接口是比较多的,栈和队列均可以使用该接口

Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现

面试题

1.用队列实现栈

import java.util.LinkedList;
import java.util.Queue;

class MyStack {

    public Queue<Integer> queue1;
    public Queue<Integer> queue2;

    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    public void push(int x) {
        if (empty()) {
            queue1.offer(x);
            return;
        }
        if (!queue1.isEmpty()) {
            queue1.offer(x);
        } else {
            queue2.offer(x);
        }
    }

    public int pop() {
        if (empty()) {
            return -1;
        }
        if (!queue1.isEmpty()) {
            int size = queue1.size();
            for (int i = 0; i < size - 1; i++) {
                queue2.offer(queue1.poll());
            }
            return queue1.poll();
        } else {
            int size = queue2.size();
            for (int i = 0; i < size - 1; i++) {
                queue1.offer(queue2.poll());
            }
            return queue2.poll();
        }
    }

    public int top() {
        if (empty()) {
            return -1;
        }
        if (!queue1.isEmpty()) {
            int size = queue1.size();
            int ret = -1;
            for (int i = 0; i < size; i++) {
                ret = queue1.poll();
                queue2.offer(ret);
            }
            return ret;
        } else {
            int size = queue2.size();
            int ret = -1;
            for (int i = 0; i < size; i++) {
                ret = queue2.poll();
                queue1.offer(ret);
            }
            return ret;
        }
    }

    public boolean empty() {
        return queue1.isEmpty() && queue2.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

2.用栈实现队列

import java.util.Stack;

class MyQueue {

    public Stack<Integer> s1;
    public Stack<Integer> s2;

    public MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }

    public void push(int x) {
        s1.push(x);
    }

    public int pop() {
        // 两个栈都是空 意味着 队列为空
        if (empty()) {
            return -1;
        }
        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }

    public int peek() {
        if (empty()) {
            return -1;
        }
        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.pop());
            }
        }
        return s2.peek();
    }

    // 判断模拟实现的队列是否为空
    public boolean empty() {
        return s1.empty() && s2.empty();

    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/521327.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

使用GPT需要注意的事项

GPT出来之后&#xff0c;基本就告别浏览器搜索问题答案了。将问题原封不动的copy给GPT基本可以得到解答。 但是这个也有弊端&#xff0c;那就是太依赖GPT了。 1&#xff0c;使用GPT需要更强的专业知识&#xff1a;除了能问对问题&#xff0c;还要具备识别GPT&q…

VPDN(L2TP、PPTP)

1、虚拟专用拨号网络 远程接入VPN&#xff0c;客户端可以是PC机 技术&#xff1a;L2TP、PPTP 术语&#xff1a;LAC&#xff1a;L2TP的访问集中器 --- 提供用户的接入 LNS&#xff1a;L2TP的网络服务器 --- 提供L2TP服务的服务器 2、技术 1&#xff09;PPTP 点对点隧道…

深入理解Java匿名内部类(day21)

在Java编程中&#xff0c;匿名内部类是一种非常有用的特性&#xff0c;它允许我们定义和实例化一个类的子类或实现一个接口&#xff0c;而无需给出子类的名称。这种特性使得代码更加简洁、紧凑&#xff0c;尤其适用于一些只使用一次的临时对象。本文将深入探讨Java匿名内部类的…

租用阿里云的服务器多少钱?30元、61元、99元、165元、199元

租个阿里云的服务器多少钱&#xff1f;很便宜&#xff0c;云服务器2核2G3M固定带宽99元一年、2核4G服务器30元3个月、199元一年&#xff0c;轻量应用服务器2核2G3M配置61元一年、2核4G4M带宽165元一年&#xff0c;可以在阿里云CLUB中心查看 aliyun.club 当前最新的优惠券和活动…

基于Socket简单的TCP网络程序

⭐小白苦学IT的博客主页 ⭐初学者必看&#xff1a;Linux操作系统入门 ⭐代码仓库&#xff1a;Linux代码仓库 ❤关注我一起讨论和学习Linux系统 TCP单例模式的多线程版本的英汉互译服务器 我们先来认识一下与udp服务器实现的不同的接口&#xff1a; TCP服务器端 socket()&…

基于单片机电子密码锁系统设计

**单片机设计介绍&#xff0c;基于单片机电子密码锁系统设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机电子密码锁系统设计概要主要包括以下几个方面&#xff1a; 一、系统概述 基于单片机电子密码锁系统是一个…

打造你的专属云开发环境:支持任意 IDE,任意云服务 | 开源日报 No.215

loft-sh/devpod Stars: 6.9k License: MPL-2.0 devpod 是一个开源的、仅限客户端的、不受限制的工具&#xff0c;可以与任何集成开发环境&#xff08;IDE&#xff09;一起使用&#xff0c;并允许您在任何云端、Kubernetes 或本地 Docker 上进行开发。 使用 devcontainer.json…

贪心算法|45.跳跃游戏II

力扣题目链接 class Solution { public:int jump(vector<int>& nums) {if (nums.size() 1) return 0;int curDistance 0; // 当前覆盖最远距离下标int ans 0; // 记录走的最大步数int nextDistance 0; // 下一步覆盖最远距离下标for (int i 0;…

qt-C++笔记之QLabel加载图片

qt-C笔记之QLabel加载图片 —— 2024-04-06 夜 code review! 文章目录 qt-C笔记之QLabel加载图片0.文件结构1.方法一&#xff1a;把图片放在项目路径下&#xff0c;在 .pro 文件中使用 DISTFILES添加图片文件1.1.运行1.2.qt_test.pro1.3.main.cpp 2.方法二&#xff1a;不在 .pr…

深入浅出 -- 系统架构之分布式集群的分类

一、单点故障问题 集群&#xff0c;相信诸位对这个概念并不陌生&#xff0c;集群已成为现时代中&#xff0c;保证服务高可用不可或缺的一种手段。 回想起初集中式部署的单体应用&#xff0c;因为只有一个节点&#xff0c;因此当该节点出现任意类型的故障&#xff08;网络、硬件…

go | 上传文件分析 | http协议分析 | 使用openssl 实现 https 协议 server.key、server.pem

是这样的&#xff0c;现在分析抓包数据 test.go package mainimport ("fmt""log""github.com/gin-gonic/gin" )func main() {r : gin.Default()// Upload single filer.MaxMultipartMemory 8 << 20r.POST("/upload", func(c *g…

【单片机】心率传感器,串口发送,MAX30102心率传感器模块

数值还是稳定的&#xff0c;但太贵了&#xff0c;stm32单片机的话&#xff0c;直接用这篇博客&#xff08;https://qq742971636.blog.csdn.net/article/details/137359381&#xff09;的代码&#xff0c;一样稳定。 解析这个模块的数据 char rev_max30102_bufferdata[30]; cha…

Flutter学习12 - SharedPreferences

1、shared_preferences 插件 类似于 Android 中的 SharedPreferences&#xff0c;键值对的形式进行本地存储 1.1、引入插件 在 pubspec.yaml 中引入 dependencies:shared_preferences: ^2.1.0在需要用到的文件中引入 import package:shared_preferences/shared_preference…

安全的通信协议HTTPS被攻击改采用什么防护方案

随着互联网的发展&#xff0c;保护用户在网上交换的敏感信息的安全性变得至关重要。HTTPS&#xff08;Hypertext Transfer Protocol Secure&#xff09;作为一种安全的通信协议&#xff0c;通过加密数据传输&#xff0c;保护用户的隐私和数据安全。然而&#xff0c;尽管HTTPS提…

Ubuntu部署LangChain-Chatchat

个人博客&#xff1a;https://blog.lukeewin.top 更多内容欢迎访问我的博客。 一、环境 OS: Ubuntu 20.04 PyTorch: 2.0.0 Python: 3.8 CUDA: 11.8 GPU: RTX 4090 24GB CPU: 12 vCPU Intel(R) Xeon(R) Platinum 8352V CPU 2.10GHz RAM: 90GB 硬盘: 180GB LLM: Chatglm3-6b E…

ubuntu20.04.6安装sshd服务,并连接到远程服务器

文章目录 sshd 是 OpenSSH 服务器的守护进程OpenSSH下载在 Ubuntu 上&#xff0c;可以按照以下步骤来管理 sshd 服务 防火墙开启22端口使用Mobaxterm链接服务器 sshd 是 OpenSSH 服务器的守护进程 它负责提供远程登录和安全的 shell 服务。通过启动 sshd 服务&#xff0c;可以…

小米汽车su7全色系展示源码

源码简介 小米汽车全色系展示源码&#xff0c;小米汽车su7全色系展示源码 安装教程 纯HTML&#xff0c;直接将压缩包上传网站目录解压即可 首页截图 源码下载 小米汽车su7全色系展示源码-小8源码屋源码简介 小米汽车全色系展示源码&#xff0c;小米汽车su7全色系展示源码 …

015——步进电机模块驱动开发(基于I.MX6uLL、MX-1502和28BYJ-48)

目录 一、电机驱动模块介绍 1.1 特性 1.2 应用范围 1.3 概述 1.4 电气属性 1.5 经典应用线路 二、电机介绍&#xff08;本节内容来自韦东山老师课程资料&#xff09; 三、 代码编写思路 四、 驱动程序 五、应用程序 一、电机驱动模块介绍 1.1 特性  低待机电流 (…

lua学习笔记6(经典问题输出99乘法表)

print("************for循环的99乘法表*************") for i 1, 9 dolocal line "" -- 创建一个局部变量来累积每行的输出--local 是一个关键字&#xff0c;用于声明一个局部变量。for j 1, i doline line .. j .. "*" .. i .. ""…

基于YOLOv8的铁路工人安全作业检测系统

&#x1f4a1;&#x1f4a1;&#x1f4a1;本文摘要&#xff1a;基于YOLOv8的铁路工人安全作业检测系统&#xff0c;属于小目标检测范畴&#xff0c;并阐述了整个数据制作和训练可视化过程&#xff0c; 博主简介 AI小怪兽&#xff0c;YOLO骨灰级玩家&#xff0c;1&#xff0…