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

数据结构《栈和队列》

文章目录

  • 一、什么是栈?
    • 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);}}@Overridepublic int push(int a) {isFull(array);array[useSide++] = a;return a;}@Overridepublic int pop() {int top = peek();useSide--;return top;}@Overridepublic int peek() {try {if(isEmpty(array)){throw new EmptyException("空数组读取异常");}}catch (EmptyException e){e.printStackTrace();}return array[useSide - 1];}@Overridepublic boolean isEmpty(int[] array) {return array.length == useSide;}@Overridepublic int size() {return useSide;}@Overridepublic 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 hereStack<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() — 判断是否为空队列

@Overridepublic 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;@Overridepublic 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;}@Overridepublic int poll() {int fisrt = peek();head = head.next;useSide --;return fisrt;}@Overridepublic int peek() {try {if(head == null){throw new EmptyException("空指针异常访问");}}catch (EmptyException e){e.printStackTrace();}return head.val;}@Overridepublic 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 ;否则,返回 falsepublic boolean empty() {return size == 0;}

总结

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

相关文章:

数据结构《栈和队列》

文章目录 一、什么是栈&#xff1f;1.1 栈的模拟实现1.2 关于栈的例题 二、什么是队列&#xff1f;2.2 队列的模拟实现2.2 关于队列的例题 总结 提示&#xff1a;关于栈和队列的实现其实很简单&#xff0c;基本上是对之前的顺序表和链表的一种应用&#xff0c;代码部分也不难。…...

C# 超链接控件LinkLabel无法触发Alt快捷键

在C#中&#xff0c;为控件添加快捷键的方式有两种&#xff0c;其中一种就是Windows中较为常见的Alt快捷键&#xff0c;比如运行对话框&#xff0c;记事本菜单等。只需要按下 Alt 框号中带下划线的字母即可触发该控件的点击操作。如图所示 在C#开发中&#xff0c;实现类似的操作…...

JVM类加载过程-Loading

一、Class对象的生命周期 .class文件是如何加载到内存中:.class文件是ClassLoader通过IO将文件读到内存,再通过双亲委派的模式进行Loading,再Linking、以及Initializing,代码调用等一系列操作后,进行GC,组成完整的生命周期; 二、双亲委派模式(Loading的过程): 1、类…...

2024年11月19日Github流行趋势

项目名称&#xff1a;build-your-own-x 项目维护者&#xff1a;danistefanovic, rohitpaulk, sarupbanskota 等项目介绍&#xff1a;通过从零开始重新创建你最喜欢的技术来掌握编程。项目star数&#xff1a;312,081项目fork数&#xff1a;29,004 项目名称&#xff1a;freqtrad…...

详细描述一下Elasticsearch索引文档的过程?

大家好&#xff0c;我是锋哥。今天分享关于【详细描述一下Elasticsearch索引文档的过程&#xff1f;】面试题。希望对大家有帮助&#xff1b; 详细描述一下Elasticsearch索引文档的过程&#xff1f; Elasticsearch的索引文档过程是其核心功能之一&#xff0c;涉及将数据存储到…...

基于css的Grid布局和vue实现点击左移右移轮播过渡动画效果

直接上代码&#xff0c;以下代码基于vue2,需要Vue3或者react可以使用国内直连GPT/Claude来帮你转换下 代码如下&#xff1a; // ScrollCardsGrid.vue <template><div class"scroll-cards-container"><!-- 左箭头 --><div v-show"showLef…...

HarmonyOS NEXT应用元服务开发Intents Kit(意图框架服务)习惯推荐方案概述

一、习惯推荐是HarmonyOS学习用户的行为习惯后做出的主动预测推荐。 1.开发者将用户在应用/元服务内的使用行为向HarmonyOS共享&#xff0c;使得HarmonyOS可以基于共享的数据学习用户的行为习惯。 2.在HarmonyOS学习到用户的行为习惯后&#xff0c;会给用户推荐相应功能&#x…...

【AtCoder】Beginner Contest 380-F.Exchange Game

题目链接 Problem Statement Takahashi and Aoki will play a game using cards with numbers written on them. Initially, Takahashi has N N N cards with numbers A 1 , … , A N A_1, \ldots, A_N A1​,…,AN​ in his hand, Aoki has M M M cards with numbers B …...

30. 并发编程

一、什么是多任务 如果一个操作系统上同时运行了多个程序&#xff0c;那么称这个操作系统就是 多任务的操作系统&#xff0c;例如&#xff1a;Windows、Mac、Android、IOS、Harmony 等。如果是一个程序&#xff0c;它可以同时执行多个事情&#xff0c;那么就称为 多任务的程序。…...

【包教包会】CocosCreator3.x框架——带翻页特效的场景切换

一、效果演示 二、如何获取 1、https://gitee.com/szrpf/TurnPage 2、解压&#xff0c;导入cocos creator&#xff08;版本3.8.2&#xff09;&#xff0c;可以直接运行Demo演示 三、算法思路 1、单场景 页面预制体 通过loadScene来切换页面&#xff0c;无法实现页面特效。…...

k8s上面的Redis集群链接不上master的解决办法

问题描述 之前在k8s上面部署了一台node&#xff0c;然后创建了6个redis的pod&#xff0c;构建了一个redis的集群&#xff0c;正常运行。 最近添加了一台slave node&#xff0c;然后把其中的几个redis的pod调度到了slave node上面&#xff0c;结果集群就起不来了&#xff0c;…...

