当前位置: 首页 > news >正文

栈和队列(数据结构)

1. (Stack)

1.1 概念
:一种特殊的线性表,其 只允许在固定的一端进行插入和删除元素操作 。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO Last In First Out )的原则。
压栈:栈的插入操作叫做进栈 / 压栈 / 入栈, 入数据在栈顶
出栈:栈的删除操作叫做出栈。 出数据在栈顶
如图所示:
进栈:进栈顺序是ABCD,A先压入栈底,B压在A上,如此依次压栈,最后的D就是栈顶数据
出栈:只能从一端出,所以栈顶数据先出,出栈顺序就为DCBA,D最先出,A最后出

 现实生活也有很多像栈一样的结构,如枪里的子弹最先打出去的是最后装的子弹,羽毛球桶最先拿出来的羽毛球是最后放进去的,都符合栈的后进先出LIFO(Last In First Out)的原则。

1.2栈的常用方法

2. 队列(Queue)

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

2.2 队列的实现

如图我们可以知道队列是一个接口,接口不能实例化,但可以通过实现了该接口的类来实例化,所以   Queue可以通过ArrayList,LinkedList,PriorityQueue等来实例化该接口;

public static void main ( String [] args ) {
Queue < Integer > q = new LinkedList <> ();
Queue < Integer > q1 = new ArrayList <> ();
Queue < Integer > q2  = new  PriorityQueue <> ();
}

 循环队列

如何区分空与满
1. 通过添加 size 属性记录
2. 保留一个位置
3. 使用标记
通过1方法来模拟实现k长度的循环队列:
class MyCircularQueue {int[] elem;int front;int rear;int size;public MyCircularQueue(int k) {elem=new int[k];front=rear=0;}public boolean enQueue(int value) {if(isFull()){return false;}else{elem[rear]=value;rear=(rear+1)% elem.length;size++;return true;}}public boolean deQueue() {if(isEmpty()){return false;}else{front=(front+1)%elem.length;size--;return true;}}public int Front() {if(isEmpty()){return -1;}return elem[front];}public int Rear() {if(isEmpty()){return -1;}int rear1=(rear==0)?elem.length-1:rear-1;//rear==0的时候比较特殊return elem[rear1];}public boolean isEmpty() {return size==0;}public boolean isFull() {return size==elem.length;}
}

通过2方法来模拟实现k长度的循环队列:
class MyCircularQueue {int[] elem;int front;int rear;public MyCircularQueue(int k) {elem=new int[k+1];//浪费一个空间来判断循环队列的队满;front=rear=0;}public boolean enQueue(int value) {if(isFull()){return false;}else{elem[rear]=value;rear=(rear+1)% elem.length;return true;}}public boolean deQueue() {if(isEmpty()){return false;}else{front=(front+1)%elem.length;return true;}}public int Front() {if(isEmpty()){return -1;}return elem[front];}public int Rear() {if(isEmpty()){return -1;}int rear1=(rear==0)?elem.length-1:rear-1;//rear==0的时候比较特殊return elem[rear1];}public boolean isEmpty() {return front==rear;}public boolean isFull() {return (rear+1)% elem.length==front;}
}

4.栈和队列的相互转化

4.1用队列实现栈

栈:先进后出

队列:先进先出

进栈的实现:两队列都空就放数据到队列1里,否则就哪个队列为空就放哪里

出栈的实现:将有不为空的队列里的size-1个元素方到另一个队列里,然后就将只剩下一个元素的队列出队列就实现的出栈;

class MyStack {

    Queue<Integer> queue1;

    Queue<Integer> queue2;

    public MyStack() {

        queue1=new LinkedList<>();

        queue2=new LinkedList<>();

    }

    public void push(int x) {

        if(!queue1.isEmpty()){

            queue1.add(x);

        }else if(!queue2.isEmpty()){

            queue2.add(x );

        }else{

            queue1.add(x);

        }

    }

    public int pop() {

        if(empty()){

            return -1;

        }

        if (queue1.isEmpty()){

            int size= queue2.size();

            for (int i = 0; i < size-1; i++) {

                int val=queue2.poll();

                queue1.add(val);

            }

            return queue2.poll();

        }

        else {

            int size= queue1.size();

            for (int i = 0; i < size-1; i++) {

                int val = queue1.poll();

                queue2.add(val);

            }

            return queue1.poll();

        }

    }

    public int top() {

        if(empty()){

            return -1;

        }

        if (queue1.isEmpty()){

            int size= queue2.size();

            for (int i = 0; i < size-1; i++) {

                int val=queue2.poll();

                queue1.add(val);

            }

            int val2= queue2.peek();

            queue1.add(queue2.poll());

            return val2;

        }

        else {

            int size= queue1.size();

            for (int i = 0; i < size-1; i++) {

                int val = queue1.poll();

                queue2.add(val);

            }

            int val2= queue1.peek();

            queue2.add(queue1.poll());

            return val2;

        }

    }

