当前位置:

首页 > 编程开发 > Java栈和队列的应用场景和用法举例

Java栈和队列的应用场景和用法举例

在学习栈和队列之前,先了解一下什么是线性表:一次保存单个同类型的元素,多个元素之间逻辑上连续,比如数组,链表,字符串,栈和队列栈和队列其实操作受限的线性表,数组也罢,链表也罢,既可以在头部插入和删除,也能在尾部插入和删除,但是栈和队列只能在一端插入,在一端删除一、栈1.定义只能在一端插入元素,也只能在这一端删除元素(栈顶),可以把栈看作一个“水杯”,只能从一端添加元素,也只能从一段删除元素,而且,先进入水杯的水在杯底,后进入水杯的水在杯顶,往出倒水的时候,也是倒出的杯顶的水,栈也是一样,先入栈的元素在栈底

本文目录

    Java栈和队列的应用场景和用法举例

    在学习栈和队列 之前,先了解一下什么是线性表:一次保存单个同类型的元素,多个元素之间逻辑上连续,比如数组,链表,字符串,栈和队列
    栈和队列其实操作受限的线性表,数组也罢,链表也罢,既可以在头部插入和删除,也能在尾部插入和删除,但是栈和队列只能在一端插入,在一端删除

    一、栈

    1.定义

    只能在一端插入元素,也只能在这一端删除元素(栈顶),可以把栈看作一个“水杯”,只能从一端添加元素,也只能从一段删除元素,而且,先进入水杯的水在杯底,后进入水杯的水在杯顶,往出倒水的时候,也是倒出的杯顶的水,栈也是一样,先入栈的元素在栈底,后入栈的元素在栈顶,所以先入栈的元素后出,后入栈的元素先出,这也是栈的特性“先进后出,后进先出”Last In First Out(LIFO),取出元素和添加元素只能在栈顶。
    将1 2 3 4 5,一次放入栈中
    Java栈和队列的应用场景和用法举例

    2.栈的应用

    1.无处不在的undo(撤销)操作

    在任何一个编辑器中输错一个内容后,使用Ctrl + z就返回到了输入的内容;
    在任何一个浏览器中点击后退操作
    Java栈和队列的应用场景和用法举例
    都是栈的这个结构的应用
    1.使用编辑器使用撤销操作,一次输入就把内容压入栈中,再输入就就再压入栈中,发现一次输入错误,就使用撤销操作,把当前栈顶的错误内容弹出,那么当前栈顶的内容就是上次输入的内容。
    2.浏览网页其实也是相同原理的,就像打开百度 -> 打开csdn -> 打开创作中心,也是使用栈这个结构,先把百度网页压入栈中 ,然后csdn网页压入栈中,然后创作中心网页压入栈中,想要返回到csdn主页,按下后头箭头,就把当前栈顶的创作中心网页弹出,取出csdn主页。

    2.操作系统栈

    程序再执行的过程中,从A函数调用B函数,从B函数调用C函数,调用结束,返回执行时,如何得知从哪继续开始执行呢,背后也是栈这个结构

    3.栈的实现

    基于链表实现的栈 – 链式栈
    基于数组实现的栈 – 顺序栈(使用较多)
    定义一个基于动态数组实现的栈

    //基于动态数组实现的顺序栈public class MyStack {
        //记录当前栈的元素个数
        private int size;
        //实际存储数据的动态数组,此时在栈中只能在数组的尾部添加和删除元素
        private List data = new ArrayList<>();
        }

    4.栈的操作

    1.向栈中添加一个元素
    只能在栈顶添加

     /**
         * 向当前栈中添加元素 -- >压栈操作
         * @param val
         */
        public void push(E val){
            data.add(val);
            size++;
        }

    2.当前从栈顶弹出一个元素

    /**
         * 弹出当前栈顶元素,返回栈顶元素的值
         * @return
         */
        public E pop(){
            if (isEmpty()){
                //栈为空无法弹出
                throw new NoSuchElementException("stack is empty!cannot pop!");
            }
            //在数组末尾删除元素
            E val = data.get(size - 1);
            data.remove(size - 1);
            size --;
            return val;
        }

    3.查看当前栈顶元素,但不弹出

    /**
         * 查看当前栈顶元素值,不弹出该元素
         * @return
         */
        public E peek(){
            if (isEmpty()){
                throw new NoSuchElementException("stack is empty!cannot peek!");
            }
            return data.get(size - 1);
        }

    二、队列

    1.定义

    队列:先进先出(FIFO)的数据结构i,元素只能从队尾添加到队列中,也只能从队首出队列,元素的出队顺序和入队顺序保持一致
    将1 2 3 4 5依次入队
    Java栈和队列的应用场景和用法举例

    2.队列的应用

    现实生活中,各种各样的“排队”操作

    3.队列的实现

    基于数组实现的队列 – 顺序队列
    基于链表实现的队列 – 链式队列
    出队操作只能在队列的头部进行,若采用数组实现的队列,每次出队一个元素就得搬移剩下的所有元素向前移动一个单位,此时采用链表实现的队列更适合队列的结构,删除元素只需要删除头结点,添加元素在链表的尾部添加

    public interface Queue {
        //入队操作
        void offer(E val);
        //出队操作
        E poll();
        //查看队首元素
        E peek();
        boolean isEmpty();}

    对于栈来说队列的实现子类是比较多的,比如
    FIFO队列
    双端队列
    循环队列
    优先级队列
    不管哪个队列都要实现

    4.FIFO队列

    1.定义一个FIFO队列

    // An highlighted blockvar foo = 'bar';

    2.向队列中添加一个元素

    public void offer(E val) {
            Node node = new Node<>(val);
            if (head == null){
                head = tail = node;
            }else{
                //链表的尾插
                tail.next = node;
                tail = node;
            }
            size++;
        }

    3.从当前队首出队一个元素

     public E poll() {
            if (isEmpty()){
                throw new NoSuchElementException("queue is empty! cannot poll!");
            }
            //头删
            E val = head.val;
            Node node = head;
            head = head.next;
            node.next = node = null;
            size--;
            return val;
        }

    4.查看当前队列的队首元素

    public E peek() {
            if (isEmpty()){
                throw new NoSuchElementException("queue is empty!cannot peek!");
            }
            return head.val;
        }

    5.循环队列

    1.定义:基本上都是使用固定长度的数组来实现,数组在实现队时,若从数组头部删除元素需要频繁的移动后面的元素,效率比较低;出队和入队操作,使用两个引用,一个head,一个tail,添加元素在数组的尾部添加,删除元素只需要移动head引用指向的地址即可(逻辑删除)
    2.应用:操作系统的生产消费者模型,MySQL数据库的InnoDB存储引擎的redo日志
    3.循环队列就是使用长度固定的数组来实现,数组头部就是队首(head),数组的尾部就是队尾(tail),数组[head…tail)时循环队列的有效元素
    head永远指向循环队列的第一个元素
    tai永远指向循环队列有效元素的后一个位置
    Java栈和队列的应用场景和用法举例
    此时循环队列的有效元素就为7 9 1两个元素
    循环队列出队一个元素,就只用让head引用向后移动一个位置
    Java栈和队列的应用场景和用法举例
    此时循环队列的有效元素就只有9 和 1 两个元素了
    再出队一个元素,但此时head引用已经走到末尾了,所谓循环队列就是当head或者tail引用走到数组末尾时,再向后移动就是返回数组头部的操作,循环队列最大好处就是进行元素的删除的时候不需要进行数据的搬移操作,当有新的元素添加到队列中就会覆盖掉原来的元素,就只需要将tail索引位置覆盖上新的元素,再让tail再向后移动

    当队列为空时,head == tail

    Java栈和队列的应用场景和用法举例

    当队列已“满”时,head == tail

    Java栈和队列的应用场景和用法举例
    循环队列需要注意的关键点
    1.因此当head 和 tail相等时,没法区分此时循环队列已满,还是为空,因此在循环队列中,若(tail + 1) % n == head就认为循环队列已满
    Java栈和队列的应用场景和用法举例
    此时循环队列就已经满了,在循环队列中就会浪费一个空间,判断队列是否已满
    2.head和tail的移动不能简单的 + 1,使用取模操作,取数组长度
    tail = (tail + 1) % n
    head = (head + 1) % n
    对数组长度取模的本质:
    当head和tai走到数组最后一个索引位置时,下一次要返回数组头部,就必须用 + 1对数组长度取模
    3.head == tail时,认为队列为空

    6.循环队列的操作

    1.定义一个循环队列

    //基于整形的循环队列public class LoopQueue implements Queue {
        //定长数组
        private Integer[] data;
        //指向队首元素
        int head;
        //指向队尾元素的下一个元素
        int tail;
        public LoopQueue(int size){
            data = new Integer[size + 1];
        }}

    2.向循环队列中添加一个元素

    @Override    public void offer(Integer val) {
           if (isFull()){
               throw new ArrayIndexOutOfBoundsException("loopQueue is full!cannot offer");
           }
           data[tail] = val;
           tail = (tail + 1) % data.length;
        }

    3.从循环队列中出队一个元素

     @Override    public Integer poll() {
            if (isEmpty()){
                throw new NoSuchElementException("loopQueue is empty!cannot poll!");
            }
            Integer val = data[head];
            head = (head + 1) % data.length;
            return val;
        }

    4.查看当前循环队列队首元素

     @Override    public Integer peek() {
            if (isEmpty()){
                throw new NoSuchElementException("loopQueue is empty!cannot peek!");
            }
            return data[head];
        }

    5.判断当前循环队列是否为空

     @Override    public boolean isEmpty() {
            return head == tail;
        }

    6.判断当前循环队列是否已满

     public boolean isFull(){
            return (tail + 1) % data.length == head;
        }

    7.toString方法

    public String toString(){
            StringBuilder sb = new StringBuilder();
            sb.append("front [");
            //最后一个有效元素的索引
            int lsatIndex = tail == 0 ? data.length - 1 : tail - 1;
            for (int i = head; i != tail;) {
                sb.append(data[i]);
                if (i != lsatIndex){
                    sb.append(", ");
                }
                i = (i + 1) % data.length;
            }
            sb.append("] tail");
            return sb.toString();
        }

    7.双端队列

    双端队列:Deque是Queue的子接口,这个队列既可以尾插,头出;也可以头插,尾出
    Java栈和队列的应用场景和用法举例
    双端队列的一个常用子类就是LinkedList,不管使用栈还是队列,都可以统一使用双端队列接口
    1.现在需要一个栈
    Java栈和队列的应用场景和用法举例
    2.现在需要一个队列
    Java栈和队列的应用场景和用法举例

    本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系bd@zhengruan.com
    作者最新文章
    编程开发 Java
    相关文章 更多
    Yandex官网入口及网页搜索使用方法
    Yandex官网入口及网页搜索使用方法

    Yandex官网入口是https://www.yondex.net/,该平台支持多语言切换、智能搜索匹配、虚拟键盘变更及实时翻译,提供地图、图片、新闻、购物等垂直服务,并具备账户同步、隐私管理、个性化首页和云存储等功能。

    Java单元测试入门:使用JUnit 5编写第一个测试用例
    Java单元测试入门:使用JUnit 5编写第一个测试用例

    面向初学者的JUnit 5实用入门指南。从测试概念、Maven依赖配置,到手把手编写首个单元测试用例及断言验证,助你掌握Java单元测试的核心流程。

    Java变量未初始化报错解析:局部变量与成员变量默认值差异
    Java变量未初始化报错解析:局部变量与成员变量默认值差异

    深入解析Java中局部变量未初始化编译报错与成员变量自动赋予默认值的机制差异,涵盖JVM内存分配、编译期确定性赋值检查与实际排查修复方案。

    Java获取当前时间并格式化输出:DateTimeFormatter与SimpleDateFormat
    Java获取当前时间并格式化输出:DateTimeFormatter与SimpleDateFormat

    详细讲解在Java中获取当前系统时间并进行格式化输出的两种核心方案:基于Java 8全新日期时间API的DateTimeFormatter与传统遗留的SimpleDateFormat,包含完整代码示例、线程安全机制对比及生产选型建议。

    Java中final与static final常量的定义及初始化规则
    Java中final与static final常量的定义及初始化规则

    深入解析Java中final变量与static final常量的定义、内存语义、初始化时机及合法赋值路径,涵盖编译期常量优化与实战避坑指南。

    Java抽象方法与接口方法的区别及选型建议
    Java抽象方法与接口方法的区别及选型建议

    深入对比Java中抽象类抽象方法与接口方法的语法演进、设计意图及运行期差异,并提供清晰的架构选型决策流程与实战范例。

    Java实现HTTP请求与JSON解析的完整代码示例
    Java实现HTTP请求与JSON解析的完整代码示例

    本文提供Java标准库HttpClient发起HTTP GET/POST请求并结合Jackson进行JSON数据反序列化与序列化的完整代码示例与工程实践指南。

    Java递归出现StackOverflowError的原因分析及栈空间优化方案
    Java递归出现StackOverflowError的原因分析及栈空间优化方案

    详细分析Java递归调用出现StackOverflowError的原因,结合代码说明线程栈、栈帧和递归深度之间的关系,并介绍终止条件排查、迭代改写、减少栈帧开销以及通过-Xss调整JVM栈空间的方法。

    Java空指针异常(NPE)的代码排查与修复实例
    Java空指针异常(NPE)的代码排查与修复实例

    针对Java中常见的NullPointerException(NPE),本文从堆栈日志定位、典型代码触发场景、具体修复代码对比到防御体系进行系统讲解,提供实用且易上手的排查与修复方案。

    selenium上传文件教程本地文件路径设置方法
    selenium上传文件教程本地文件路径设置方法

    深入解析Selenium处理文件上传的技术细节,涵盖标准HTML控件的路径直接注入法与非标准控件的系统级模拟方案,提供Windows与Linux环境下的路径设置最佳实践及常见异常排查。

    查看更多
    精品专题 更多
    装机必备
    装机必备

    正软商城装机必备专区,精选办公、浏览器、安全防护、影音播放、压缩解压、设计创作和系统工具等电脑常用正版软件,帮助用户快速完成新电脑软件配置。

    Windows
    Windows

    正软商城Windows软件专区,汇集适用于Windows电脑的办公、设计、安全防护、影音播放、开发工具和系统优化软件,提供软件介绍、系统要求、正版授权及购买下载服务。

    PDF教程
    PDF教程

    正软商城PDF教程频道提供PDF编辑、转换、合并、拆分、压缩及格式处理方法,同时介绍常用PDF软件和工具的使用技巧。

    Mac软件 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    Aperty macOS版
    Aperty macOS版
    macOS

    Aperty 是 Skylum 推出的 AI 人像修图软件,支持自然肤质修饰、瑕疵处理、面部与身体调整、预设及批量同步。

    WINDOWS 更多
    讯飞智作 网页版
    讯飞智作 网页版
    Windows/ macOS/ Linux

    讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

    火山引擎 网页版
    火山引擎 网页版
    Windows/ macOS/ Linux

    火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

    PixTV 网页版
    PixTV 网页版
    Windows

    PixTV 是一款在浏览器中使用的 AI 视觉内容创作平台,提供图片、视频、音频、文字生成、AI 分镜、局部重绘、提示词反推和无限画布等工具,适合短剧、漫剧、广告及社交媒体内容制作。