【数据结构(六)】队列

❣博主主页: 33的博客❣
▶️文章专栏分类:数据结构◀️
🚚我的代码仓库: 33的代码仓库🚚
🫵🫵🫵关注我带你学更多数据结构知识

在这里插入图片描述

目录

  • 1.前言
  • 2.概念
  • 3.队列的使用
  • 4.循环队列
  • 5.双端队列
  • 6.经典习题
    • 6.1队列实现栈
    • 6.2栈实现队列
  • 7.总结

1.前言

同学们排队等过车吧,最先去排队的人就是第一个出队上车的人。这就是日常生活中的队列。在数据结构中,队列也是这样的,最先进队的人最先出队,那我们就通过这篇文章来了解队列的详细知识点吧。

2.概念

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾(Tail/Rear) 出队列:进行删除操作的一端称为队头(Head/Front)
在这里插入图片描述


3.队列的使用

在Java中,Queue是个接口,底层是通过链表实现的。
在这里插入图片描述
注意
Queue是个接口,在实例化时必须实例化LinkedList的对象,因为LinkedList实现了Queue接口。

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());
    }
 }

4.循环队列

实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列通常使用数组实现
在这里插入图片描述
设计循环队列:
在这里插入图片描述
设计思路

1.首先要创建一个数组,我们再定义两个参数来确定环形数组的下个元素存放的下标end和第一个元素下标first。
2.当添加元素时,直接添加到end位置,end+1,但如果如上图,走到7的位置,那么end能直接+1吗?肯定是不行的,那么我们就可以把下一个下标定义为(end+1)%queue.length
3.那么我们该如何判满和判空呢?我们通常认为如果end下标等于first下标就认为空,如果end是下一个元素的下标等于first元素下标,那么就认为队列满,这样判断我们就会浪费一个空间来,所以设置数组大小的时候为K+1

public class MyCircularQueue {
    int[] queue;
    int first=0;
    int end=0;
    MyCircularQueue(int k){
        queue=new int[k+1];
    }
    public int Front(){
        if(isEmpty()){
            return -1;
        }
        return queue[first];
    }
    public int Rear(){
        if (isEmpty()) {
            return -1;
        }
        if (end==0){
            return queue[queue.length-1];
        }else {
            return queue[end-1];
        }
    }
    public Boolean enQueue( int value){
        if(isFull()){
            return false;
        }
        queue[end]=value;
        end=(end+1)%queue.length;
        return true;
    }
    public Boolean deQueue(){
        if(isEmpty()){
            return false;
        }
        first=(first+1)%queue.length;
        return true;
    }
    public Boolean isEmpty(){
        if(first==end){
            return true;
        }else {return false;}
    }
    public Boolean isFull(){
        if((end+1)%queue.length==first){
            return true;
        } else {
            return false;
        }
    }
}

5.双端队列

***双端队列(deque)***是指允许两端都可以进行入队和出队操作的队列,deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队,也可以从队尾出队和入队。
Deque是一个接口,使用时必须创建LinkedList或者ArrayList的对象。
在这里插入图片描述
在实际工程中,使用Deque接口是比较多的,栈和队列均可以使用该接口。

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

6.经典习题

6.1队列实现栈

使用两个队列实现一个后入先出(LIFO)的栈:OJ链接
解题思路

插入元素的时候,哪一个队列不为空就插入哪一个队列
删除元素的时候,先把size-1个元素移到另外一个队列,再删除最会一个元素
易错点,不能定义stack.size()来表示从一个队列进入另一个队列的元素,因为size是一直在变的。

public class MyStack {
    public Queue<Integer> sq1;
    public Queue<Integer> sq2;
    public int size=0;
        public MyStack() {
            sq1=new LinkedList<>();
            sq2=new LinkedList<>();;
        }

        public void push(int x) {
            if(!sq1.isEmpty()){
                sq1.offer(x);
            }
            if(!sq2.isEmpty()){
                sq2.offer(x);
            }
            if(sq1.isEmpty()&&sq2.isEmpty()){
                sq1.offer(x);
            }
            size++;
        }

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

        return sq2.poll();
        }

        public int top() {
            int x=-1;
            if(!sq1.isEmpty()){
                for (int i=0;i<size;i++){
                    x= sq1.poll();
                    sq2.offer(x);
                }

            }
            else if(!sq2.isEmpty()){
                for (int i=0;i<size;i++){
                     x= sq2.poll();
                    sq1.offer(x);
                }
            }
            return x;
        }
        public boolean empty() {
          return sq1.isEmpty()&&sq2.isEmpty();
        }
    }