    public boolean empty() {

        return (queue2.isEmpty()&&queue1.isEmpty());

    }

}

注意: 

问题:观察上图发现只是实例化queue接口的类不一样,其余代码一样,那为什么结果会不一样呢?

解答:

优先级队列 是会自动按照升序排序的 也就是每次push进来一个元素 都会自动排成升序  所以stack中从栈底到栈顶分别是  1 2 2 3 4,因此结果是4  4  3


而双向链表是没有排序这个性质 从栈底到栈顶分别是  1 2 3 4 2 ,因此结果是 2 2 4 

4.1用栈实现栈队列

栈:先进后出

队列:先进先出

进队的模拟实现:

stack1专门用来放元素,都为空的时候就将元素加入stack1中,stack1不为空就直接push,为空就将stack2中的元素全部放入stack1中

出队的模拟实现:

stack2专门用来出元素,进行出对操作时将元素放入stack2中出元素即可

class MyQueue {

    Stack<Integer> stack1;

    Stack<Integer> stack2;

    public MyQueue() {

        stack1=new Stack<>();

        stack2=new Stack<>();

    }

    public void push(int x) {

        if(!stack1.isEmpty()) {

            stack1.push(x);

        }else if(!stack2.isEmpty()){

            int size=stack2.size();

            for (int i = 0; i < size; i++) {

                 int val=stack2.pop();

                 stack1.push(val);

            }

            stack1.push(x);

        }else{

            stack1.push(x);

        }

    }

    public int pop() {

        if(empty()){

            return -1;

        }

        if(stack2.isEmpty()){

            int size=stack1.size();

            for (int i = 0; i < size; i++) {

                stack2.push(stack1.pop());

            }

            return stack2.pop();

        }else{

            return stack2.pop();

        }

    }

    public int peek() {

        if(empty()){

            return -1;

        }

        if(stack2.isEmpty()){

            int size=stack1.size();

            for (int i = 0; i < size; i++) {

                stack2.push(stack1.pop());

            }

            return stack2.peek();

        }else{

            return stack2.peek();

        }

    }

