StackQueue+泛型简单理解

  • 🍁 个人主页：爱编程的Tom
  • 💫 本篇博文收录专栏：Java专栏
  • 👉 目前其它专栏：c系列小游戏     c语言系列--万物的开始_               
  • 🎉 欢迎 👍点赞✍评论⭐收藏💖三连支持一下博主🤞
  • 🧨现在的沉淀就是对未来的铺垫🎨 

目录

前言

栈（Stack）

栈的定义

栈的使用 

栈的模拟实现 

栈的应用场景

改变元素的序列  

将递归转化为循环 

队列(Queue) 

队列的定义 

队列的使用 

队列模拟实现 

循环队列 

双端队列 (Deque) 

泛型


 

前言

本篇文章将带你深入了解栈和队列的底层知识和基础架构，学会使用对数据的组织和运用！

栈（Stack）

栈的定义

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。

进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。

栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。  

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据在栈顶。

下面结合图片给出具体的理解：

 

栈的使用 

 

下面给出代码的运用加以理解： 

public static void main(String[] args) {
    Stack<Integer> s = new Stack();
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);
    System.out.println(s.size());   // 获取栈中有效元素个数---> 4
    System.out.println(s.peek());   // 获取栈顶元素---> 4
    s.pop();   // 4出栈，栈中剩余1   2   3，栈顶元素为3
    System.out.println(s.pop());   // 3出栈，栈中剩余1 2   栈顶元素为3
    if(s.empty()){
        System.out.println("栈空");
   }else{
        System.out.println(s.size());
   }
}

栈的模拟实现 

 

从上图中可以看到，Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的。 

Stack的具体模拟实现如下： 

public class MyStack {
    public int[] elem;
    public int usedSize;
    public static final int DEFAULT_CAPACITY = 10;
    public MyStack() {
        this.elem = new int[DEFAULT_CAPACITY];
    }

    //压栈
    public void push(int val) {
        if (isFull()) {
            this.elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize++] = val;
    }

    public boolean isFull() {
        return usedSize == elem.length;
    }


    //出栈
    public int pop() {
        if (isEmpty()) {
            throw new EmptyStackException("栈为空！！！！");
        }
        int oldVal = elem[usedSize-1];
        usedSize--;
        //elem[usedSize] = null;
        return oldVal;
    }

    public boolean isEmpty() {
        return usedSize == 0;
    }

    public int peek() {
        if(isEmpty()) {
            throw new EmptyStackException("栈为空！！！！！");
        }
        return elem[usedSize - 1];
    }
}

栈的应用场景

改变元素的序列  

如上图两题在栈的理解上，解决可得选项为 C 和 B.

将递归转化为循环 

这里给大家提供一个例子：逆序打印链表 

// 递归方式
void printList(Node head){
    if(null != head){
        printList(head.next);
        System.out.print(head.val + " ");
   }
}
 
// 循环方式
void printList(Node head){
    if(null == head){
        return;
   }
    
    Stack<Node> s = new Stack<>();
    // 将链表中的结点保存在栈中
    Node cur = head;
    while(null != cur){
        s.push(cur);
        cur = cur.next;
   }
// 将栈中的元素出栈
    while(!s.empty()){
        System.out.print(s.pop().val + " ");
   }
}

这里还有一些练习的题目：如果想更深入了解栈的相关机理，可以尝试做一做

1.括号匹配

2.逆波兰表达式 

3.出栈入栈次序匹配 

4.最小栈 

这里提出一个思考题：栈、虚拟机栈、栈帧有什么区别呢？

栈：栈是一种数据结构，具有后进先出（LIFO）的特性，用于存储函数调用、局部变量等数据。在计算机中，栈通常是指操作系统管理的内存区域，用于存储函数调用时的参数、返回地址、局部变量等。

虚拟机栈：虚拟机栈是指在Java虚拟机中用来执行Java方法的内存区域，用于存储方法的局部变量、操作数栈、动态链接、方法出口等信息。虚拟机栈与操作系统的栈类似，但是在Java虚拟机中，每个线程都有自己的虚拟机栈，用于执行方法时的数据存储。

栈帧：栈帧是指在方法调用时压入虚拟机栈中的数据结构，用于存储方法的局部变量、操作数栈、动态链接、方法出口等信息。每个方法调用都会创建一个对应的栈帧，用于存储该方法执行时需要的数据。栈帧是虚拟机栈中的一个重要组成部分，用于支持方法的执行和调用。

队列(Queue) 

队列的定义 

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，

队列具有先进先出FIFO(First In First Out)

入队列：进行插入操作的一端称为队尾（Tail/Rear）

出队列：进行删除操作的一端称为队头 （Head/Front）  

 

队列的使用 

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

队列模拟实现 

