【数据结构与算法】7、队列（Queue）的实现【用栈实现队列】

目录

  • 一、队列介绍
  • 二、使用 LinkedList 实现队列
  • 三、LeetCode：用【栈】实现队列
    • (1) 老师讲之前我自己的实现（Correct）
    • (2) 实现思路
    • (3) 代码实现
  • 四、jdk 的 Queue
  • 五、双端队列（Deque）
  • 六、循环队列
    • (1) 分析
    • (2) 入队
    • (3) 出队
    • (4) 动态扩容
      • ① 我自己的垃圾实现
      • ② 老师的代码实现
    • (5) 索引映射封装
    • (6) 循环队列完整代码
  • 七、循环双端队列

一、队列介绍

☘️ 队列（Queue）是一种特殊的线性表，只能在头尾两端进行操作
🎁 队尾（rear）：只能从队尾添加元素，一般叫做 enQueue，入队
🎁 队头（front）：只能从队头移除元素，一般叫做 deQueue，出队
🎁 先进先出的原则，First In First Out，FIFO

在这里插入图片描述

在这里插入图片描述

二、使用 LinkedList 实现队列

在这里插入图片描述

/**
 * 利用动态数组实现栈
 */
public class Queue<E> {
    // 通过【组合】的方式使用 LinkedList
    private final List<E> list = new LinkedList<>();

    /**
     * 获取队列中的元素个数
     */
    public int size() {
        return list.size();
    }

    /**
     * 判断队列中是否一个元素都没有（判断是否是一个空队列）
     */
    public boolean isEmpty() {
        return list.isEmpty();
    }

    /**
     * 往队列中添加元素（入队）
     */
    public void enQueue(E element) {
        list.add(0, element);
    }

    /**
     * 取出队首元素, 并删之（出队）
     *
     * @return 队首元素
     */
    public E deQueue() {
        return list.remove(size() - 1);
    }

    /**
     * 获取队列的头元素
     */
    public E front() {
        return list.get(size() - 1);
    }

    /**
     * 清空队列
     */
    public void clear() {
        list.clear();
    }

}

☘️ 队列内部的实现可以直接利用动态数组和链表
☘️ 优先使用双向链表。① 队列主要是往头尾两端操作元素；② 双向链表由于有头指针 first 和尾指针 last 的存在，在头尾进行元素操作都是 O(1) 的复杂度

三、LeetCode：用【栈】实现队列

https://leetcode.cn/problems/implement-queue-using-stacks/

(1) 老师讲之前我自己的实现（Correct）

🍃 代码是正确的，通过了 LeetCode 的检查

public class MyQueue {
    private Stack<Integer> stackLeft = new Stack<>(); // 左栈
    private Stack<Integer> stackRight = new Stack<>(); // 右栈

    /**
     * 构造方法
     */
    public MyQueue() {

    }

    /**
     * 入队
     */
    public void push(int x) {
        stackLeft.push(x);
    }

    /**
     * 出队
     */
    public int pop() {
        // 先把【左栈】的元素全部出栈并入栈到【右栈】中
        while (!stackLeft.isEmpty()) {
            stackRight.push(stackLeft.pop());
        }

        Integer elem = stackRight.pop();

        // 把【右栈】元素放入【左栈】
        while (!stackRight.isEmpty()) {
            stackLeft.push(stackRight.pop());
        }

        return elem;
    }

    /**
     * 返回队首元素
     */
    public int peek() {
        // 先把【左栈】的元素全部出栈并入栈到【右栈】中
        while (!stackLeft.isEmpty()) {
            stackRight.push(stackLeft.pop());
        }

        Integer elem = stackRight.peek();

        // 把【右栈】元素放入【左栈】
        while (!stackRight.isEmpty()) {
            stackLeft.push(stackRight.pop());
        }

        return elem;
    }

    public boolean empty() {
        return stackLeft.isEmpty();
    }

}

/**
 * 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();
 */

(2) 实现思路

📖 准备 2 个栈：inStack、outStack
📘入队时，把元素 push 到 inStack 中
📘出队时
✏️如果 outStack 为空，① 将 inStack 所有元素逐一弹出，push 到 outStack；② outStack 弹出栈顶元素
✏️如果 outStack 不为空， outStack 弹出栈顶元素

在这里插入图片描述

(3) 代码实现

public class MyQueue {
    // 入队时, 往 inStack 插入元素
    private Stack<Integer> inStack = new Stack<>();
    private Stack<Integer> outStack = new Stack<>();

    /**
     * 构造方法
     */
    public MyQueue() {

    }

