数据结构《栈和队列》

文章目录

  • 一、什么是栈？
    • 1.1 栈的模拟实现
    • 1.2 关于栈的例题
  • 二、什么是队列？
    • 2.2 队列的模拟实现
    • 2.2 关于队列的例题
  • 总结

提示：关于栈和队列的实现其实很简单，基本上是对之前的顺序表和链表的一种应用，代码部分也不难。主要的是对栈和队列的实际运用。

一、什么是栈？

可以理解为一个竖过来的数组、顺序表，同时这个数组只能将末尾的元素先推出来，再推出来前面的元素，也就是我们所说的，先进后出、后进先出。
在这里插入图片描述
栈的实例化

Stack<E> stack = new Stack<>();

1.1 栈的模拟实现

在这里插入图片描述

自定义的接口，规范自定义的类,便于模拟实现

public interface IStack {
    //放入元素
    int push(int a);
    //推出栈顶元素
    int pop();
    //查看栈顶元素
    int peek();
    //栈是否为空
    boolean isEmpty(int[] array);
    //栈中的元素个数
    int size();
    //栈中寻找某个元素距离栈顶的距离
    int search(int a);
}

push(int a) — 将元素放入栈中

public int push(int a) {
        isFull(array);
        array[useSide++] = a;
        return a;
    }

在这里插入图片描述

peek() — 查看栈顶元素

public int peek() {
        try {
            if(isEmpty(array)){
                throw new EmptyException("空数组读取异常");
            }
        }catch (EmptyException e){
            e.printStackTrace();
        }
        return array[useSide - 1];
    }

在这里插入图片描述

pop() — 出栈顶元素

public int pop() {
        int top = peek();
        useSide--;
        return top;
    }

在这里插入图片描述

isEmpty(int[] array) — 判断栈是否为空

public boolean isEmpty(int[] array) {
        return array.length == useSide;
    }

size() — 得到栈中的元素个数

public int size() {
        return useSide;
    }

search(int a) — 得到栈中某个元素距离栈顶的距离，栈顶元素位置按1来计算

public int search(int a) {
        int cur = useSide - 1;
        int len = 1;
        while (0 <= cur){
            if(a == array[cur]){
                return len;
            }else {
                cur--;
                len++;
            }
        }
        return -1;
    }

代码整合

public class MyStack implements IStack{
    private int[] array;

    public MyStack() {
        this.array = new int[10];
    }
    private int useSide;


    private void isFull(int[] check){
        if(isEmpty(check)){
            array = Arrays.copyOf(check,2*check.length);
        }
    }
    @Override
    public int push(int a) {
        isFull(array);
        array[useSide++] = a;
        return a;
    }

    @Override
    public int pop() {
        int top = peek();
        useSide--;
        return top;
    }

    @Override
    public int peek() {
        try {
            if(isEmpty(array)){
                throw new EmptyException("空数组读取异常");
            }
        }catch (EmptyException e){
            e.printStackTrace();
        }
        return array[useSide - 1];
    }

    @Override
    public boolean isEmpty(int[] array) {
        return array.length == useSide;
    }

    @Override
    public int size() {
        return useSide;
    }

    @Override
    public int search(int a) {
        int cur = useSide - 1;
        int len = 1;
        while (0 <= cur){
            if(a == array[cur]){
                return len;
            }else {
                cur--;
                len++;
            }
        }
        return -1;
    }
}

1.2 关于栈的例题

例题1 有效括号
在这里插入图片描述
在这里插入图片描述

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        if(s == null){
            return false;
        }
        for(int i = 0; i < s.length(); i++){
            char cur = s.charAt(i);
            if(cur == '(' || cur == '{' || cur == '['){
                stack.push(cur);
            }else if(cur == ')' || cur == '}' || cur == ']'){
                if(stack.isEmpty()){
                    return false;
                }
                if(cur == ')'&&stack.peek() == '(' || 
                   cur == '}'&&stack.peek() == '{' || 
                   cur == ']'&&stack.peek() == '['){
                    stack.pop();
                }else{
                    return false;
                }
            }else{
                return false;
            }
        }
        if(stack.isEmpty()){
            return true;
        }
        return false;
    }
}

例题2 逆波兰表达式
在这里插入图片描述