队列中既然可以存储元素，那底层肯定要有能够保存元素的空间

常见的空间类型有两种：顺序结构 和 链式结构。

思考题：队列的实现使用顺序结构还是链式结构好？ 

顺序结构：

优点：顺序结构的队列使用数组实现，插入和删除操作的时间复杂度为O(1)，在空间上比较节省。

缺点：在插入和删除元素时，需要移动其他元素，可能会导致性能下降。而且顺序结构的队列有容量限制，当队列满时需要进行扩容操作。

链式结构：

优点：链式结构的队列使用链表实现，插入和删除操作的时间复杂度为O(1)，不需要移动其他元素。而且链式结构的队列没有容量限制，可以动态增加或减少元素。

缺点：链式结构的队列在内存占用上比顺序结构更大，因为每个节点都需要额外的指针指向下一个节点。

总结：如果对内存占用要求比较高，且队列的大小是固定的，可以选择顺序结构实现队列；如果对插入和删除操作的性能要求比较高，且队列的大小是动态变化的，可以选择链式结构实现队列。

队列实现场景图：

 

下面给出模拟实现的代码（仅供参考）： 

public class Queue {
    // 双向链表节点
    public static class ListNode{
        ListNode next;
        ListNode prev;
        int value;
 
        ListNode(int value){
            this.value = value;
       }
   }
 
    ListNode first;   // 队头
    ListNode last;    // 队尾
    int size = 0;
 
    // 入队列---向双向链表位置插入新节点
    public void offer(int e){
        ListNode newNode = new ListNode(e);
        if(first == null){
            first = newNode;
            // last = newNode;
       }else{
            last.next = newNode;
            newNode.prev = last;
            // last = newNode;
       }
 
        last = newNode;
        size++;
   }
 
    // 出队列---将双向链表第一个节点删除掉
    public int poll(){
        // 1. 队列为空
        // 2. 队列中只有一个元素----链表中只有一个节点---直接删除
        // 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除
        int value = 0;
        if(first == null){
            return null;
       }else if(first == last){
            last = null;
            first = null;
       }else{
            value = first.value;
            first = first.next;
            first.prev.next = null;
            first.prev = null;
       }
        --size;
        return value;
   }
 
    // 获取队头元素---获取链表中第一个节点的值域
    public int peek(){
        if(first == null){
            return null;
       }
 
        return first.value;
   }
 
    public int size() {
        return size;
   }
 
    public boolean isEmpty(){
        return first == null;
   }
}

循环队列 

 

数组下标循环的小技巧

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

 

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

 

如何区分空与满 

1. 通过添加 size 属性记录 

2. 保留一个位置

3. 使用标记  

 

感兴趣的可以试试这道相关题目：设计循环队列 

双端队列 (Deque) 

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

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

 

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

这里给出两种实现方式：

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

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

泛型

泛型：就是适用于许多许多类型。从代码上讲，就是对类型实现了参数化。 

主要目的：就是指定当前的容器，要持有什么类型的对象。让编译器去做检查。 

在编译的过程当中，将所有的T替换为Object这种机制，这种机制称为：擦除机制。  

class MyArray<T> {
    public T[] array = (T[])new Object[10];//1
 
    public T getPos(int pos) {
        return this.array[pos];
   }
    public void setVal(int pos,T val) {
        this.array[pos] = val;
   }
}
public class TestDemo {
    public static void main(String[] args) {
        MyArray<Integer> myArray = new MyArray<>();//2
        myArray.setVal(0,10);
        myArray.setVal(1,12);
        int ret = myArray.getPos(1);//3
        System.out.println(ret);
        myArray.setVal(2,"bit");//4
   }
}

对上述代码进行一个说明：

1. 类名后的代表占位符，表示当前类是一个泛型类

了解：【规范】类型形参一般使用一个大写字母表示，

常用的名称有：

E 表示 Element

K 表示 Key

V 表示 Value

N 表示 Number

T 表示 Type

S, U, V 等等 - 第二、第三、第四个类型

2. 注释1处，不能new泛型类型的数组 ,说明：

T[] ts = new T[5];//是不对的

3. 注释2处，类型后加入 指定当前类型

4. 注释3处，不需要进行强制类型转换

5. 注释4处，代码编译报错，此时因为在注释2处指定类当前的类型，此时在注释4处，编译器会在存放元素的时 候帮助我们进行类型检查。

此处只对泛型做一个简单的介绍，不作过多解释，理解就好......  

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

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

相关文章

新的语言学习系统: 记忆镶嵌

新的语言学习系统: 记忆镶嵌