    /**
     * 入队（只要是入队, 就往 inStack 插入元素）
     */
    public void push(int x) {
        inStack.push(x);
    }

    /**
     * 出队
     */
    public int pop() {
        if (outStack.isEmpty()) { // 如果 outStack 为空
            // 将 inStack 所有元素逐一弹出, push 到 outStack 中
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }

        return outStack.pop();
    }

    /**
     * 返回队首元素
     */
    public int peek() {
        if (outStack.isEmpty()) { // 如果 outStack 为空
            // 将 inStack 所有元素逐一弹出, push 到 outStack 中
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }

        return outStack.peek();
    }

    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }

}

/**
 * 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();
 */

四、jdk 的 Queue

☘️ offer()：入队
☘️ poll()：出队
☘️ peek()：返回队头元素

☘️ jdk 的 Queue 底层也是 LinkedList

五、双端队列（Deque）

💴 双端队列是能在头尾两端添加、删除的队列
💴 英文 deque 是 double ended queue 的简称
在这里插入图片描述

☆ 队尾是链表的末尾
☆ 队头是链表的第一个元素

/**
 * 双端队列
 */
public class Deque<E> {
    private final List<E> linkedList;

    public Deque() {
        this.linkedList = new LinkedList<>();
    }

    public int size() {
        return linkedList.size();
    }

    public boolean isEmpty() {
        return linkedList.isEmpty();
    }

    public void clear() {
        linkedList.clear();
    }

    /**
     * 从队尾入队
     */
    public void enQueueRear(E element) {
        linkedList.add(element);
    }

    /**
     * 从队头入队
     */
    public void enQueueFront(E element) {
        linkedList.add(0, element);
    }

    /**
     * 从队头出队
     */
    public E deQueueFront() {
        return linkedList.remove(0);
    }

    /**
     * 从队尾出队
     */
    public E deQueueRear() {
        return linkedList.remove(size() - 1);
    }

    /**
     * 获取队列的头元素
     */
    public E front() {
        return linkedList.get(0);
    }

    /**
     * 获取队列的【尾】元素
     */
    public E rear() {
        return linkedList.get(size() - 1);
    }

}

六、循环队列

(1) 分析

在这里插入图片描述

☘️ 队列底层也可以使用动态数组实现，并且各项接口也可以优化到 O(1) 的时间复杂度
☘️ 用数组实现并且优化之后的队列也叫做：循环队列（Circle Queue）

☘️ 循环双端队列：可以进行两端添加、删除操作的循环队列

(2) 入队

在这里插入图片描述

在这里插入图片描述

  /**
   * 往队列中添加元素（入队）
   */
  public void enQueue(E element) {
      elements[(front + size) % elements.length] = element;
      size++;
  }

在这里插入图片描述

(3) 出队

在这里插入图片描述

  /**
   * 取出队首元素, 并删之（出队）
   *
   * @return 队首元素
   */
  public E deQueue() {
      E frontElem = elements[front];
      elements[front] = null;
      front = (front + 1) % elements.length;
      size--;
      return frontElem;
  }

(4) 动态扩容

在这里插入图片描述

① 我自己的垃圾实现

🍀 也是能够满足要求的，但代码效率不行 😪

    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        // 如果所需容量足够, 则不扩容
        if (oldCapacity >= capacity) return;

        // 申请全新的数组空间（新容量是旧容量的 1.5 倍）
        capacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[capacity];

        // 把旧数组中的数据复制到新数组中
        int index = 0;
        int flagSize = 0;
        E[] oldElements = this.elements;
        while (!this.isEmpty()) {
            E e = this.deQueue();
            flagSize++;
            newElements[index] = e;
            index++;
        }

        // elements 指针指向新数组
        this.elements = newElements;
        // 队头 front 指向 0
        front = 0;
        size = flagSize;

        System.out.println(oldCapacity + "扩容为" + capacity);
    }

② 老师的代码实现

 private void ensureCapacity(int capacity) {
     int oldCapacity = elements.length;
     // 如果所需容量足够, 则不扩容
     if (oldCapacity >= capacity) return;

     // 申请全新的数组空间（新容量是旧容量的 1.5 倍）
     capacity = oldCapacity + (oldCapacity >> 1);
     E[] newElements = (E[]) new Object[capacity];

     for (int i = 0; i < size; i++) {
         newElements[i] = elements[(i + front) % elements.length];
     }

     // elements 指针指向新数组
     this.elements = newElements;
     // 队头 front 指向 0
     front = 0;

     System.out.println(oldCapacity + "扩容为" + capacity);
 }

(5) 索引映射封装

  public int realIndex(int index) {
      return (front + index) % elements.length;
  }