6.2栈实现队列

请你仅使用两个栈实现先入先出队列:OJ链接
解题思路

定义两个栈s1,和s2,每次入队列存入s1中,每次出队列存入s2中。
当要出队列时,就把s1的元素依次出队,进入s2当中,s2再出队列
易错点,不能定义stack.size()来表示从s1进入s2的元素,因为s1的size是一直在变的。

class MyQueue {
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    public MyQueue() {
        stack1=new Stack<>();
        stack2=new Stack<>();
    }
    public void push(int x) {
        stack1.push(x);
    }
    public int pop() {
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        } 
        return stack2.pop();
    }
    public int peek() {
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        } 
        return stack2.peek();
    }
    public boolean empty() {
    return stack2.isEmpty()&&stack1.isEmpty(); 
    }
}

7.总结

本篇文章主要介绍了队列的使用,循环队列,双端队列,以及如何用队列实现栈,用栈实现队列。

下期预告:二叉树

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

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

相关文章

【学习笔记十】EWM自动产品包装配置

一、确定包装物料建议的程序 1.定义内向交货处理的凭证类型 2.确定包装物料建议的程序确定原理 使用可以确定包装材料建议的过程来指定业务代码。系统使用这些业务代码查找包装规格。包装期间&#xff0c;系统可建议包装材料。如果系统确定包装规格并建议包装材料&#xff0c;…

Maven创建项目

目录 1.创建项目 2.从Maven Repository: Search/Browse/Explore (mvnrepository.com)链接&#xff0c;下载API 3.1.0 3.在main文件内创建webapp文件夹&#xff0c;再webapp文件夹内创建WEB-INF文件夹&#xff0c;在WEB-INF文件夹内创建web.xml 4.网络编程 5.打包 6.部署 …

Python学习笔记16 - 函数

函数的创建和调用 函数调用的参数传递 函数的返回值 函数的参数定义 变量的作用域 递归函数 斐波那契数列 总结

网络编程套接字(二)之UDP服务器简单实现

目录 一、服务端UdpServer 1、udp_server.hpp 1、服务器的初始化 2、服务器的运行 2、udp_server.cc 二、客户端UdpClient udp_client.cc 三、完整代码 一、服务端UdpServer 1、udp_server.hpp 首先&#xff0c;我们在该文件中&#xff0c;将服务器封装成一个类&#…

网络抓包工具使用

一、下载安装 &#xff08;1&#xff09; linux&#xff1a; ① 使用 yum install tcpdump -y 安装 **tcpdump**工具 ② 编译安装 yum -y install gcc-c yum -y install flex yum -y install bison官网下载tcpdump和libpcap 官网地址:https://www.tcpdump.org/index.html#lat…

网红天水海英麻辣烫改名:还是商标的问题!

近日火爆网络的天水海英麻辣烫改名&#xff0c;改成“哈海英麻辣烫”&#xff0c;并打了TM&#xff0c;表示此商标名称商标局已经受理并下发通知书&#xff0c;普推知产老杨检索分析&#xff0c;改名的主要原因还是商标。 对于餐饮店和麻辣烫核心类别就在43类别及30类方便食品&…

表格单列相同字段值合并

用specName(el.specName row.specName)和id的区别(el.id row.id)&#xff0c;使用id的时候id是唯一值&#xff0c;判断的时候不会出现重复情况&#xff0c;使用specName的时候&#xff0c;如果有重复的值&#xff0c;会出现合并错位的情况。 解决方案&#xff1a;先按照specT…

【树哈希】CF1182D Complete Mirror

CF1182D - Complete Mirror Description 给定一个 n n n 个点的无根树&#xff0c;求一个树根 r o o t root root,使得对于任意两个节点 v 1 , v 2 v_1,v_2 v1​,v2​&#xff0c;若满足 d i s t ( v 1 , r o o t ) d i s t ( v 2 , r o o t ) dist(v_1,root)dist(v_2,ro…

CUDA编程---全局内存

CUDA内存模型概述 内存的访问和管理是所有编程语言的重要部分。在现代加速器中&#xff0c;内存管理对高性能计算有着很大的影响。因为多数工作负载被加载和存储数据的速度所限制&#xff0c;所以有大量低延迟、高带宽的内存对性能是十分有利的。 然而&#xff0c;大容量、高性…