摘要 记忆镶嵌是由多个关联记忆网络协同工作来完成感兴趣的预测任务。与transformer类似,记忆镶嵌具有组合能力和上下文学习能力。与transformer不同,记忆镶嵌以相对透明的方式实现这些能力。该研究在玩具示例上展示了这些能力,并且还表明记忆镶嵌在中等规模语言建模任务上的表…
阅读更多...
JVM调优：JVM运行时数据区详解

JVM调优：JVM运行时数据区详解

一、前言 Java运行时数据区域划分&#xff0c;Java虚拟机在执行Java程序时&#xff0c;将其所管理的内存划分为不同的数据区域&#xff0c;每个区域都有特定的用途和创建销毁的时间。 其中&#xff0c;有些区域在虚拟机进程启动时就存在&#xff0c;而有些区域则是随着用户线程…
阅读更多...
YOLOv9-20240507周更说明|更新MobileNetv4等多种轻量化主干

YOLOv9-20240507周更说明|更新MobileNetv4等多种轻量化主干

专栏地址&#xff1a;目前售价售价69.9&#xff0c;改进点70 专栏介绍&#xff1a;YOLOv9改进系列 | 包含深度学习最新创新&#xff0c;助力高效涨点&#xff01;&#xff01;&#xff01; 本周已更新说明&#xff1a; ### ⭐⭐更新时间&#xff1a;2024/5/12⭐⭐ 1. YOLOv9…
阅读更多...
企业网站HTTP网站业务被慢连接攻击了该怎么办

企业网站HTTP网站业务被慢连接攻击了该怎么办

企业的网站建设中遇到网络攻击会出现哪些问题&#xff1f;一些中小型企业对于网络安全的认知不足&#xff0c;网站建设种类众多&#xff0c;电子商城类&#xff0c;小型游戏&#xff0c;支付类型&#xff0c;H5页面的网站&#xff0c;开发等等&#xff0c;如遇见网络攻击造成的…
阅读更多...
ubuntu server 22.04.4 系统安装详细教程

ubuntu server 22.04.4 系统安装详细教程

本教程使用vmware workstation 17创建虚拟机进行安装演示&#xff0c;安装方式和真机安装没有区别。 1、下载镜像 下载ubuntu server版本系统镜像&#xff0c;官网下载地址&#xff1a;https://cn.ubuntu.com/download/server/step1 注意&#xff1a;自己下载时需要确认是否是…
阅读更多...
ARP中间人

ARP中间人

文章目录 ARP中间人ARP协议介绍使用kali进行ARP毒化使用kali进行ARP中间人使用kali进行ARP钓鱼ARP攻击防御ARP总结 ARP中间人 ARP协议介绍 维基百科ARP介绍 ARP&#xff08;地址解析协议&#xff09;在网络通信中扮演着至关重要的角色&#xff0c;它通过将网络层地址&#x…
阅读更多...
运维基础（二）- 钉钉的使用

运维基础（二）- 钉钉的使用

一、钉钉的介绍&#xff08;来自百度百科&#xff09; 免费沟通和协同的多端平台 帮助中国企业通过系统化的解决方案&#xff08;微应用&#xff09;&#xff0c;全方位提升中国企业沟通和协同效率。 钉钉&#xff08;Ding Talk&#xff09; 是阿里巴巴打造的企业级智能移动…
阅读更多...
Windows环境下代码文档生成工具Doxygen使用详细教程

Windows环境下代码文档生成工具Doxygen使用详细教程

背景 最近研究aom源码&#xff0c;发现编译需要依赖Doxygen工具&#xff0c;故此篇博客详细记录下Doxygen的安装和使用。 Doxygen Doxygen 是一个强大的源代码文档生成工具&#xff0c;它支持多种编程语言&#xff0c;能够直接从源代码中的注释提取文档&#xff0c;并生成多…
阅读更多...
RabbitMQ中间件安装

RabbitMQ中间件安装

消息队列 RabbitMQ yum -y update yum -y install epel-release erlang # 安装erlang erl -version # 判断是否安装成功根据官网的的表格判断自己用哪个版本的 RabbitMQ&#xff1a;https://www.rabbitmq.com/docs/which-erlang#r16b03 [rootiZuf6hqrs5cb2ccyuc9nqvZ ~]# er…
阅读更多...
tomcat 设置JVM 参数

tomcat 设置JVM 参数

tomcat 启动的服务 设置jvm 设置的文件目录&#xff1a; /tomcat/bin/catalina.sh 添加设置参数&#xff1a; JAVA_OPTS“$JAVA_OPTS -server -Xms1024m -Xmx4096m -XX:MetaspaceSize1024m -XX:MaxMetaspaceSize2048m -XX:HeapDumpOnOutOfMemoryError -XX:HeapDumpPath/data/se…
阅读更多...
0510Goods的Maven项目

0510Goods的Maven项目