(6) 循环队列完整代码

/**
 * 循环队列
 */
@SuppressWarnings("all")
public class CircleQueue<E> {

    private int front; // 记录着队头元素的下标
    private int size;
    private E[] elements;

    public static final int DEFAULT_CAPACITY = 10;

    public CircleQueue(int capacity) {
        capacity = (capacity > DEFAULT_CAPACITY) ? capacity : DEFAULT_CAPACITY;
        elements = (E[]) new Object[capacity];
    }

    public CircleQueue() {
        this(DEFAULT_CAPACITY);
    }

    /**
     * 获取队列中的元素个数
     */
    public int size() {
        return size;
    }

    /**
     * 判断队列中是否一个元素都没有（判断是否是一个空队列）
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 获取队列的头元素
     */
    public E front() {
        return elements[front];
    }

    /**
     * 往队列中添加元素（入队）
     */
    public void enQueue(E element) {
        // 扩容检测
        ensureCapacity(size + 1);

        elements[realIndex(size)] = element;
        size++;
    }

    /**
     * 我自己的垃圾实现
     */
//    private void ensureCapacity(int capacity) {
//        int oldCapacity = elements.length;
//        // 如果所需容量足够, 则不扩容
//        if (oldCapacity >= capacity) return;
//
//        // 申请全新的数组空间（新容量是旧容量的 1.5 倍）
//        capacity = oldCapacity + (oldCapacity >> 1);
//        E[] newElements = (E[]) new Object[capacity];
//
//        // 把旧数组中的数据复制到新数组中
//        int index = 0;
//        int flagSize = 0;
//        E[] oldElements = this.elements;
//        while (!this.isEmpty()) {
//            E e = this.deQueue();
//            flagSize++;
//            newElements[index] = e;
//            index++;
//        }
//
//        // elements 指针指向新数组
//        this.elements = newElements;
//        // 队头 front 指向 0
//        front = 0;
//        size = flagSize;
//
//        System.out.println(oldCapacity + "扩容为: " + capacity);
//    }
    private void ensureCapacity(int capacity) {
        int oldCapacity = elements.length;
        // 如果所需容量足够, 则不扩容
        if (oldCapacity >= capacity) return;

        // 申请全新的数组空间（新容量是旧容量的 1.5 倍）
        capacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[capacity];

        for (int i = 0; i < size; i++) {
            newElements[i] = elements[realIndex(i)];
        }

        // elements 指针指向新数组
        this.elements = newElements;
        // 队头 front 指向 0
        front = 0;

        System.out.println(oldCapacity + "扩容为" + capacity);
    }

    private void print(String s, E[] es) {
        System.out.println("s = " + s);
        for (E e : es) {
            System.out.println(e);
        }
        System.out.println("s = " + s);
    }


    /**
     * 取出队首元素, 并删之（出队）
     *
     * @return 队首元素
     */
    public E deQueue() {
        E frontElem = elements[front];
        elements[front] = null;
        front = realIndex(1);
        size--;
        return frontElem;
    }


    /**
     * 清空队列
     */
    public void clear() {
        for (E element : elements) {
            element = null;
        }

        size = 0;
        front = 0;
    }

    public int realIndex(int index) {
        return (front + index) % elements.length;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("{size=").append(size).
            append(", capacity=").append(elements.length).
            append(", [");

        for (int i = 0; i < elements.length; i++) {
            // 不是第 0 个元素就拼接【, 】
            if (i != 0) {
                sb.append(", ");
            }

            sb.append(elements[i]);
        }

        sb.append("]}");

        return sb.toString();
    }
}

七、循环双端队列

☘️ 用数组实现并且优化之后的队列也叫做：循环队列（Circle Queue）

🍀 循环双端队列不需要存在一个叫做 rear 的变量来存储队尾元素的下标
🍃 队尾元素的下标: front + size - 1

略…

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

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

相关文章

基于FPGA的RC滤波器设计实现

基于FPGA的RC滤波器设计实现

目录 简介&#xff1a; 传递函数 FPGA代码实现 总结 简介&#xff1a; RC滤波器的特性基本情况介绍 RC一阶低通滤波介绍&#xff1b;RC滤波器电路简单&#xff0c;抗干扰性强&#xff0c;有较好的低频性能&#xff0c;并且选用标准的阻容元件易得&#xff0c;所以在工程测…
阅读更多...
【JAVA】十分钟带你了解java的前世今生

【JAVA】十分钟带你了解java的前世今生