public int evalRPN(String[] tokens) {
        
        Stack<String> stack = new Stack<>();
        for(int i = 0; i < tokens.length; i++){
            if(tokens[i].equals("+") || tokens[i].equals("-") || tokens[i].equals("*") || tokens[i].equals("/")){
                int m = Integer.parseInt(stack.pop());
                int n = Integer.parseInt(stack.pop());
                if(tokens[i].equals("+")){
                    stack.push(String.valueOf(m+n));
                }else if(tokens[i].equals("-")){
                    stack.push(String.valueOf(n-m));
                }else if(tokens[i].equals("*")){
                    stack.push(String.valueOf(m*n));
                }else{
                    stack.push(String.valueOf(n/m));
                }
            }else{
                stack.push(tokens[i]);
            }
        }
        return Integer.parseInt(stack.pop());
    }

例题3 最小栈
在这里插入图片描述

public Stack<Integer> stack;
    public Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
        if(minStack.empty()){
            minStack.push(val);
        }else{
            int m = minStack.peek();
            if(m >= val){
                minStack.push(val);
            }
        }
    }
    
    public void pop() {
        if(stack.empty()){
            return;
        }
        int m = stack.pop();
        if(m == minStack.peek()){
            minStack.pop();
        }
    }
    
    public int top() {
        if(stack.empty()){
            return -1;
        }
        return stack.peek();
    }
    
    public int getMin() {
        if(minStack.empty()){
            return -1;
        }
        return minStack.peek();
    }

例题4 栈的压入、弹出序列
在这里插入图片描述

public boolean IsPopOrder (int[] pushV, int[] popV) {
        // write code here
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for(int i = 0; i < pushV.length;i++){
            stack.push(pushV[i]);
            while(!stack.isEmpty() && stack.peek() == popV[j] && j < popV.length){
                stack.pop();
                j++;
            }
        }
        
        return stack.isEmpty();
    }

二、什么是队列？

可以理解为一个双向链表(一个一个节点在排队)，同时这个链表只能将队头的元素先推出来，再推出来后面的元素，也就是我们所说的，先进先出、后进后出。
在这里插入图片描述
队列的实例化

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

2.2 队列的模拟实现

在这里插入图片描述

自定义的接口，规范自定义的类,便于模拟实现

public interface IQueue {
    //
    int offer(int a);
    int poll();
    int peek();
    boolean isEmpty();
}

isEmpty() — 判断是否为空队列

@Override
    public boolean isEmpty() {
        return useSide == 0;
    }

offer(int a) — 从队尾放入元素

public int offer(int a) {
        ListNode listNode = new ListNode(a);
        listNode.val = a;
        if(isEmpty()){
            head = listNode;
            last = listNode;
        }else {
            last.next = listNode;
            listNode.pre = last;
            last = listNode;
        }
        useSide++;
        return a;
    }

在这里插入图片描述

peek() — 查看队头元素

public int peek() {
        try {
            if(head == null){
                throw new EmptyException("空指针异常访问");
            }
        }catch (EmptyException e){
            e.printStackTrace();
        }
        return head.val;
    }

在这里插入图片描述

poll() — 推出队头的元素

public int poll() {
        int fisrt = peek();
        head = head.next;
        useSide --;
        return fisrt;
    }

在这里插入图片描述

代码整合

public class MyQueue implements IQueue{

    static class ListNode{
        int val;
        ListNode pre;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    private ListNode head;
    private ListNode last;
    private int useSide;


    @Override
    public int offer(int a) {
        ListNode listNode = new ListNode(a);
        listNode.val = a;
        if(isEmpty()){
            head = listNode;
            last = listNode;
        }else {
            last.next = listNode;
            listNode.pre = last;
            last = listNode;
        }
        useSide++;
        return a;
    }

    @Override
    public int poll() {
        int fisrt = peek();
        head = head.next;
        useSide --;
        return fisrt;
    }

    @Override
    public int peek() {
        try {
            if(head == null){
                throw new EmptyException("空指针异常访问");
            }
        }catch (EmptyException e){
            e.printStackTrace();
        }
        return head.val;
    }

    @Override
    public boolean isEmpty() {
        return useSide == 0;
    }

}

2.2 关于队列的例题

例题1 设计循环队列
在这里插入图片描述

class MyCircularQueue {
    public int[] array;
    int front;
    int rear;