0510Goods的Maven项目包-CSDN博客 数据库字段 商品主页 修改页面 点击商品主页更改信息&#xff0c; 跳转到修改页面&#xff0c; 并保留初始信息。 商品类别最多选取三项&#xff0c;最少选取一项 添加界面 商品类别最多选取三项&#xff0c;最少选取一项
阅读更多...
第三方组件element-ui

第三方组件element-ui

1、创建 选vue2 不要快照 vue2于vue3差异 vue2main。js import Vue from vue import App from ./App.vueVue.config.productionTip falsenew Vue({render: h > h(App), }).$mount(#app)vue3 main.js vue2不能有多个跟组件&#xff08;div&#xff09;
阅读更多...
老胡的周刊（第141期）

老胡的周刊（第141期）

老胡的信息周刊[1]&#xff0c;记录这周我看到的有价值的信息&#xff0c;主要针对计算机领域&#xff0c;内容主题极大程度被我个人喜好主导。这个项目核心目的在于记录让自己有印象的信息做一个留存以及共享。 &#x1f3af; 项目 koishi[2] 周刊群友推荐&#xff0c;创建跨平…
阅读更多...
对博客系统基本功能进行自动化测试（Junit + Selenium)

对博客系统基本功能进行自动化测试（Junit + Selenium)

环境搭建&#xff1a; 浏览器&#xff1a; 本次测试使用Chrome浏览器在jdk的bin目录下安装对应浏览器驱动&#xff08;尽量选择与浏览器版本相近的驱动&#xff09;chromedriver.storage.googleapis.com/index.htmlJunit依赖&#xff1a; <!-- https://mvnreposit…
阅读更多...
【linux-IMX6ULL-RTC-IIC-SPI配置思路】

【linux-IMX6ULL-RTC-IIC-SPI配置思路】

目录 1. RTC简介1.1 IMX6ULL中的RTC1.2 SNVS_LP中的SRTC配置流程1.3 程序实现 2. IIC通信协议2.1 IIC基础2.2 IIC通信协议2.2.1 IIC写时序2.2.2 IIC读时序 3. IIC通信的硬件框图及配置流程3.1 IMX6ULL的硬件IIC框图3.1 IIC配置流程3.2 硬件IIC代码实现 4. SPI通信4.1 SPI通信基…
阅读更多...
【Python探索之旅】选择结构（条件语句）

【Python探索之旅】选择结构（条件语句）

文章目录 条件结构&#xff1a; 1.1 if单分支结构 1.2 if-else 多分支结构 1.3 if-elif 多重结构&#xff1a; 完结撒花​ 前言 Python条件语句是通过一条或多条语句的执行结果&#xff08;True或者False&#xff09;来决定执行的代码块。 Python提供了顺序、选择、循环三…
阅读更多...
IP SSL怎么签发使用

IP SSL怎么签发使用

IP证书的签发首先是需要有一个可供绑定的IP地址&#xff0c;作为常用数字证书之一&#xff0c;IP证书也因为其广泛的应用范围而深得用户的青睐和喜欢。 部署IP证书后&#xff0c;可以实现该IP地址的https访问&#xff0c;过程和域名证书相差不多。 IP证书和域名证书的区别 很…
阅读更多...
针对关键 PuTTY 私钥恢复漏洞的 PoC 发布

针对关键 PuTTY 私钥恢复漏洞的 PoC 发布

安全研究人员针对广泛使用的 PuTTY SSH 和 Telnet 客户端中的一个关键漏洞发布了概念验证 (PoC) 漏洞利用。 该漏洞CVE-2024-31497允许攻击者恢复 PuTTY 版本 0.68 至 0.80 中使用 NIST P-521 椭圆曲线生成的私钥。 该漏洞源于 PuTTY在使用 P-521 曲线时偏向生成ECDSA随机数。…
阅读更多...
算法课程笔记——自下而上树形DP

算法课程笔记——自下而上树形DP

算法课程笔记——自下而上树形DP #include<bits/stdc.h>usingnamespacestd; constintN100005; intn,a[N]; longlongdp[N][2]; vector<int> e[N]; voiddfs(intu){for(autov:e[u]){dfs(v);dp[u][1]dp[v][0];dp[u][0]max(dp[v][0],dp[v][1]);}dp[u][1]a[u]; } intmain…
阅读更多...
Vue中CSS动态样式绑定与注意事项

Vue中CSS动态样式绑定与注意事项

vue中css使用动态变量_vue css变量 动态-CSDN博客 需求&#xff1a; vue使用el-select&#xff0c;下拉选择值时‘输入框’的背景图片就改变为对应所选项的背景图 分析 &#xff1a; 每次下拉选择&#xff0c;值发生变化&#xff0c;背景图与值一一对应绑定&#xff0c;为动态…
阅读更多...
最新文章

Copyright @ 2022~2023