个人主页&#xff1a;【&#x1f60a;个人主页】 系列专栏&#xff1a;【初始JAVA】 文章目录 前言JAVA介绍诞生&#x1f52c;名字与图标&#x1f916;发展&#x1f6e9;️未来&#x1fa84; 前言 玩过我的世界的朋友想必对JAVA以及它的图标都很熟悉&#xff0c;在游戏开始画面…
阅读更多...
7.3 SpringBoot整合MyBatis分页插件github.pageHelper：实现图书列表API

7.3 SpringBoot整合MyBatis分页插件github.pageHelper：实现图书列表API

文章目录 前言一、自己实现分页第一步&#xff0c;count 查询 总记录数&#xff08;totalCount&#xff09;&#xff0c;计算总页数&#xff08;totalPages&#xff09;第二步&#xff0c;limit 查询 指定页数据 二、不考虑分页的查询图书列表MapperBookServiceImplBookListPar…
阅读更多...
FastDFS单机部署及SpringBoot整合

FastDFS单机部署及SpringBoot整合

前言 FastDFS是一个开源的高性能分布式文件系统。它的主要功能包括&#xff1a;文件存储、文件同步和文件访问&#xff08;文件上传和文件下载&#xff09;&#xff0c;可以解决高容量和负载平衡问题。FastDFS应满足其服务基于文件的网站的要求&#xff0c;如照片共享网站和视…
阅读更多...
Maynor的博客专家成长之路——暨2023年中复盘

Maynor的博客专家成长之路——暨2023年中复盘

文章目录 博客专家成长之路——暨2023年中复盘前言念念不忘的博客专家每天只做三件事敲代码写博客健健身 我的感悟 不足之处未来&#xff1a;和CSDN共同成长最后 博客专家成长之路——暨2023年中复盘 前言 ​ 2023年不知不觉已经过去了半年有余&#xff0c;也是时候作年中复盘…
阅读更多...
ChatGPT 是什么？

ChatGPT 是什么？

写在前面&#xff1a;这篇文章是今年1月份对chatgpt做调研学习时写的&#xff0c;都是从别处搬来的&#xff0c;纯扫盲的作用。本来一直以草稿的形势存在&#xff0c;但今天整理博客&#xff0c;顺便给发出来吧。 文章目录 1. ChatGPT简介1.1 ChatGPT 支持的场景举例 2 ChatGPT…
阅读更多...
计算机网络————应用层

计算机网络————应用层

文章目录 概述域名系统DNS域名结构域名服务器解析过程常见的DNS记录DNS报文格式基础结构部分问题部分资源记录(RR, Resource Record)部分 万维网WWWURLHTTPHTTP发展HTTP报文结构请求报文响应报文 cookie 内容分发网络CDN 概述 应用层的具体内容就是规定应用进程在通信时所遵循的…
阅读更多...
python数据分析之利用多种机器学习方法实现文本分类、情感预测

python数据分析之利用多种机器学习方法实现文本分类、情感预测

大家好&#xff0c;我是带我去滑雪&#xff01; 文本分类是一种机器学习和自然语言处理&#xff08;NLP&#xff09;任务&#xff0c;旨在将给定的文本数据分配到预定义的类别或标签中。其目标是为文本数据提供自动分类和标注&#xff0c;使得可以根据其内容或主题进行组织、排…
阅读更多...
【AI】PyTorch安装记录及Anaconda环境配置

【AI】PyTorch安装记录及Anaconda环境配置

【AI】PyTorch安装记录及Anaconda环境配置 说下本地环境&#xff0c;RTX4070 12GB GPU&#xff1b;618刚买&#xff0c;不能让他闲着&#xff0c;配置一下炼丹环境&#xff0c;开始为打工人工作。为了方便后续部署模型之间依赖不冲突&#xff0c;所以使用Anaconda管理Python环…
阅读更多...
网络环境TFTPNFS搭建

网络环境TFTPNFS搭建

文章目录 1. TFTP服务搭建2. NFS 环境搭建 1. TFTP服务搭建 1、Ubuntu上搭建TFTP服务器&#xff0c;需要安装tftp-hpa和tftpd-hpa&#xff0c;命令如下&#xff1a; sudo apt-get install tftp-hpa tftpd-hpa sudo apt-get install xinetd2、TFTP也需要一个文件夹来存放文件…
阅读更多...
Django DRF - 【Token】认证基本使用

Django DRF - 【Token】认证基本使用

一. 前言 Django Rest Framework Token是Django Rest Framework中的一个扩展&#xff0c;用于实现用户认证和授权。它为每个用户生成一个唯一的Token&#xff0c;并将其存储在数据库中。在用户进行API请求时&#xff0c;用户需要在请求的HTTP Header中包含Token&#xff0c;这…
阅读更多...
考场作弊行为自动抓拍告警算法 yolov7

