出门一笑， “栈” 落江横 (Java篇)

news/2024/5/19 18:42:40

本篇会加入个人的所谓‘鱼式疯言’

❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言
而是理解过并总结出来通俗易懂的大白话,
小编会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的.
🤭🤭🤭可能说的不是那么严谨.但小编初心是能让更多人能接受我们这个概念！！！

前言

说完数据结构的链表小专题，小编今天带来了我们这节非常有意思的栈一种非常有意思的数据结构，实不相蛮，栈也是我们线性表中的一种结构哦 💥 💥 💥

一. 栈的初识

1. 栈的简介

栈：一种特殊的线性表，其 只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守 后进先出 LIFO（Last In First Out）的原则。

而利用我们的栈对数据操作时

我们主要有两种方式

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。

在这里插入图片描述

鱼式疯言

我们可以贴近生活去理解我们的栈

压入子弹和出子弹的时候，就是栈的出栈和入栈
在这里插入图片描述
羽毛球入球桶和出球桶，就是栈的出栈和入栈

二. Stack 类

1.Stack 的简介

在我们的Java的数据结构的集合类中，内部就提供了那么一种栈的类

在这里插入图片描述

我们就成为 Stack 类，而这个类就实现了我们 栈的所需要的功能

2. Stack 的使用

<1>. 入栈

class Test {public static void main(String[] args) {Stack<Integer> s=new Stack<>();s.push(1);s.push(2);s.push(3);}
}

在这里插入图片描述

无论怎么存放，都是先存放的放栈底，后存放的放栈顶

<2>. 出栈

class Test {public static void main(String[] args) {Stack<Integer> s=new Stack<>();// 先在栈顶入栈s.push(1);s.push(2);s.push(3);// 然后在栈底出栈System.out.println(s.pop());System.out.println(s.pop());}
}

在这里插入图片描述

出栈也如此，放在 栈顶的元素先出，栈底的元素后出 ，也就意味着 先入后出

<3>. 查栈

class Test {public static void main(String[] args) {Stack<Integer> s=new Stack<>();// 先在栈顶入栈s.push(1);s.push(2);s.push(3);// 然后在栈底出栈System.out.println(s.pop());  // 3System.out.println(s.pop());  // 2// 查看当前栈顶元素System.out.println(s.peek());  // 1System.out.println(s.peek());  // 1}
}

在这里插入图片描述

最终呈现出来的效果是一直打印栈顶的元素

故查栈时，只能查看当前 栈顶元素

<4>栈的大小以及是否为空

栈的大小

class Test {public static void main(String[] args) {Stack<Integer> s=new Stack<>();// 先在栈顶入栈s.push(1);s.push(2);s.push(3);System.out.println("=========== 栈的大小 ======");System.out.println(s.size());}
}

在这里插入图片描述

根据返回值的数字来判断栈中大小

栈是否为空

class Test {public static void main(String[] args) {Stack<Integer> s=new Stack<>();// 先在栈顶入栈s.push(1);s.push(2);s.push(3);System.out.println("=========== 栈的大小 ======");System.out.println(s.size());System.out.println("========栈是否为空=========");if (s.empty()) {System.out.println("该栈为空！");} else {System.out.println("该栈不为空!");}}
}

在这里插入图片描述

根据返回的布尔类型来判断栈是否为空

鱼式疯言

返回 true 说明为空
返回 false 说明不为空

以上是我们栈的主要功能

可能有一些碎片化的功能小编可能未提及，小编个人认为不是很重要，小伙伴们只要掌握以上Stack 的 4 种功能 即可

竟然是程序员，肯定少不了实操的嘛，下面就让小编带着友友们来实现我们的栈吧 💖 💖 💖

三. 栈的实现

在这里插入图片描述

1. 构建栈的底层

说到栈的先入后出的特点，我们不得不想起我们之前学过的顺序表和链表

小伙伴们是不是觉得很相似呢，入栈不就相当于尾插么，出栈不就相当于尾删

竟然两者都能实现，那么我们该选择顺序表还是链表好呢，小编认为自然是选择顺序表更优一点

这是为啥呢 ?

因为啊我们的顺序表本质上是数组

而我们的数组本身就是一块连续的空间，所以不管我们尾插还是尾删数据时，自然选择我们的顺序表更恰当咯 😁 😁 😁

public class MyStack implements IStack{// 定义一个栈public int []elem;public MyStack() {this.usesize = 0;this.elem =new int[SIZEMAX];}// 现有栈元素大小public  int usesize;
}

2. 入栈

请添加图片描述

// 入栈@Overridepublic void push(int val) {if (isFull()) {this.elem= Arrays.copyOf(elem,2*elem.length);}elem[usesize]=val;usesize++;}// 检查栈是否满private boolean isFull() {return usesize==size();}

在这里插入图片描述

入栈是容易，但小伙伴们可不要掉以轻心哦，当我们入栈时，一定要注意数组的空间是否足够

如果不够一定要及时的 扩容

具体扩容细节可以参考的我们 Java篇的顺序表哦

顺序表详解链接

3. 出栈

请添加图片描述

// 去除栈顶元素@Overridepublic int pop() {if (isEmpty()) {return -1;}int ret=elem[usesize-1];
//         elem[usesize]=null;usesize--;return ret;}//检查是否空@Overridepublic boolean isEmpty() {return usesize==0;}

在这里插入图片描述

首先我们得判断该栈元素是否为 空 ，这时我们就可以用到我们自己写的 isEmpty（）方法啦。如果成立就返回 -1

然后出栈就没有我们入栈那么细节的需要考虑增容的情况啦，我们只需要把有效元素大小减少一位即可 💖 💖 💖

鱼式疯言

但要注意一点哦，如果该数据类型是引用数据类型就需要置空

// elem[usesize]=null;

4. 查栈


// 喵一眼栈顶元素
@Override
public int peek() {if (isEmpty()) {return -1;}return elem[usesize-1];
}//检查是否空@Overridepublic boolean isEmpty() {return usesize==0;}

在这里插入图片描述

在 peek（） 方法中，我们只需要返回当前栈顶的元素即可。

5.栈的大小以及是否为空

//检查是否空
@Override
public boolean isEmpty() {return usesize==0;
}// 返回栈的大小
@Override
public int size() {return usesize;
}

在这里插入图片描述

检查栈是否为空只需要是否等于 0 即可

6. 程序逻辑与接口代码展示

package stack;public interface IStack {int SIZEMAX=10;// 入栈void push(int val);// 出栈int pop();// 喵栈int peek();// 是否空boolean isEmpty();// 栈的大小int size();}


package stack;public class TestStack {public static void main(String[] args) {MyStack ms=new MyStack();// 入栈ms.push(1);ms.push(2);ms.push(3);ms.push(4);ms.push(5);System.out.println("======出栈元素======");// 出栈// 先出栈顶System.out.println(ms.pop());  // 5System.out.println(ms.pop());  // 4System.out.println(ms.pop()); // 3System.out.println("=======查栈元素==========");// 看栈顶System.out.println(ms.peek());System.out.println(ms.peek());System.out.println("========查栈大小========");// 栈的大小System.out.println(ms.size);System.out.println("=======查栈是否为空=======");if (ms.isEmpty()) {System.out.println("MyStack 为空！");} else {System.out.println("MyStack 不为空！");}}
}