第十五届蓝桥杯省赛C/C++大学B组真题及赛后总结

目录 个人总结 C/C 组真题 握手问题 小球反弹 好数 R 格式 宝石组合 数字接龙 爬山 拔河 ​编辑 再总结及后续规划 个人总结 第一次参加蓝桥杯&#xff0c;大二&#xff0c;以前都在在学技术&#xff0c;没有系统的学过算法。所以&#xff0c;还是花了挺多时间去备…

【8086汇编】汇编语言基础入门

文章目录 一、汇编简介1. 汇编语言的组成2. CPU、寄存器、内存3. CPU对存储器的读写4. 拓展5. 检测6. 解析 二、寄存器1. mov、add命令2. 物理地址3. CS:IP 装段地址和偏移地址3.1 如何改变CS:IP的值 4. 数据段DS:[address]4.1 前置知识&#xff1a;字与字节4.2 DS:[address] 5…

串口RS485

1.原理 全双工&#xff1a;在同一时刻可以同时进行数据的接收和数据的发送&#xff0c;两者互不影响 半双工&#xff1a;在同一时刻只能进行数据的接收或者数据的发送&#xff0c;两者不能同时进行 差分信号幅值相同&#xff0c;相位相反&#xff0c;有更强的抗干扰能力。 干…

【C语言】N子棋小游戏♔

目录 前言 一、何为N子棋游戏&#xff1f; 二、游戏思路 三、游戏实现 3.1 模块化 3.2 游戏棋盘 3.3 下棋操作 3.3.1 玩家下棋 3.3.2 电脑下棋 3.4 判断输赢 总结 前言 三子棋小游戏相信大家都玩过吧&#xff0c;类似的5子琪等等&#xff0c;这篇文章将带着大家从0到…

【leetcode面试经典150题】28.盛最多水的容器(C++)

【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主&#xff0c;题解使用C语言。&#xff08;若有使用其他语言的同学也可了解题解思路&#xff0c;本质上语法内容一致&…

分享一些有趣的 Linux 命令

1、sl 会显示一辆火车穿过你的终端屏幕 2、cmatrix 在终端中显示类似于《黑客帝国》电影中的绿色数字雨效果 3、fortune 显示一个随机的名人名言或者笑话 4、cowsay 让一头牛说出你输入的话 5、toilet 在终端中将输入的文本以艺术字体的形式呈现 6、figlet 类似于 toile…

回溯算法初识

文章目录 回溯算法初识什么是回溯算法回溯算法的步骤回溯算模版例题 回溯算法初识 什么是回溯算法 ​ 回溯算法是一种通过不断尝试可能的解决方案来解决问题的算法。它通常用于解决组合优化问题&#xff0c;如排列组合问题、子集和问题等。该算法通过尝试所有可能的候选解&am…

【热门话题】常见分类算法解析

&#x1f308;个人主页: 鑫宝Code &#x1f525;热门专栏: 闲话杂谈&#xff5c; 炫酷HTML | JavaScript基础 ​&#x1f4ab;个人格言: "如无必要&#xff0c;勿增实体" 文章目录 常见分类算法解析1. 逻辑回归&#xff08;Logistic Regression&#xff09;2. 朴…

【设计模式】聊聊观察者设计模式原理及应用

原理 观察者模式属于行为模式&#xff0c;行为模式主要解决类和对象之间交互问题。 含义&#xff1a;在对象之间定义一个一对多的依赖&#xff0c;当一个对象状态改变时&#xff0c;所有依赖的对象会自动通知。 被依赖的对象被观察者(Observable) &#xff0c;依赖的对象观察…

移动Web学习06-移动端适配Less预处理器项目案例

项目目标&#xff1a;实现在不同宽度设备中等比缩放的网页效果 Less代码 import ./base; import ./normalize;// 变量: 存储37.5 rootSize: 37.5rem; *{margin: 0;padding: 0; } body {background-color: #F0F0F0; }// 主体内容 .main {// padding-bottom: (50 / 37.5rem);pa…

缺失msvcr110.dll要怎么处理?快捷的修复msvcr110.dll方法

当你在使用电脑进行工作或娱乐时&#xff0c;可能会突然遇到一个错误提示&#xff1a;“程序无法启动&#xff0c;因为电脑中缺失msvcr110.dll”。这样的情况不仅会打断你的活动&#xff0c;还可能带来一定程度的不便。面对这个在Windows操作系统中相对常见的问题&#xff0c;其…