考场作弊行为自动抓拍告警算法 yolov7

考场作弊行为自动抓拍告警系统通过yolov7python网络模型算法&#xff0c;考场作弊行为自动抓拍告警算法实时监测考场内所有考生的行为&#xff0c;对考生的行为进行自动抓拍&#xff0c;并分析判断是否存在作弊行为。YOLOv7 的发展方向与当前主流的实时目标检测器不同&#xff…
阅读更多...
关于Apache Dubbo反序列化漏洞（CVE-2023-23638）的预警提示与对应的Zookeeper版本

关于Apache Dubbo反序列化漏洞（CVE-2023-23638）的预警提示与对应的Zookeeper版本

公司在升级dubbo过程中因zookeeper版本不匹配&#xff0c;导致服务注册和调用出现异常 一、漏洞详情 Apache Dubbo是一款高性能、轻量级的开源Java服务框架。 Apache官方发布安全公告&#xff0c;修复了Apache Dubbo中的一个反序列化漏洞&#xff08;CVE-2023-23638&#xff…
阅读更多...
玩转C++调试之Python的GDB库增强

玩转C++调试之Python的GDB库增强

玩转C调试之Python的GDB库增强 0.导语 调试是软件开发过程中不可或缺的一环&#xff0c;而GDB&#xff08;GNU调试器&#xff09;作为一款功能强大的调试工具&#xff0c;在开发者中得到广泛应用。除了传统的命令行调试功能外&#xff0c;GDB还提供了Python的GDB库&#xff0c;…
阅读更多...
计算机网络——自顶向下方法（第一章学习记录）

计算机网络——自顶向下方法（第一章学习记录）

什么是Internet? 可以从两个不同的方面来理解Internet。&#xff08;它的构成。它的服务&#xff09; 1.因特网的主要构成 处在因特网的边缘部分就是在因特网上的所有主机&#xff0c;这些主机又称为端系统&#xff08;end system&#xff09;&#xff0c;端系统通过因特网服…
阅读更多...
【C2】文件，时间，多线程，动静态库

【C2】文件，时间，多线程，动静态库

文章目录 1.文件&#xff1a;fprint/fgets/fwrite/fread&#xff0c;ftell/rewind/fseek/fflush1.1 文本文件&#xff1a;FILE结构体1.2 二进制文件&#xff1a;没有行概念1.3 文件定位&#xff1a;linux下文本文件模式和二进制文件模式没有区别。fgets和fprintf以行方式读写文…
阅读更多...
【测试效率提升技巧】xmind测试用例转换为excel工具使用手册

【测试效率提升技巧】xmind测试用例转换为excel工具使用手册

【测试效率提升技巧】xmind测试用例转换为excel工具使用手册 一、前置环境配置二、执行Xmind2testcase的转换方法1.在控制台输入xmind2testcase [path/xmind文件路径] [-csv] [-xml] [-json]&#xff0c;例&#xff1a;xmind2testcase /root/homin/XX测试点.xmind -csv ##在当前…
阅读更多...
MacOS 升级golang版本后无法debug，升级delve版本

MacOS 升级golang版本后无法debug，升级delve版本

golang版本升级到1.20以后导致debug失效了&#xff0c;本文针对MacOS系统&#xff0c;win系统也可作参考。 WARNING: undefined behavior - version of Delve is too old for Go version 1.20.4 (maximum supported version 1.19) 1、升级delve版本 brew install delve 安装…
阅读更多...
抖音seo账号矩阵系统源码代开发组件

抖音seo账号矩阵系统源码代开发组件

一.开发矩阵系统的项目背景&#xff1a; 目录 一.开发矩阵系统的项目背景&#xff1a; 二.短视频矩阵系统SaaS模板组件通常包含以下几个方面的内容&#xff1a; 三.抖音SEO账号矩阵系统源码的技术搭建过程可以分为几个步骤&#xff1a; 1.确定系统的需求和目标&#xff0c…
阅读更多...
MATLAB App Designer基础教程 Matlab GUI入门（一）

MATLAB App Designer基础教程 Matlab GUI入门（一）

MATLAB GUI入门 第一天 学习传送门&#xff1a; 【MATLAB App Designer基础教程Matlab GUI界面设计&#xff08;全集更新完毕-用户界面设计appdesigner&#xff08;中文&#xff09;Matlab Gui教程】 https://www.bilibili.com/video/BV16f4y147x9/?p2&share_sourcecopy_…
阅读更多...
最新文章

Copyright @ 2022~2023