数据结构(Java)实现:栈和队列

文章目录

  • 1. 栈的模拟实现
    • 1.1 普通栈的模拟实现
    • 1.2 泛型栈的模拟实现
  • 2. 栈的介绍
  • 3. 栈的使用
  • 4. 栈的应用场景
    • 4.1 改变元素的序列
    • 4.2 将递归转换为循环
    • 4.3 使用栈解题
  • 5. 栈的链表实现
  • 6. 队列概念
  • 7. 队列的使用
  • 8. 模拟队列的实现
    • 8.1 链式队列
    • 8.2 顺序队列
  • 9. 双端队列

1. 栈的模拟实现

在这里插入图片描述
从上图中可以看到,Stack继承了Vector,Vector和ArrayList类似,都是动态的顺序表,不同的是Vector是线程安全的。

1.1 普通栈的模拟实现

在这里插入图片描述
栈的模拟实现没有顺序表和链表难,实现代码和对应的注释如下。

public class MyStack {int[] elem;int usedSize=0;public MyStack(){elem=new int[10];}//入栈public void push(int e){//判满,如果满了扩容if(isFull()){elem= Arrays.copyOf(elem,elem.length*2);}//入栈elem[usedSize]=e;usedSize++;}//判满public boolean isFull(){return usedSize==elem.length;}//出栈public int pop(){//判空,如果为空返回-1if(empty()){return -1;}//出栈后元素个数减一usedSize--;return elem[usedSize];}//查看public int peek(){//判空,如果为空返回-1if(empty()){return -1;}//peek只返回,不删除return elem[usedSize-1];}//判空public boolean empty(){return usedSize==0;}
}

测试代码

    public static void main(String[] args) {MyStack s=new MyStack();s.push(1);s.push(2);s.push(3);System.out.println(s.pop());System.out.println(s.peek());System.out.println(s.peek());}

1.2 泛型栈的模拟实现

要使栈变成泛型,仅需改变数据类型。

public class MyStack2 <E>{public Object[] elem;//泛型的本质是Object类public int usedSize = 0;public MyStack2(){elem=new Object[10];}public void push(E e){if(isFull()){elem= Arrays.copyOf(elem,elem.length*2);}elem[usedSize]=e;usedSize++;}public boolean isFull(){return usedSize==elem.length;}//出栈public E pop(){//返回类型为Eif(empty()){return null;}usedSize--;return (E)elem[usedSize];//类型转换}public E peek(){//返回类型为Eif(empty()){return null;}return (E)elem[usedSize-1];//类型转换}public boolean empty(){return usedSize==0;}
}

测试代码

    public static void main(String[] args) {MyStack2<String > s = new MyStack2<>();s.push("hello");s.push("zzuli");s.push("welcome");s.push("to");s.push("zzuli");System.out.println(s.pop());System.out.println(s.pop());System.out.println(s.peek());System.out.println(s.peek());}

2. 栈的介绍

:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶
出栈:栈的删除操作叫做出栈。出数据在栈顶
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

3. 栈的使用

在这里插入图片描述

    public static void main(String[] args) {Stack<Integer> s=new Stack<>();s.push(1);//入栈s.push(2);//入栈s.push(3);//入栈s.push(4);//入栈s.push(5);//入栈System.out.println(s.size());//栈的数据个数System.out.println(s.pop());//出栈System.out.println(s.pop());//出栈System.out.println(s.peek());//查看栈顶元素System.out.println(s.peek());//查看栈顶元素if(s.empty()){//判空System.out.println("栈空");}else{System.out.println("栈不为空");}}

4. 栈的应用场景

4.1 改变元素的序列

在这里插入图片描述
答案:C、B

4.2 将递归转换为循环

当我们逆序打印单向链表时,可以通过递归的方式打印。

// 递归方式
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 + " ");}}

4.3 使用栈解题

  1. 括号匹配
  2. 逆波兰表达式求值
  3. 出栈入栈次序匹配
  4. 最小栈