    public MyCircularQueue(int k) {
        array = new int[k+1];
    }
    // 向循环队列插入一个元素。如果成功插入则返回真。
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        array[rear] = value;
        rear = (rear+1) % array.length;
        return true;
    }
    //从循环队列中删除一个元素。如果成功删除则返回真。
    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }
        front = (front+1) % array.length;
        return true;
    }
    //从队首获取元素。如果队列为空，返回 -1 。
    public int Front() {
        if(isEmpty()){
            return -1;
        }
        return array[front];
    }
    //获取队尾元素。如果队列为空，返回 -1 。
    public int Rear() {
        if(isEmpty()){
            return -1;
        }
        if(rear == 0){
            return array[array.length - 1];
        }
        return array[rear-1];
    }
    //检查循环队列是否为空。
    public boolean isEmpty() {
        return rear == front;
    }
    //检查循环队列是否已满。
    public boolean isFull() {
        return (rear+1) % array.length == front;
    }
}

例题2 用队列实现栈
在这里插入图片描述

class MyStack {
    public Queue<Integer> queue1;
    public Queue<Integer> queue2;
    int size;
    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }
    
    public void push(int x) {
        if(queue1.isEmpty() && queue2.isEmpty()){
            queue1.offer(x);
            size++;
        }else if(!queue1.isEmpty()){
            queue1.offer(x);
            size++;
        }else if(!queue2.isEmpty()){
            queue2.offer(x);
            size++;
        }
    }
    
    public int pop() {
        if(queue1.isEmpty() && queue2.isEmpty()){
            return -1;
        }
        if(queue1.isEmpty() && !queue2.isEmpty()){
            int cur = size - 1;
            while(cur != 0){
                queue1.offer(queue2.poll());
                cur--;
            }
            size--;
            return queue2.poll();
        }else if(!queue1.isEmpty() && queue2.isEmpty()){
            int cur = size - 1;
            while(cur != 0){
                queue2.offer(queue1.poll());
                cur--;
            }
            size--;
            return queue1.poll();
        }
        return -1;
    }
    
    public int top() {
        if(queue1.isEmpty() && queue2.isEmpty()){
            return -1;
        }
        if(queue1.isEmpty() && !queue2.isEmpty()){
            int cur = size - 1;
            while(cur != 0){
                queue1.offer(queue2.poll());
                cur--;
            }
            int m = queue2.peek();
            queue1.offer(queue2.poll());
            return m;
        }else if(!queue1.isEmpty() && queue2.isEmpty()){
            int cur = size - 1;
            while(cur != 0){
                queue2.offer(queue1.poll());
                cur--;
            }
            int m = queue1.peek();
            queue2.offer(queue1.poll());
            return m;
        }
        return -1;
    }
    
    public boolean empty() {
        return size == 0;
    }

}

例题3 用栈实现队列
在这里插入图片描述

Stack<Integer> stack1;
    Stack<Integer> stack2;
    int size = 0;

    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    //将元素 x 推到队列的末尾
    public void push(int x) {
        stack1.push(x);
        size++;
    }
    //从队列的开头移除并返回元素
    public int pop() {
        if(empty()){
            return -1;
        }
        if(!stack2.isEmpty()){
            size--;
            return stack2.pop();
        }else if(stack2.isEmpty() && !stack1.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
            size--;
            return stack2.pop();
        }
        return -1;
    }
    //返回队列开头的元素
    public int peek() {
        if(empty()){
            return -1;
        }
        if(!stack2.isEmpty()){
            return stack2.peek();
        }else if(stack2.isEmpty() && !stack1.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
            return stack2.peek();
        }
        return -1;
    }
    //如果队列为空，返回 true ；否则，返回 false
    public boolean empty() {
        return size == 0;
    }

总结

本篇文章介绍了有关数据结构中的栈和队列的相关内容，以及它们的简单实现，和简单使用，如果有什么不正确的或者不严谨的地方，还望指正，谢谢大家！

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

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

相关文章

ComfyUI-image2video模型部署教程

ComfyUI-image2video模型部署教程

一、介绍 本项目基于ComfyUI进行部署&#xff0c;在上面可以简单实现图片到视频的效果。也就是可以通过给定一张图片&#xff0c;实现的功能是图片动起来。 二、部署 要求显存&#xff1a;VAE解码需要13G以上 1. 部署ComfyUI 本篇的模型部署是在ComfyUI的基础上进行&#x…
阅读更多...
react中如何在一张图片上加一个灰色蒙层，并添加事件？

react中如何在一张图片上加一个灰色蒙层，并添加事件？

