开发者社区> IT辰柒_Java> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

【数据结构与算法】栈的深入学习(上)

简介: 【数据结构与算法】栈的深入学习(上)
+关注继续查看

✨hello,进来的小伙伴们,你们好耶!✨

🍅🍅系列专栏:【数据结构与算法】

✈️✈️本篇内容:  栈的认识,栈的使用,栈的模拟实现!

⛵⛵作者简介:一名双非本科大三在读的科班Java编程小白,道阻且长,你我同行!

一、栈(Stack)

一、栈的概念

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

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

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


image.jpeg

二、栈的使用

881ffd248fcc4638901eba5f6eb5ea74.png

代码演示:

入栈push()

   public class MyStack {

       public static void main(String[] args) {

           Stack<Integer> s1 = new Stack<>();

           s1.push(1);

           s1.push(2);

           s1.push(3);

           s1.push(4);

           s1.push(5);

           System.out.println(s1);

       }

   }

运行结果:  

20681ce674f849a49401839e66a9cadb.png

 出栈pop(),这里我们出栈两个元素,那么剩下的结果应该是1 2 3

   public class MyStack {

       public static void main(String[] args) {

           Stack<Integer> s1 = new Stack<>();

           s1.push(1);

           s1.push(2);

           s1.push(3);

           s1.push(4);

           s1.push(5);

           System.out.println(s1);

           s1.pop();

           s1.pop();

           System.out.println(s1);

       }

   }

运行结果:

2bee1f5356344dffb393c5f5e6d30fce.png

 获取栈顶元素peek():

   public class MyStack {

       public static void main(String[] args) {

           Stack<Integer> s1 = new Stack<>();

           s1.push(1);

           s1.push(2);

           s1.push(3);

           s1.push(4);

           s1.push(5);

           System.out.println(s1.peek());

       }

   }

运行结果:

79a9e8015b9540848633d0f96b029bfe.png

 获取栈中有效元素的个数

   public class MyStack {

       public static void main(String[] args) {

           Stack<Integer> s1 = new Stack<>();

           s1.push(1);

           s1.push(2);

           s1.push(3);

           s1.push(4);

           s1.push(5);

           System.out.println(s1.size());

       }

   }

运行结果:

601eacca683d460d93fa193f8268141c.png

 判断栈是否为空

   public class MyStack {

       public static void main(String[] args) {

           Stack<Integer> s1 = new Stack<>();

           s1.push(1);

           s1.push(2);

           s1.push(3);

           s1.push(4);

           s1.push(5);

           System.out.println(s1.empty());

       }

   }

运行结果:

b0e72e2cbf28452fbd198057d8f214f6.png

三、栈的应用场景

1. 若进栈序列为 1,2,3,4 ,进栈过程中可以出栈,则下列不可能的一个出栈序列是(C)

A: 1,4,3,2  B: 2,3,4,1  C: 3,1,4,2  D: 3,4,2,1

问题分析:类似于这种栈的选择题,如果元素较少,我们直接心算就可以,元素较多的话我们可以画图来解决,本题c选项,先出的是3,那么就是1,2,3进栈,然后3出栈,第二个出栈选项给的是1,我们知道1是第一个进栈的,那么想出1,2必须先出,所以C选项错误!

 

2.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈,然后再依次出栈,则元素出栈的顺序是( B)。

A: 12345ABCDE  B: EDCBA54321  C: ABCDE12345  D: 54321EDCBA

问题分析:简单明了,栈的结构先进后出,直接选B。

四、栈的模拟实现

   import java.util.Arrays;

   import java.util.Stack;

     

   /**

    * 栈的模拟实现

    */

     

   public class MyStack {

     

       public int[] elem;

       public int usedSize;

       public static final int DEFAULT_SIZE = 10;

     

       public MyStack() {

           this.elem = new int[DEFAULT_SIZE];

       }

     

     

       /**

        * 压栈

        */

     

       public int push(int val) {

           if(isFull()) {

               elem = Arrays.copyOf(elem,2*elem.length);

           }

           this.elem[usedSize] = val;

           usedSize++;

           return val;

       }

     

     

       public boolean isFull() {

           return usedSize == elem.length;

       }

     

     

       public int pop() {

           if(empty()) {

               throw new MyEmptyStackException("栈为空!");

           }

           /*int ret = elem[usedSize-1];

           usedSize--;

           return ret;*/

           return elem[--usedSize];

       }

     

     

       public boolean empty() {

           return usedSize == 0;

       }

     

     

       public int peek() {

           if(empty()) {

               throw new MyEmptyStackException("栈为空!");

           }

           return elem[usedSize-1];

       }

     

   }

🍎🍎栈的模拟实现我们使用的是数组来实现的,代码也非常的简单明了,易于看懂,博主准备下一篇博客更新栈的几个经典面试题,慢慢干货,期待你的一键三连喔!🤟🤟

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
数据结构和算法-栈|学习笔记
快速学习数据结构和算法-栈
9 0
数据结构与算法
本文主要是对数据结构与算法的前四章进行简单的介绍,主要介绍的是线性表、栈、队列、递归的相关知识 。
88 0
数据结构与算法(一)
近日受北京疫情影响居家办公,给自己充充电,刷一遍 邓俊辉老先生的算法与数据结构教程,纯属学习笔记,有总结不当的地方欢迎指正~
33 0
数据结构与算法(4)栈
由于栈比较简单,也很容易理解,学过的人都知道一句话就可以描述栈的特性:后进先出。所以这篇文章主要是写如何使用代码来描述栈,当然也是让大家很容易理解的语言。还是先给出这篇文章的大致脉络。 首先,对栈有一个基本认识 接下来,用代码实现栈,以及栈的常用操作 然后,介绍栈的几种应用场景 最后,小结一下。
32 0
有必要学习数据结构和算法吗?
有必要学习数据结构和算法吗?
62 0
数据结构与算法-链表(上)
数据结构与算法-链表
28 0
数据结构与算法学习笔记
数据结构与算法学习笔记
36 0
算法学习 | 数据结构(一)
线性表是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号,其具体含义在不同的情况下一般不同。
1410 0
+关注
IT辰柒_Java
攀登者!
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载