上面四题题解链接

5. 栈的链表实现

Java集合类的Stack底层是一个数组。这种栈叫做顺序栈。那么是否可以使用链表来实现栈呢?
在这里插入图片描述
如果那单链表来实现栈,最好使用链表头部进行入栈和头栈,这样时间复杂度为O(1)。相反,如果从链表的尾部入栈和出栈,时间复杂度为O(n)(此时需要遍历链表才能实现入栈和出栈)。
在这里插入图片描述
如果使用双向链表,从链表的头或者尾进行入栈和出栈,时间复杂度均为O(1)。因此,如果我们要使用链式栈,就可以选用双线链表来操作。
代码示例

    public static void main(String[] args) {LinkedList<Integer> stack=new LinkedList<>();stack.push(1);//入栈stack.push(2);stack.push(3);stack.pop();//出栈}

通过Ctrl查看LInkedListpush方法和pop方法可以发现,其本质是链表的头插和头删。
在这里插入图片描述
在这里插入图片描述

6. 队列概念

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出得的特点FIFO(First In First Out)。
入队列:进行插入操作的一端称为队尾(Tail/Rear)
出队列:进行删除操作的一端称为队头(Head/Front)
在这里插入图片描述

7. 队列的使用

在Java中,Queue是个接口,底层是通过链表实现的
在这里插入图片描述

方法功能
boolean offer(E e)入队列
E poll()出队列
peek()获取队头元素
int size()获取队列中有效元素个数
boolean isEmpty()检测队列是否为空

注意:Queue是个接口,在实例化时必须实例化LinkedList的对象,因为LinkedList实现了Queue接口。
在这里插入图片描述
上面是Queue接口的一些方法。add方法和offer方法都是用来新增元素的。remove方法和poll方法都是用来弹出元素的。element方法和peek方法都是用来获取队头元素的。那他们有什么区别呢?
在这里插入图片描述

注释翻译:
add方法

如果可以立即插入到此队列中,则在不违反容量限制的情况下插入指定的元素,成功后返回 true,如果当前没有可用空间,则引发 IllegalStateException。
参数:
e – 要添加的元素
返回:
true(由 Collection.add 指定)
抛出:
IllegalStateException – 如果由于容量限制而此时无法添加元素
ClassCastException – 如果指定元素的类阻止将其添加到此队列中
NullPointerException – 如果指定的元素为 null,并且此队列不允许 null 元素
IllegalArgumentException – 如果此元素的某些属性阻止将其添加到此队列中
offer方法
如果可以立即插入到此队列中,则将其指定的元素插入到此队列中,而不会违反容量限制。当使用容量受限的队列时,此方法通常比 add 更可取,后者只能通过引发异常来无法插入元素。
参数:
e – 要添加的元素
返回:
如果元素已添加到此队列中,则为 true,否则为 false
抛出:
ClassCastException – 如果指定元素的类阻止将其添加到此队列中
NullPointerException – 如果指定的元素为 null,并且此队列不允许 null 元素
IllegalArgumentException – 如果此元素的某些属性阻止将其添加到此队列中
在这里插入图片描述

注释翻译:
remove方法

检索和删除此队列的头部。此方法与 poll() 的不同之处仅在于如果此队列为空,它会引发异常。
返回:
此队列的头部
抛出:
NoSuchElementException – 如果此队列为空
poll方法
检索并删除此队列的头部,如果此队列为空,则返回 null。
返回:
此队列的头部,如果此队列为空,则为 null

在这里插入图片描述

注释翻译:
element方法

检索但不删除此队列的头部。此方法与 peek 的唯一区别在于,如果此队列为空,它会引发异常。
返回:
此队列的头部
抛出:
NoSuchElementException – 如果此队列为空
peek方法
检索但不删除此队列的头部,如果此队列为空,则返回 null。
返回:
此队列的头部,如果此队列为空,则为 null

使用代码示例

    public static void main(String[] args) {Queue<Integer> q=new LinkedList<>();q.offer(1);//入队列q.offer(2);q.offer(3);System.out.println(q.poll());//出队列System.out.println(q.poll());System.out.println(q.element());//查看第一个队列元素System.out.println(q.element());System.out.println(q.isEmpty());//队列判空}

8. 模拟队列的实现

队列中既然可以存储元素,那底层肯定要有能够保存元素的空间,通过前面线性表的学习了解到常见的空间类型有两种:顺序结构和链式结构

8.1 链式队列

在这里插入图片描述
我们使用双向链表来实现链式队列。实现代码如下:

public class MyQueue {static class ListNode{//队列节点public ListNode prev;public ListNode next;public int val;public ListNode(int val){this.val=val;this.prev=null;this.next=null;}}public ListNode head;public ListNode last;//入队列public void offer(int val) {ListNode node = new ListNode(val);//创建节点//尾插法入队列if(head==null){head=node;last=node;}else {last.next=node;node.prev=last;last=node;}}//出队列public int poll(){if(head==null){return -1;}//头删法出队列int ret=head.val;if(head.next==null){head=last=null;}else {head=head.next;head.prev=null;}return ret;}//查看队头元素public int peek(){if(head==null){return -1;}//如果队头不为空,返回队头的值return head.val;}//判断队列是否为空public boolean isEmpty(){//如果头节点为null,队列为空return head==null;}
}

8.2 顺序队列

使用顺序表来实现队列,如果不移动元素的位置来进行出队列和入队列就会造成一个问题:假设first为队头(可以出数据的下标),last为队尾(可以存放数据的下标),入队过程中last到顺序表的最后一个位置,而first端元素在出队列,这样就会使队列的前一段空出来了而没有存储数据。示例图如下:
在这里插入图片描述
如果将last重新回到0下标的空间,这样会使队列不连续。因此,我们通过数组来实现环形队列。
在这里插入图片描述
环形队列的连续问题解决了,但是当队尾走到顺序表的尽头,此时我们一直让fist++或者last++可能会造成数组越界,我们可以在每次入队列或者出队列时加一个判断,当first==len或者last==len时让他们的下标设置为0,。我们也可以通过表达式来设置下标,first=(first+1)%len或者last=(last+1)%len,通过这个表达式就不用担心数组越界的问题了。
在这里插入图片描述
考虑完数组越界问题后,我们如何区分队列的空与满?单纯依靠头尾相遇并不能解决这个问题,因为环形链表头尾相遇时可能为空,也可能为满。我们有下面三种解决方案。题目:力扣循环队列。

  1. 使用usedSize,当usedSize==len时就为满。
class MyCircularQueue {public int[] elem;//存放队列元素public int first;//队列头public int last;//队列尾public int usedSize;//元素个数//构造方法public MyCircularQueue(int k) {elem=new int[k];this.usedSize=0;this.first=0;this.last=0;}//入队列 public boolean enQueue(int value) {if(isFull()){//判满,如果队列满了返回falsereturn false;}//元素入队列elem[last]=value;//队尾位置往后移一个last=(last+1)%elem.length;//元素个数加1usedSize++;//成功入队列,返回truereturn true;}//出队列public boolean deQueue() {if(isEmpty()){//判空,如果队列为空返回falsereturn false;}//出队列直接让对头往后移动一个first=(first+1)%elem.length;//元素个数减1usedSize--;//出队列成功,返回truereturn true;}//看队头元素public int Front() {if(isEmpty()){//判空,如果为空返回-1return -1;}//不为空,first下标即为队头元素return elem[first];}//看队尾元素public int Rear() {if(isEmpty()){//判空,如果为空返回-1return -1;}int index;if(last==0) {//如果last为0,队尾元素下标就为elem.length-1index = elem.length-1;}else {//否则,队尾元素下标为last-1index = last-1;}//返回对应下标的元素return elem[index];}//判空public boolean isEmpty() {//如果usedSize为0,队列尾空return usedSize==0;}//判满public boolean isFull() {//如果usedSize等于数组长度队列为满return usedSize==elem.length;}
}
  1. 使用一个boolean类型的标记,。
class MyCircularQueue {public int[] elem;//存放队列元素public int first;//队列头public int last;//队列尾public boolean flag;//标记//构造方法public MyCircularQueue(int k) {elem=new int[k];this.flag=false;//flag为false时,队列不满this.first=0;this.last=0;}//入队列public boolean enQueue(int value) {if(isFull()){//判满,如果队列满了返回falsereturn false;}//元素入队列elem[last]=value;//队尾位置往后移一个last=(last+1)%elem.length;if(last==first){//入队列时,last走完一圈回到first队列就满了flag=true;}//成功入队列,返回truereturn true;}//出队列public boolean deQueue() {if(isEmpty()){//判空,如果队列为空返回falsereturn false;}//出队列直接让对头往后移动一个first=(first+1)%elem.length;flag=false;//出队列时,队列就不满,标志设为false//出队列成功,返回truereturn true;}//看队头元素public int Front() {if(isEmpty()){//判空,如果为空返回-1return -1;}//不为空,first下标即为队头元素return elem[first];}//看队尾元素public int Rear() {if(isEmpty()){//判空,如果为空返回-1return -1;}int index;if(last==0) {//如果last为0,队尾元素下标就为elem.length-1index = elem.length-1;}else {//否则,队尾元素下标为last-1index = last-1;}//返回对应下标的元素return elem[index];}//判空public boolean isEmpty() {//如果last==first且flag为false,队列为空return last==first&&!flag;}//判满public boolean isFull() {//如果队列为满,flag为truereturn flag;}
}
  1. 浪费一个空间,当first+1==last时,为满。
class MyCircularQueue {public int[] elem;//存放队列元素public int first;//队列头public int last;//队列尾//构造方法public MyCircularQueue(int k) {//因为浪费了一个空间,所以为了保证能够存够k个元素就需要开辟k+1个空间elem=new int[k+1];this.first=0;//队头this.last=0;//队尾}//入队列public boolean enQueue(int value) {if(isFull()){//判满,如果队列满了返回falsereturn false;}//元素入队列elem[last]=value;//队尾位置往后移一个last=(last+1)%elem.length;//成功入队列,返回truereturn true;}//出队列public boolean deQueue() {if(isEmpty()){//判空,如果队列为空返回falsereturn false;}//出队列直接让对头往后移动一个first=(first+1)%elem.length;//出队列成功,返回truereturn true;}//看队头元素public int Front() {if(isEmpty()){//判空,如果为空返回-1return -1;}//不为空,first下标即为队头元素return elem[first];}//看队尾元素public int Rear() {if(isEmpty()){//判空,如果为空返回-1return -1;}int index;if(last==0) {//如果last为0,队尾元素下标就为elem.length-1index = elem.length-1;}else {//否则,队尾元素下标为last-1index = last-1;}//返回对应下标的元素return elem[index];}//判空public boolean isEmpty() {//头等于尾时为空return last==first;}public boolean isFull() {//浪费一个元素,尾的下一个为头就视为满return (last+1)%elem.length==first;}
}

9. 双端队列

双端队列(deque)是指允许两端都可以进行入队和出队操作的队列,deque 是 “double ended queue” 的简称。
那就说明元素可以从队头出队和入队,也可以从队尾出队和入队。
在这里插入图片描述
Deque是一个接口,使用时必须创建LinkedList的对象。
在这里插入图片描述
在实际工程中,使用Deque接口是比较多的,栈和队列均可以使用该接口。

//下面这两个类也可以当做链表栈使用,也可以当做队列使用
Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现

下面是Deque的一些方法。
在这里插入图片描述
栈和队列相关练习题链接

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Python编码系列—Python中的安全密码存储与验证:实战指南

&#x1f31f;&#x1f31f; 欢迎来到我的技术小筑&#xff0c;一个专为技术探索者打造的交流空间。在这里&#xff0c;我们不仅分享代码的智慧&#xff0c;还探讨技术的深度与广度。无论您是资深开发者还是技术新手&#xff0c;这里都有一片属于您的天空。让我们在知识的海洋中…

livox MID-360调试(解决ip设置问题)

整体的调试思路参考大疆Livox Mid360 使用指南_mid360中的imu内参-CSDN博客这篇博客。 但是在调试过程中出现了ip地址设置不对导致的报错&#xff1a; 1.livox viewer中看不到点云数据 2.livox SDK2 bind error。 joeyjoey:~/slam/Livox-SDK2/build/samples/livox_lidar_qu…

基于PLC的电热水器的水箱水位控制系统(论文+源码)

1总体方案设计 本设计基于PLC的电热水器的水箱水位控制系统的整体结构如图2.1所示&#xff0c;系统采用S7-1200 PLC为控制器&#xff0c;可以实现电热水器水箱中的水位、水温检测&#xff0c;并且用户可以设定目标水位和水温&#xff0c;在自动模式下&#xff0c;当水位低于低水…

mysql 8.0 的 建表 和八种 建表引擎实例

文章目录 MySQL 8.0 中&#xff0c;主要有以下四种常见的建表引擎一、InnoDB 引擎建表注意点建表知识点 二、MyISAM 引擎建表使用场景 三、Memory 引擎使用场景 四、Archive 引擎五、BLACKHOLE 引擎一、特点二、适用场景三、注意事项 六、MRG_MyISAM 引擎MRG_MyISAM 和 MyISAM …

uniapp组件中的emit声明触发事件

emit解析 在 uniapp 中&#xff0c;emit 主要用于组件间通信&#xff0c;特别是在子组件需要向父组件或者其他组件发送消息的时候。具体用途包括&#xff1a; 子传父数据&#xff1a;子组件通过 $emit 触发一个事件&#xff0c;并携带参数&#xff0c;父组件监听这个事件并对参…

Oracle 网络安全产品安全认证检索

自2023年7月1日起&#xff0c;国家网信办、工业和信息化部、公安部、国家认证认可监督管理委员会统一公布和更新网络关键设备和网络安全专用产品清单。列入《网络关键设备和网络安全专用产品目录》的网络安全专用产品应当按照《信息安全技术网络安全专用产品安全技术要求》等相…

笔记:应用Visual Studio Profiler分析CPU使用情况

一、目的&#xff1a;应用Visual Studio Profiler分析CPU使用情况 使用 Visual Studio Profiler 分析 CPU 使用情况可以帮助你识别性能瓶颈&#xff0c;优化代码&#xff0c;提高应用程序的响应速度。 二、实现 以下是如何使用 Visual Studio Profiler 分析 CPU 使用情况的详…

保存json时,保存成自己喜欢的格式的方法(而不是直接保存成格式化的json文档)

保存json时&#xff0c;不是直接保存成格式化的json文档的格式的方法 前言&#xff0c;博主是如何把格式话的json格式保存成自己喜欢的json格式的保存成格式化的json文档的格式&#xff1a;带缩进格式全部保存成一行每条数据保存成一行&#xff1a; 保存成自己喜欢的格式碎碎念…

Hadoop之HDFS的原理和常用命令及API(java)

1、简介 书接上回&#xff0c;上篇博文中介绍如何安装Hadoop和基本配置&#xff0c;本文介绍Hadoop中分布式文件组件--HDFS&#xff0c;在HDFS中&#xff0c;有namenode、datanode、secondnamenode这三个角色&#xff0c;本文将详细介绍这几个组件是如何进行协作的&#xff0c;…

【数据结构 | 每日一题】图的概念辨析

图的概念辨析 考点分析&#xff1a;我们学习数据结构图的第一小节就是&#xff1a;图的基本概念&#xff0c;我们会发现图的概念非常多且有些概念之间又很像&#xff0c;而对于初学者来说&#xff0c;相比树的概念是不好理解的&#xff0c;很容易搞混&#xff0c;因此做了这么…

传输层(TCP、UDP、RDT详解)

目录 1.无连接传输&#xff1a;UDP UDP&#xff1a;User Datagram Protocol&#xff08;用户数据报协议&#xff09; UDP&#xff1a;校验和 Internet校验和的例子 2.可靠数据传输&#xff08;Rdt&#xff09;的原理 可靠数据传输&#xff1a;问题描述 1.Rdt1.0&#xff…

【hot100篇-python刷题记录】【在排序数组中查找元素的第一个和最后一个位置】

R7-二分查找篇 目录 双指针 二分优化 ps: 思路&#xff1a; 双指针 直接用双指针回缩啊 class Solution:def searchRange(self, nums: List[int], target: int) -> List[int]:ret[-1,-1]left,right0,len(nums)-1while left<len(nums):if nums[left]target:ret[0]…

华为Huawei路由器交换机SSH配置

华为设备的SSH登录配置需要5个步骤&#xff0c;示例如下&#xff1a; 一、配置命令 使能SSH功能 stelnet server enable生成公钥 rsa local-key-pair create 1024配置AAA用户密码及相应授权 aaalocal-user xxx password cipher xxxyyy1234local-user xxx privilege level …

三十二、初识Gin框架

目录 一、搭建web项目 1、引入gin依赖 2、搭建项目结构 二、路由绑定 1、创建路由 解释&#xff1a; 2、创建实例化模块 3、创建具体事项 4、main中添加注册 一、搭建web项目 1、引入gin依赖 在项目路径下&#xff0c;终端中输入 go get -u github.com/gin-gonic/gin…

语音测试(一)视频转音频

视频转音频 下载ffmpeg工具进入bin目录cmd进入控制台输入命令 ffmpeg.exe -i ./视频.mp4 ./音频.wav

C语言试题(含答案解析)

单选 1.下面C程序的运行结果为&#xff08;&#xff09; int main(void) {printf("%d", B < A);return 0; }A.编译错误 B.1 C.0 D.运行错误 A’的ascii码值为65&#xff0c;‘B’的ascii码值为66&#xff0c;‘B’<‘A’是不成立的&#xff0c;返回0&#xf…

什么是W外链?外链的优势有哪些?

一、定义 定义W 外链是一家企业级在线短链接生成工具&#xff0c;免费的微信获客助手&#xff0c;支持批量短链接网址生成等&#xff0c;还支持自定义域名短链接数据统计等。在链接缩短的同时&#xff0c;支持高并发、防劫持&#xff0c;是专业的在线生成短链接工具。 网络营…

PrimeTime low power-多电压设计流程(3)

4.Golden UPF flow Golden UPF flow是维护设计多电压电源意图的可选方法。它在整个综合、物理实现和验证步骤中使用原始的Golden UPF 文件,以及由综合和物理实现工具生成的supplemental UPF 文件。 图 141 比较了传统的 UPF-prime 流程与Golden UPF 流程。 Golden UPF 流程在…

达梦数据库事务管理

目录 一、事务简介 二、事务特性 1.原子性 2.一致性 3.隔离性 4.持久性 三、事务提交 1.自动提交模式 2.手动提交模式 3.隐式提交 四、事务回滚 1.自动回滚 2.手动回滚 3.回滚到保存点 4.语句级回滚 五、事务锁定 1.锁模式 &#xff08;1&#xff09;共享锁 …

【加密社】马后炮视角来看以太坊二层战略

阅读正文前先给大家普及下知识&#xff0c;以下文章中提到的 Blobs指的是&#xff1a;"Blob Carriers" 或 "Calldata Blobs" 这是在以太坊网络中用于携带数据的一种方式&#xff0c;尤其是在涉及Rollup&#xff08;如Optimistic Rollup和ZK-Rollup&#xf…