Java-数据结构-栈和队列-Stack和Queue (o゚▽゚)o

2024-09-08 06:12

本文主要是介绍Java-数据结构-栈和队列-Stack和Queue (o゚▽゚)o,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文本目录:

❄️一、栈(Stack):

    ▶ 1、栈的概念:

  ▶ 2、栈的使用和自实现:

     ☑ 1)、Stack():

      ☑ 2)、push(E e):

     ☑ 3)、empty(): 

       ☑ 4)、peek(E e): 

      ☑ 5)、pop(E e): 

     ☑ 6)、size(E e): 

▶ 3、栈自实现的总代码:

❄️二、队列(Queue):

      ▶ 1、栈的概念:

▶ 2、队列的使用和自实现: 

      ☑ 1)、Queue():

       ☑ 2)、isEmpty():

     ☑ 3)、size():

     ☑ 4)、offer(E e):

     ☑ 5)、peek():

      ☑ 6)、poll():

▶ 3、队列的自实现的总代码:

❄️三、循环队列:

▶ 1、成员变量和初始化:

▶ 2、isEmpty()方法:

▶ 3、enQueue(int value)方法:、

 ▶ 3、isEmpty()方法:

 ▶ 4、deQueue()方法:

  ▶ 5、Front()方法:

  ▶ 6、Rear()方法:

❄️四、双端队列:

 ❄️五、总结:


❄️一、栈(Stack):

    1、栈的概念:

         栈:是一种特殊的线性表,其 只允需在固定的一端进行插入和删除操作

   进行插入和删除的一端叫做栈顶,另一端叫做栈底。并且要遵循 先进后出 的规则

压栈:栈的插入操作叫做压栈,入数据在栈顶。

出栈:栈的删除操作叫做出栈,出数据在栈顶。

我们来看看图片是怎样进行的:


  ▶ 2、栈的使用和自实现:

         我们来自实现一个栈,并且和 Java 自带的栈的方法进行比较,看看效果是否一样:

     ☑ 1)、Stack():

             构造一个空的栈。

这也是对于 栈 的构造方法,我们先来看看Java 中自带的是什么效果并且看看如何使用的:    这就是Java自带的栈的构造方法。

    我们接下来看看我们自己定义的栈是怎样写这个方法的,在写方法之前呢,我们先来把栈的成员变量来实现一下,我们对于栈呢,我们使用数组来存放数据

 我们来看看构造方法如何实现,这是个无参构造方法:

这个呢就是我们的自实现构造方法,我们来看看使用自实现的构造方法的效果:

所以效果是一样的。 


      ☑ 2)、push(E e):

             将 e 这个数据入栈。

 我们同样先来看看Java 中自带的是什么效果并且看看如何使用的:

 这就是 Java 里面自带的入栈操作。

         我们来看看自实现的push,在编写代码之前,我们先来看看 push 的思路是什么:

         我们的 push 呢,就是每次往数组下标指向的那个里面放数据,这个下标呢就是我们的 usedSize 这个下标,之后我们放入元素之后,我们要把 usedSize 这个长度往后加1。

         但是这里插入元素的时候呢,我们要注意,当我们的数组的内存满了的话,我们是不是要2倍扩容,所以我们要注意这一点:

对于 push 方法呢就是这个意思了。 我们来看看代码是如何实现的:

我们来看看使用效果如何:

 我们可以看到结果是一样的对于数据的存放。说明我们对于 push 这个方法是没有问题的。


     ☑ 3)、empty(): 

             判断栈是否为空。

这个方法就非常简单了,我们之间来看看Java 的和自实现的比较是否结果一样:

    当我们一开始创建栈的之后呢,判断栈是否为空的话,肯定是为空的所以返回 true 是正确的。由此可得我们的自定义的 empty() 代码是没有问题的。 


       ☑ 4)、peek(E e): 

              返回栈顶的元素,但是不出栈顶的元素。

我们也是来看看如何实现的: 

     这个代码也是很简单的,我们至于要返回 usedSize-1 的这个下标的元素就可以了,因为我们的usedSize总是比下标长 1 个单位

      但是这里我们也是需要注意的是,我们需要先判断一下,我们的栈是否为空,如果为空,都没有元素,所以返回不了元素。这也是 为什么我要先写 empty 这个方法的原因

    我们先来看代码,之后再看看Java中的和自实现的有没有区别:

运行的比较: 


      ☑ 5)、pop(E e): 

                  出栈顶的元素,并且把栈顶的元素删除。

      这个呢,我们先把栈顶的元素打印出来,之后呢我们把 usedSize 自减一次,使得我们访问不到删除的元素,这个比较简单,我们直接来看看代码:

我们来看看实现代码的比较:      我们可以看到我们最先访问的 23 这个栈顶,这个方法是pop,所以会把栈顶元素删除,之后我们再用peek 方法访问的是12,所以呢这个删除方法 peek 没有问题。


     ☑ 6)、size(E e): 

                返回栈的长度。

 这个方法是非常简单的,我们直接返回数组的有效的数组长度。我们直接看代码的实现吧:


▶ 3、栈自实现的总代码:

 OK,我们呢对于栈的方法的实现现在常用的都自实现完事了,我们现在来看看总代码:

public class MyStack {public int[] elem;//存放栈的数据public int usedSize;//我们数组的有效长度public MyStack() {this.elem = new int[10];}private boolean isFull() {return usedSize == elem.length;}public void push(int e) {if (isFull()) {//二倍扩容this.elem = Arrays.copyOf(elem,2*elem.length);}//这是在放完元素后再自加elem[usedSize++] = e;}public boolean empty() {return usedSize == 0;}public int peek() {if (empty()) {System.out.println("栈为空没有元素");return -1;}return elem[usedSize - 1];}public int pop() {int e = peek();usedSize--;return e;}public int size() {return usedSize;}
}

   OK,我们对于栈的实现就已经完事了,我们开看看一道关于栈的选择题来看看吧: 

练习:

     我们来看看这道题选什么? 这道题呢,我们正确的呢是选择 C 因为C中呢我们出 3 后栈里的元素为2,1 从栈顶到栈底,所以我们不可能出1,在不先出2的情况下,所以C 是错误的。

   你是否选择正确了呢?


❄️二、队列(Queue):

    在了解队列之前呢,我们请出我们的那个数据结构的那个表单:

       我们要学习的 Queue 和我们之后要了解的 Deque 我们之前学习过的 LinkedList 这个类中都将它们实现了,所以呢我们的 LinkedList 类呢有 Queue 和 Deque 的性质。所以呢,LinkedList可以使链表、可以是队列(Queue)、可以是双端队列(Deque)

      ▶ 1、栈的概念:

       队列:是一种只允许一端进行插入元素,在另一端进行删除元素的特殊的线性表。

       队列具有 先进先出 的性质:进行插入的一端叫做队尾,进行删除的一端叫做队头。也就是队尾进,队头出。

       队列呢就相当于是我们 排队打饭 的例子,我们先来打饭的先走,后打饭的后走。

 我们来看看流程的表:

相当于这样:


▶ 2、队列的使用和自实现: 

      ☑ 1)、Queue():

      这里我们创建队列的时候要注意了,我们的 队列只是一个接口,不是类,所以不能创建对象,所以我们需要使用 LinkedList 类来进行创建,进行向上转型

我们来看看这个队列要如何创建:

   这个就是用 LinkedList 来进行来创建 队列 的方法。


        在我们自实现方法之前呢,我们来想一下,我们的队列使用什么结构来进行存储元素呢?

        我们在之前呢,我们了解到了 顺序存储 和 链式存储 两种方式,对于我们队列呢我们使用   链式存储 的方式来进行存储元素,但是我们 链式存储 有 单链表 和 双链表 两种方式,我们呢最好使用 双链表 的形式,这样呢方便我们 存储和删除,而且我们的队列要有头和尾,所以双链表更加的合适。这样呢我们了解队列怎样存储之后,我们来看看自实现队列:


       ☑ 2)、isEmpty():

               判断队列是否为空。

     这个方法是非常简单的,我们只需要判断 队头 是不是空就可以了或者我们判断一下有效长度是不是 0 也是可以判断的,因为我们每次出元素都在队头,当我们的头为空说明没有元素了。我们来看看代码:

  这个呢,我们就不进行演示了,我们直接继续往下看: 


     ☑ 3)、size():

           返回队列的长度。

    我们再来看一个简单的代码,这个代码就非常简单了,我们不是定义了一个 usedSize 这个成员变量了吗,这个就是我们队列的有效长度,所以我们直接返回这个 usedSize 这个成员变量就可以了,我们来看看代码的实现:

是不是很简单呢,所以我们这个也不进行代码的演示了,我们还是继续往下看: 


     ☑ 4)、offer(E e):

           入队列操作。

      对于入队的之前呢,我们要先进行对队列的判断,如果我们的队列是空的话,我们要把我们的要入队的节点newNode,我们要执行 firast = last = newNode 的操作

       第一步,当我们的队列不为空的时候呢,我们要把 last.next 指向 newNode 这个节点。

       第二步,我们把新的节点 newNode.prev 指向我们的last这个节点,

       第三步,把 last 往后移一位。

这个呢,就是我们入队的操作思路啦,之后我们,来看看代码是如何实现的: 

     这个呢就是我们的入队操作了,我们来看看 Java 中的队列和自实现的队列的 入队 操作有没有不同的。 

我们可以看到,我们的自实现是没有问题的。Ok,我们来看下一个 队列 的操作:


     ☑ 5)、peek():

          获得队头的元素

   对于这个方法呢,是非常的简单的,我们想要队头的元素的话,我们只需要返回 first.val 这个数据就可以了:

比如这个呢,我们的队头元素就是 first.val 这个元素 ,所以我们来看看代码:

看一下运行的结果怎么样: 

OK,我们可以看到这个方法是没有问题的,我们接下来看看 队列 的最后一个常用的方法:


      ☑ 6)、poll():

            出队列操作。

       我们对于出队列之前呢,我们要先把队列判断一下是否为空,之后我们才能进行出队操作。 

       对于出队操作呢,我们是出队头的元素,我们呢要先把队头元素出出来,之后我们在把 first 往后移动一位,是我们出的那个元素,在队列中删除。但是呢,如果我们的 first 不是空的话,我们呢要把 first.prev 赋值为null,因为我们要把前一个节点删除,所以呢,我们要置空

       我们来看看方法的思路:

了解思路之后呢,我们来看看代码如何编写的:

 

 我们来看看代码有没有问题:

      我们可以看到当我们的 poll 执行之后呢,我们的 peek 的元素就变了,说明我们已经出队了,所以没有问题。


▶ 3、队列的自实现的总代码:

public class MyQueue {static class ListNode {public int val;public ListNode prev;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode first;//队头public ListNode last;//队尾public int usedSize;//长度public boolean isEmpty() {return first == null;//return usedSize == 0;}public int size() {return usedSize;}public void offer(int val) {ListNode newNode = new ListNode(val);if (isEmpty()) {first = last = newNode;}else {last.next = newNode;newNode.prev = last;last = last.next;}usedSize++;}public int poll() {if (isEmpty()) {return -1;}int val = first.val;first = first.next;if (first != null) {first.prev = null;}usedSize--;return val;}public int peek() {if (isEmpty()) {return -1;}return first.val;}
}

       我们的队列呢就到这里就结束了,接下来我们来看一个特殊的队列——循环队列。 


❄️三、循环队列:

 我们呢,先来了解一下循环队列长什么样的,是怎样进行循环的,我们来看看循环队列的形状:

 

    这个呢就是我们的循环队列了,它就像一个轮子一样,是一个环状的。就相当于我们把数组给卷起来似得。

     当这个队列是空的时候呢,我们的 front 和 rear 是在同一个位置,就是相等。

那么我们接下来看看这个的存储过程,并且当什么时候呢我们才能知道我们的空间是满的呢?

我们一个一个来解决:

          这样存放元素呢,我们满的话呢·,front 和 rear 是在一个位置上,但是我们在一个位置上的时候呢,我们是用来判断是否是空的情况下,所以呢,判满是不能这样判断的,那么我们用什么办法呢?我们呢,有三种方法来判断循环队列是否是满的

 1、定义size来判断

               当我们的队列的长度和size的长度相等的时候呢,我们就是满的。

 2、添加标记,用boolean来判断