最终效果&#xff1a; 实现原理&#xff1a; 移动到图片上的时候&#xff0c;给img加一个伪类 &#xff01;&#xff01;此时就要地方要注意了&#xff0c;因为img标签是闭合的标签&#xff0c;无法直接添加 伪类&#xff08;::after&#xff09;&#xff0c;所以 我是在img外…
阅读更多...
使用Axios函数库进行网络请求的使用指南

使用Axios函数库进行网络请求的使用指南

目录 前言1. 什么是Axios2. Axios的引入方式2.1 通过CDN直接引入2.2 在模块化项目中引入 3. 使用Axios发送请求3.1 GET请求3.2 POST请求 4. Axios请求方式别名5. 使用Axios创建实例5.1 创建Axios实例5.2 使用实例发送请求 6. 使用async/await简化异步请求6.1 获取所有文章数据6…
阅读更多...
基于Java Web 的家乡特色菜推荐系统

基于Java Web 的家乡特色菜推荐系统

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…
阅读更多...
opencv kdtree pcl kdtree 效率对比

opencv kdtree pcl kdtree 效率对比

由于项目中以一个环节需要使用kdtree ,对性能要求比较严苛&#xff0c;所以看看那个kdtree效率高一些。对比了opencv和pcl。 #include <array> #include <deque> #include <fstream> #include <opencv2/highgui.hpp> #include <opencv2/imgproc.hpp…
阅读更多...
Flink_DataStreamAPI_输出算子Sink

Flink_DataStreamAPI_输出算子Sink

Flink_DataStreamAPI_输出算子Sink 1连接到外部系统2输出到文件3输出到Kafka4输出到MySQL&#xff08;JDBC&#xff09;5自定义Sink输出 Flink作为数据处理框架&#xff0c;最终还是要把计算处理的结果写入外部存储&#xff0c;为外部应用提供支持。 1连接到外部系统 Flink的D…
阅读更多...
RAG经验论文《FACTS About Building Retrieval Augmented Generation-based Chatbots》笔记

RAG经验论文《FACTS About Building Retrieval Augmented Generation-based Chatbots》笔记

《FACTS About Building Retrieval Augmented Generation-based Chatbots》是2024年7月英伟达的团队发表的基于RAG的聊天机器人构建的文章。 这篇论文在待读列表很长时间了&#xff0c;一直没有读&#xff0c;看题目以为FACTS是总结的一些事实经验&#xff0c;阅读过才发现FAC…
阅读更多...
【Android compose原创组件】在Compose里面实现内容不满一屏也可以触发边界阻尼效果的一种可用方法

【Android compose原创组件】在Compose里面实现内容不满一屏也可以触发边界阻尼效果的一种可用方法

创意背景 在安卓 View 传统命令式开发里面提供了非常多稳定美观体验好的组件&#xff0c;但是目前Compose还未有可用的组件&#xff0c;比如View中可以使用 coordinatorlayout 的滚动效果可以实现局部&#xff08;即使内容不满一屏也可以触发滚动边界阻尼效果&#xff09;&…
阅读更多...
Android笔记(三十六)：封装一个Matrix从顶部/底部对齐的ImageView

Android笔记(三十六)：封装一个Matrix从顶部/底部对齐的ImageView

背景 ImageView的scaleType默认显示图片是这样&#xff0c;但是有时候设计稿需求希望图片左右能紧贴着ImageView左右边缘&#xff0c;又不破坏图片的比例&#xff0c;用自带的matrix&#xff0c;centerCrop等都可以满足 但是都会造成图片的某些区域被裁剪了&#xff0c;如果设…
阅读更多...
docker desktop运行rabittmq容器，控制台无法访问

docker desktop运行rabittmq容器，控制台无法访问

docker desktop运行rabittmq容器&#xff0c;控制台无法访问 启动过程&#xff1a;…此处缺略&#xff0c;网上一大堆 原因 原因是在Docker上运行的RabbitMQ&#xff0c;默认情况下是没有启用管理插件和管理页面的 解决办法 使用命令 docker exec -it 容器id /bin/bash 进…
阅读更多...
重拾CSS，前端样式精读-媒体查询

重拾CSS，前端样式精读-媒体查询