    public boolean empty() {

        return stack1.isEmpty()&&stack2.isEmpty();

    }

}

相关文章:

栈和队列(数据结构)

1. 栈(Stack) 1.1 概念 栈 &#xff1a;一种特殊的线性表&#xff0c;其 只允许在固定的一端进行插入和删除元素操作 。进行数据插入和删除操作的一端称为栈顶&#xff0c;另一端称为栈底。栈中的数据元素遵守后进先出LIFO &#xff08; Last In First Out &#xff09;的原…...

如何实现ElementUI表单项label的文字提示?

在Vue和ElementUI的丰富组件库中,定制化表单是常见的需求之一。那么如何在表单项label后添加文字提示,以提升用户体验呢? 首先我们来看一下效果图: 这里我们鼠标移动到❓图标上就会出现提示 在 ElementUI 中,el-form-item 组件允许使用 slot 自定义 label。通过在 el-fo…...

c++中的标准库

前言 hello&#xff0c;我是文宇。 正文 C标准库是C编程语言的基本组成部分之一&#xff0c;它为开发人员提供了一套丰富和强大的工具和功能&#xff0c;以便快速开发高效、可靠和可移植的应用程序。C标准库由两个主要部分组成&#xff1a;STL&#xff08;Standard Template…...

洛谷 B2145 digit 函数 B2146 Hermite 多项式 题解

题目目录&#xff1a; No.1 B2145 digit 函数 No.2 B2146 Hermite 多项式 OK&#xff0c;开始正文&#xff01; 第一题&#xff1a;B2145 digit 函数 题目描述 在程序中定义一函数 digit(n,k)&#xff0c;它能分离出整数 n 从右边数第 k 个数字。 输入格式 正整数 n …...

tailwindcss @apply 和 @layer 有什么区别

在 Tailwind CSS 中&#xff0c;apply 和 layer 是两个不同的指令&#xff0c;它们各自有不同的用途和功能。以下是它们的区别和使用方法&#xff1a; apply 指令 apply 指令用于将一组现有的 Tailwind CSS 工具类应用到一个自定义的 CSS 类中。这对于简化和复用复杂的样式非…...

React 中的 useMemo 和 useCallback

1. useMemo语法 const memoizedValue useMemo(() > computeExpensiveValue(a, b), deps); 1. 传入一个函数进去&#xff0c;会返回一个 memoized 值&#xff0c;需要注意的是&#xff0c;函数内必须有返回值&#xff1b; 2. 第二个参数会依赖值&#xff0c;当依赖值更新…...

idea社区版lombok总是突然失效:log未知的变量

用maven打包运行就没问题&#xff0c;就是idea的原因 有这么个参数 -Djps.track.ap.dependenciesfalse 是用来配置 IntelliJ IDEA 的 JVM 参数&#xff0c;它控制着 IntelliJ IDEA 是否跟踪处理器相关的依赖关系。具体来说&#xff0c;-Djps.track.ap.dependenciesfalse 参数的…...

Java语言程序设计基础篇_编程练习题*16.13(比较不同利率的贷款)

目录 题目&#xff1a;*16.13&#xff08;比较不同利率的贷款&#xff09; 习题思路 代码示例 结果展示 题目&#xff1a;*16.13&#xff08;比较不同利率的贷款&#xff09; 改写编程练习题5.21&#xff0c;创建一个图形用户界面&#xff0c;如图16-41b所示。程序应该允许…...

正点原子imx6ull-mini-Linux驱动之Regmap API 实验

我们在前面学习 I2C 和 SPI 驱动的时候&#xff0c;针对 I2C 和 SPI 设备寄存器的操作都是通过相关 的 API 函数进行操作的。这样 Linux 内核中就会充斥着大量的重复、冗余代码&#xff0c;但是这些本质 上都是对寄存器的操作&#xff0c;所以为了方便内核开发人员统一访问 I2C…...

postgresql 双重排序后 重复项 标识次序

postgresql 双重排序后 重复项 标识次序 在PostgreSQL中&#xff0c;如果你想要在双重排序后标识重复项的次序&#xff0c;可以使用窗口函数&#xff08;window functions&#xff09;。一个常见的方法是使用ROW_NUMBER()窗口函数&#xff0c;它会为每个分组内的行分配一个唯一…...

线程池ThreadPoolExecutor使用

文章目录 一、基础-Java中线程创建的方式1.1、继承Thread类创建线程1.2、实现Runnable接口创建线程1.3、实现Calable接口创建线程1.4、使用线程池创建线程二、概念-线程池基本概念2.1、并发和井行的主要区别2.1.1、处理任务不同2.1.2、存在不同2.1.3、CPU资源不同2.2、什么是线…...

Codeforces Round 963 (Div. 2)

A题&#xff1a;Question Marks 题目&#xff1a; Tim正在做一个由 4n 个问题组成的测试&#xff0c;每个问题都有 4 个选项&#xff1a;“A”、“B”、“C”和“D”。对于每个选项&#xff0c;有 n 个正确答案对应于该选项&#xff0c;这意味着有 n 个问题的答案为“A”。 n…...

Mysql函数学习笔记

MySQL 字符串函数 ASCII(s) 返回字符串 s 的第一个字符的 ASCII 码。 //返回 CustomerName 字段第一个字母的 ASCII 码 SELECT ASCII(CustomerName) AS NumCodeOfFirstChar FROM Customers;CHAR_LENGTH(s)-返回字符串 s 的字符数 //返回字符串 RUNOOB 的字符数 SELECT CHAR…...

【Linux基础】Linux基本指令(一)

目录 前言1&#xff0c; ls指令2&#xff0c;pwd指令三&#xff0c;cd指令3.1 当前目录与上级目录3.2 绝对路径和相对路径 四&#xff0c;创建一个普通文件或目录4.1 touch指令4.2 mkdir指令 五&#xff0c;删除目录或文件5.1 rmdir指令5.2 rm 指令 前言 从本章开始&#xff0…...

全球视野:航空蓄电池的国际标准与技术创新

航空蓄电池是一种专门为满足航空工业独特要求而设计的高性能储能设备。由于航空环境的特殊性&#xff0c;如高海拔、极端温度变化、频繁的充放电需求、以及对于设备重量和体积的严格限制&#xff0c;航空蓄电池需要具备一系列高级特性以确保飞机在各种飞行条件下能够安全有效地…...

11-初识python的函数——定义和调用

1 函数简介 function input()、print()、range()、len()都是python的内置函数&#xff0c;可以直接使用的 函数&#xff1a;可以用来保存代码&#xff0c;在需要的时候对这些语句进行重复调用 优点&#xff1a; 1. 遇到重复功能的时候&#xff0c;直接调用即可&#xff0c;…...

Windows安装Swoft框架

实现方式&#xff1a; 安装虚拟机&#xff0c;在虚拟机里用宝塔搭建环境后安装Swoft&#xff0c; 然后用Phpstorm SSH方式开发&#xff0c;用Apipost调用 websocket服务。 1、安装虚拟机&#xff0c;下载和安装参见 &#xff1a; https://blog.csdn.net/2401_84297265/article…...

阅读台灯什么品牌好?一文带你了解热门阅读台灯推荐

阅读台灯最终都绕不开护眼这个话题。护眼灯作为保护视力的辅助工具&#xff0c;以有效护眼的价值深受大众青睐。学生长时间用眼&#xff0c;普通台灯的伤害大&#xff0c;而阅读台灯的出现&#xff0c;通过其先进的技术和设计&#xff0c;能为学生提供了一个既舒适又健康的照明…...

1、.Net UI框架:Xamarin Forms - .Net宣传系列文章

Xamarin.Forms是一个跨平台移动应用开发框架&#xff0c;它允许开发者使用C#和.NET进行一次编码&#xff0c;然后在iOS、Android、macOS和Windows等多个平台上运行。Xamarin.Forms是Xamarin的一部分&#xff0c;而Xamarin是微软的.NET跨平台开发工具集&#xff0c;它提供了一套…...

Tomcat 最大连接数实现原理

spring boot 内置tomcat设置连接数 max-connections: 5 server:port: 9898servlet:context-path: /testtomcat:connection-timeout: 5000max-connections: 5accept-count: 5 ##初始化连接数量connectionLimitLatch protected LimitLatch initializeConnectionLatch() {if (ma…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...