              每当我们放元素的时候呢,我们把那个位置标记为 true 没有元素为 false,来判断是否满

 3、保留一个位置,浪费一个空间来进行判断

             就是当 rear 的下一个位置为 front 的时候呢,我们就是满的。比如这样:

 我们呢要如何才能判断 rear 的下一个是 front 呢? 是不是想到的是 rear + 1 =  front 就可以了呢?

    这个呢还是有点小瑕疵的,当我们的 rear 是 0 的时候我们的 front 为 1 的时候这种的是可以判断的,像这样:

   但是呢当我们的 rear 为 7 ,front 为 0 的时候就不对了,rear + 1 = 8 ≠ front ,那么我们要如何才能判断呢,我们呢这时候就有了一个公式:

              \left (rear + 1 \right )\varnothing len

比如我们 7 和 0 就是这样:(7 + 1) % 8 = 0

这个队列呢,也是一道题,我们来看链接

        循环队列


▶ 1、成员变量和初始化:

正确的代码: 


▶ 2、isEmpty()方法:

             判断是否是满的

 这里我们直接用公式:


▶ 3、enQueue(int value)方法:、

          入队操作

   这里呢,我们就是直接往 rear 下标进行放入元素,之后 rear 进行增加,但是这里我们不能使用rear++ 来进行增加,因为当我们的 rear 为7时候呢,不能++,那样就为8了,所以这里我们也要用公式来写


 ▶ 3、isEmpty()方法:

         判断队列是否为空

 这个比较简单,我们直接判断 rear 是否等于 front 就可以了。


 ▶ 4、deQueue()方法:

       出队操作

       对于这个方法,我们只需要把 front 这个下标往后走就可以了虽然我们没有删除元素,但是当我们再次在那个位置添加元素的时候,会把原先的数据覆盖掉但是这里我们的 front 的移动也需要使用公式来移动。来看代码:


  ▶ 5、Front()方法:

     得到队头元素

这个呢,我们直接返回 front 下标的元素即可 。


  ▶ 6、Rear()方法:

      得到队尾元素。

    这个方法呢,我们在对于队尾的位置判断上要麻烦一些,当我们 rear 在0下标的时候,队尾下标为7,但是呢,我们在 rear -1 的时候,和结果不一致,这里呢我们要判断,当 rear=0 的时候,我们的队尾下标为 elem.length- 1,其余时为 rear-1,我们来看代码:


我们的循环队列就到这里就结束了,我们再来看一种特殊的队列,叫——双端队列(Deque)

❄️四、双端队列:

    这个队列呢,我们不进行详细的讲解,我们了解一下其工作原理的图和其构造方法即可。和我们学习的队列差不多,只是增加了 头尾都可以进出 :

 之后我们来看一下其接口是实现:


 ❄️五、总结:

     OK,这次的关于呢 线性表中的 栈和队列 就都介绍完毕了,下次呢我们来练习一下它们的习题,这次就到这里就结束了,让我们期待下次的分享吧!!!拜拜~~~

这篇关于Java-数据结构-栈和队列-Stack和Queue (o゚▽゚)o的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1147343

相关文章

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时,有没有考虑过 JVM 是如何把静态的字节码(byte code)转化为运行时对象的呢,这个问题看似简单,但清楚的同学相信也不会太多,这篇文章首先介绍 JVM 类初始化的机制,然后给出几个易出错的实例来分析,帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段,分别是:loading 、Linking、initialization

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权,允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true (Spring security默认会带有ROLE_前缀),去

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程,特意画了如下的类图,包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口,接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类,它们之间的依赖,构建起了整个框架。想要理解整个架构,最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文(security context)的信息。当前操作的用户是谁,该用户是否已经被认证,他拥有哪些角色权限…这些都被保

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来,一站式有声阅读平台听书系统 🌟&nbsp;开篇:遇见未来,从“智听”开始 在这个快节奏的时代,你是否渴望在忙碌的间隙,找到一片属于自己的宁静角落?是否梦想着能随时随地,沉浸在知识的海洋,或是故事的奇幻世界里?今天,就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统,它正悄悄改变着我们的阅读方式,让未来触手可及! 📚&nbsp;第一站:海量资源,应有尽有 走进“智听