<项目代码>YOLOv8 瞳孔识别<目标检测>

YOLOv8是一种单阶段&#xff08;one-stage&#xff09;检测算法&#xff0c;它将目标检测问题转化为一个回归问题&#xff0c;能够在一次前向传播过程中同时完成目标的分类和定位任务。相较于两阶段检测算法&#xff08;如Faster R-CNN&#xff09;&#xff0c;YOLOv8具有更高的…...

网络编程-002-UDP通信

1.UDP通信的简单介绍 1.1不需要通信握手,无需维持连接,网络带宽需求较小,而实时性要求高 1.2 包大小有限制,不发大于路径MTU的数据包 1.3容易丢包 1.4 可以实现一对多,多对多 2.客户端与服务端=发送端与接收端 代码框架 收数据方一般都是客户端/接收端 3.头文件 #i…...

MySQL更换瀚高语法更换

MySQL更换瀚高语法更换 一、前言二、语句 一、前言 水一篇,mysql更换瀚高之后&#xff0c;一些需要更换的语法介绍 > 二、语句 MySQL瀚高MySQL用法瀚高用法说明ifnull(x,y)coalesce(x,y)相同相同用于检查两个表达式并返回第一个非空表达式。如果第一个表达式不是 NULL&…...

Object.prototype.hasOwnProperty.call(item, key) 作用与用途

在 JavaScript 中&#xff0c;Object.prototype.hasOwnProperty.call(item, key) 是一种检查对象 item 是否具有特定属性 key 作为自身的属性&#xff08;而不是继承自原型链&#xff09;的方法。这种调用方式是安全的&#xff0c;特别是在处理可能被修改过原型链的对象时。 解…...

DNS的10种资源记录

前言 在DNS&#xff08;域名系统&#xff09;中&#xff0c;常见的资源记录&#xff08;Resource Records, RR&#xff09;用于存储域名与IP地址、邮件服务器等网络资源之间的映射关系。以下是几种常见的DNS资源记录&#xff1a; 1. A记录&#xff08;Address Record&#xf…...

【数据分享】1981-2024年我国逐日最低气温栅格数据(免费获取)

气象数据一直是一个价值很高的数据&#xff0c;它被广泛用于各个领域的研究当中。之前我们分享过来源于美国国家海洋和大气管理局&#xff08;NOAA&#xff09;下设的国家环境信息中心(NCEI)发布的1929-2024年全球站点的逐日最低气温数据&#xff08;可查看之前的文章获悉详情&…...

Kafka进阶_1.生产消息

文章目录 一、Controller选举二、生产消息2.1、创建待发送数据2.2、创建生产者对象&#xff0c;发送数据2.3、发送回调2.3.1、异步发送2.3.2、同步发送 2.4、拦截器2.5、序列化器2.6、分区器2.7、消息可靠性2.7.1、acks 02.7.2、acks 1(默认)2.7.3、acks -1或all 2.8、部分重…...

百度世界2024:智能体引领AI应用新纪元

在近日盛大举行的百度世界2024大会上&#xff0c;百度创始人李彦宏以一场题为“文心一言”的精彩演讲&#xff0c;再次将全球科技界的目光聚焦于人工智能&#xff08;AI&#xff09;的无限可能。作为一名科技自媒体&#xff0c;我深感这场演讲不仅是对百度AI技术实力的一次全面…...

NIST 发布后量子密码学转型战略草案

美国国家标准与技术研究所 (NIST) 发布了其初步战略草案&#xff0c;即内部报告 (IR) 8547&#xff0c;标题为“向后量子密码标准过渡”。 该草案概述了 NIST 从当前易受量子计算攻击的加密算法迁移到抗量子替代算法的战略。该草案于 2024 年 11 月 12 日发布&#xff0c;开放…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...

Linux部署私有文件管理系统MinIO

最近需要用到一个文件管理服务&#xff0c;但是又不想花钱&#xff0c;所以就想着自己搭建一个&#xff0c;刚好我们用的一个开源框架已经集成了MinIO&#xff0c;所以就选了这个 我这边对文件服务性能要求不是太高&#xff0c;单机版就可以 安装非常简单&#xff0c;几个命令就…...

c# 局部函数 定义、功能与示例

C# 局部函数&#xff1a;定义、功能与示例 1. 定义与功能 局部函数&#xff08;Local Function&#xff09;是嵌套在另一个方法内部的私有方法&#xff0c;仅在包含它的方法内可见。 • 作用&#xff1a;封装仅用于当前方法的逻辑&#xff0c;避免污染类作用域&#xff0c;提升…...

第八部分:阶段项目 6:构建 React 前端应用

现在&#xff0c;是时候将你学到的 React 基础知识付诸实践&#xff0c;构建一个简单的前端应用来模拟与后端 API 的交互了。在这个阶段&#xff0c;你可以先使用模拟数据&#xff0c;或者如果你的后端 API&#xff08;阶段项目 5&#xff09;已经搭建好&#xff0c;可以直接连…...

基于开源AI智能名片链动2 + 1模式S2B2C商城小程序的沉浸式体验营销研究

摘要&#xff1a;在消费市场竞争日益激烈的当下&#xff0c;传统体验营销方式存在诸多局限。本文聚焦开源AI智能名片链动2 1模式S2B2C商城小程序&#xff0c;探讨其在沉浸式体验营销中的应用。通过对比传统品鉴、工厂参观等初级体验方式&#xff0c;分析沉浸式体验的优势与价值…...