前言 本文收录于CSS系列文章中&#xff0c;欢迎阅读指正 说到媒体查询&#xff0c;大家首先想到的可能是有关响应式的知识点&#xff0c;除此之外&#xff0c;它还可以用于条件加载资源&#xff0c;字体大小&#xff0c;图像和视频的优化&#xff0c;用户界面调整等等方面&am…
阅读更多...
使用 Grafana api 查询 Datasource 数据

使用 Grafana api 查询 Datasource 数据

一、使用grafana 的api 接口 官方API 二、生成Api key 点击 Administration -》Users and accss -》Service accounts 进入页面 点击Add service account 创建 service account 点击Add service account token 点击 Generate token , 就可以生成 api key 了 三、进入grafana…
阅读更多...
uniapp luch-request 使用教程+响应对象创建

uniapp luch-request 使用教程+响应对象创建

1. 介绍 luch-request 是一个基于 Promise 开发的 uni-app 跨平台、项目级别的请求库。它具有更小的体积、易用的 API 和方便简单的自定义能力。luch-request 支持请求和响应拦截、全局挂载、多个全局配置实例、自定义验证器、文件上传/下载、任务操作、自定义参数以及多拦截器…
阅读更多...
革新人脸图片智能修复

革新人脸图片智能修复

&#x1f3e1;作者主页&#xff1a;点击&#xff01; &#x1f916;编程探索专栏&#xff1a;点击&#xff01; ⏰️创作时间&#xff1a;2024年11月16日20点46分 神秘男子影, 秘而不宣藏。 泣意深不见, 男子自持重, 子夜独自沉。 论文链接 点击开启你的论文编程之旅…
阅读更多...
OpenGL ES 文字渲染方式有几种？

OpenGL ES 文字渲染方式有几种？

在音视频或 OpenGL 开发中，文字渲染是一个高频使用的功能，比如制作一些酷炫的字幕、为视频添加水印、设置特殊字体等等。 实际上 OpenGL 并没有定义渲染文字的方式，所以我们最能想到的办法是：将带有文字的图像上传到纹理，然后进行纹理贴图。 本文分别介绍下在应用层和 C+…
阅读更多...
Javaweb-day12（登录认证）

Javaweb-day12（登录认证）

登录功能 登录校验&#xff08;重点&#xff09; 登录校验指的是在服务器接收到浏览器发送过来的请求之后&#xff0c;首先要对这个请求进行校验&#xff0c;先要校验一下用户登录了没有 怎么来实现登录校验的操作呢&#xff1f;具体的实现思路可以分为两部分&#xff1a; 在…
阅读更多...
DBeaver中PostgreSQL数据库显示不全的解决方法

DBeaver中PostgreSQL数据库显示不全的解决方法

本文介绍在DBeaver中&#xff0c;连接PostgreSQL后&#xff0c;数据库显示不全的解决方法。 最近&#xff0c;在DBeaver中连接了本地的PostgreSQL数据库。但是连接后打开这个数据库时发现&#xff0c;其所显示的Databases不全。如下图所示&#xff0c;Databases只显示了一个pos…
阅读更多...
计算机视觉 1-8章 (硕士)

计算机视觉 1-8章 (硕士)

文章目录 零、前言1.先行课程&#xff1a;python、深度学习、数字图像处理2.查文献3.环境安装 第一章&#xff1a;概论1.计算机视觉的概念2.机器学习 第二章&#xff1a;图像处理相关基础1.图像的概念2.图像处理3.滤波器4.卷积神经网络CNN5.图像的多层表示&#xff1a;图像金字…
阅读更多...
如何使用EasyExcel生成多列表组合填充的复杂Excel示例

如何使用EasyExcel生成多列表组合填充的复杂Excel示例

作者&#xff1a;Funky_oaNiu 一、&#xff08;需求&#xff09;生成的表格效果&#xff1a;二、搞一个模板文件三、建立对应的表格实体类四、开始填充五、Vue3前端发起请求下载六、官方文档及AI问答 一、&#xff08;需求&#xff09;生成的表格效果&#xff1a; 其中只有顶部…
阅读更多...
手机ip地址异常怎么解决

手机ip地址异常怎么解决

在现代社会中&#xff0c;手机已成为我们日常生活中不可或缺的一部分&#xff0c;无论是工作、学习还是娱乐&#xff0c;都离不开网络的支持。然而&#xff0c;有时我们会遇到手机IP地址异常的问题&#xff0c;这不仅会影响我们的网络体验&#xff0c;还可能带来安全隐患。本文…
阅读更多...
最新文章

Copyright @ 2022~2023