`

栈和Java基础类的Stack类的源码实现,缺陷以及如何实现自己的Stack类

阅读更多

栈是重要的数据结构,从数据结构角度看,栈也是线性表,其特殊性在栈的基本操作是线性表的子集。Stack作为最基本的数据结构,在JDK代码中,也有它的实现,java.util.Stack类是继承了Vector类,来实现了栈的基本功能。

 

1.栈的基本原理

 

栈(Stack)是限定仅在表尾进行插入或者删除操作的线性表。因此,对于栈来说,表尾端有特殊含义,成为栈顶,表头称之为栈底。

 

由下图可以看出,栈的最基本的特征是LIFO(Last In First Out),因此栈又被称为后进先出 的线性表。

 

2.栈的基本操作

 

InitStack(&S)--------------构造一个空栈

IsEmpty:判断栈是否为空

ClearStack:清空栈

StackLength:栈S的元素个数,即栈的长度

GetTop:获取栈顶元素

Push:插入新的元素

Pop:删除栈顶元素

 

3.java.util.Stack源码解析

 

1)数据结构:利用Vector(动态数组)完成后进先出的操作

2)基本方法:

 

     //初始化一个长度为10 的数组

     构造器      public Stack():

 

    //放入新元素到栈顶

     public E push(E item){

           //按序更新数组元素(计数器判断最后更新数组元素的索引)

           addElement(item);

           return item;

    }

 

    /**

   *1.如果由于新增的元素导致数组的长度不够,则把原来的数组尺寸翻倍,并拷贝老数组元素到新的数组

   *2.

   *

   *

   */

   public synchronized void addElement(E obj) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = obj;
    }

 

 

//pop栈顶元素

 public synchronized E pop() {
    E    obj;
    int    len = size();

    obj = peek();
    removeElementAt(len - 1);

    return obj;
    }

 

4.java.util.stack的缺点

上述源码分析我们知道,Stack利用Vector动态数组实现了后进先出的栈的基本功能,但是数组有下列缺陷:

 

1)当数组默认的容量发生改变时,push的性能会有较大降低


5.实现自己的Stack类

 

数组的缺点是,当数组长度发生变化时,原有的元素需要经过copy到新的数组中,这样性能有较大的损耗,而链表最大的优点是插入和删除的性能非常好,Java提供了现成的双向链表类java.util.LinkedList,通过它可以快速编写自己的Stack程序,源码如下:

 

public class Stack<E>{
    LinkedList<E> list;
   
    public Stack(){
        list = new LinkedList();
    }
   
    public E pop(){
        return list.removeLast();
    }
   
    public void push(E o){
        list.add(o);
    }
   
    public E getTop(){
        return list.getLast();
    }
   
    public boolean isEmpty(){
        return list.size()==0;
    }
   
    public int size(){
        return list.size();
    }
   
    public static void main(String[] args) {
        Stack stack = new Stack();
        stack.push("bottom");
        stack.push("middle");
        stack.push("top");
        System.out.println(stack.isEmpty());
        System.out.println(stack.getTop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.isEmpty());
    }
   
}

 

 

 

 

  • 大小: 35.6 KB
2
0
分享到:
评论

相关推荐

    BS23-287基于Python的期货程序化交易系统的设计与实现-206jhypi.zip

    本系统的开发与设计是基于vue为前端页面核心框架为django/flask,技术方面主要采用了Html、Js、CSS3、python、Mysql。 本课题使用Python语言进行开发。代码层面的操作主要在PyCharm中进行,将系统所使用到的表以及数据存储到MySQL数据库中,方便对数据进行操作本课题基于WEB的开发平台 ②前端开发选择:Vue。 ②后端开发选择:python、django/flask。 ③数据库选择:MySQL。 ④开发工具选择:pycharm、Navicat for MySQL。 包含了我的信息、用户管理、期货公司管理、开户信息管理、充值信息管理、期货期货信息管理、期货投资管理、取消投资管理、投资风险管理、意见反馈、系统管理

    springboot052基于Springboot+Vue旅游管理系统毕业源码案例设计.zip

    springboot052基于Springboot+Vue旅游管理系统毕业源码案例设计 1、资源项目源码均已通过严格测试验证,保证能够正常运行; 2、项目问题、技术讨论,可以给博主私信或留言,博主看到后会第一时间与您进行沟通; 3、本项目比较适合计算机领域相关的毕业设计课题、课程作业等使用,尤其对于人工智能、计算机科学与技术等相关专业,更为适合; 4、下载使用后,可先查看README.md或论文文件(如有),本项目仅用作交流学习参考,请切勿用于商业用途。 5、资源来自互联网采集,如有侵权,私聊博主删除。 6、可私信博主看论文后选择购买源代码。 1、资源项目源码均已通过严格测试验证,保证能够正常运行; 2、项目问题、技术讨论,可以给博主私信或留言,博主看到后会第一时间与您进行沟通; 3、本项目比较适合计算机领域相关的毕业设计课题、课程作业等使用,尤其对于人工智能、计算机科学与技术等相关专业,更为适合; 4、下载使用后,可先查看README.md或论文文件(如有),本项目仅用作交流学习参考,请切勿用于商业用途。 5、资源来自互联网采集,如有侵权,私聊博主删除。 6、可私信博主看论文后选择购买源代码。 1、资源项目源码均已通过严格测试验证,保证能够正常运行; 2、项目问题、技术讨论,可以给博主私信或留言,博主看到后会第一时间与您进行沟通; 3、本项目比较适合计算机领域相关的毕业设计课题、课程作业等使用,尤其对于人工智能、计算机科学与技术等相关专业,更为适合; 4、下载使用后,可先查看README.md或论文文件(如有),本项目仅用作交流学习参考,请切勿用于商业用途。 5、资源来自互联网采集,如有侵权,私聊博主删除。 6、可私信博主看论文后选择购买源代码。

    Matlab实现牛顿拉夫逊优化算法NRBO-Kmean-Transformer-BiLSTM负荷预测算法研究.rar

    1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手

    【创新未发表】Matlab实现樽海鞘优化算法SSA-GRU实现风电数据预测算法研究.rar

    1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手

    基于向量加权平均算法INFO-Kmean-Transformer-GRU实现数据回归预测算法研究Matlab代码.rar

    1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手

    【创新未发表】Matlab实现秃鹰优化算法BES-GRU实现风电数据预测算法研究.rar

    1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手

    【创新未发表】Matlab实现雪融优化算法SAO-Kmean-Transformer-BiLSTM负荷预测算法研究.rar

    1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手

    计算机图形学之动画和模拟算法:Keyframe Animation:碰撞检测与响应.docx

    计算机图形学之动画和模拟算法:Keyframe Animation:碰撞检测与响应.docx

    【上交所-2024研报】京城股份2024年三季度报告.pdf

    行业研究报告、行业调查报告、研报

    android文心一言的一个demo

    调用文心一言api的一个尝试

    hertzbeat.tar

    hertzbeat的docker镜像文件

    【创新未发表】Matlab实现灰狼优化算法GWO-GRU实现风电数据预测算法研究.rar

    1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手

    基于减法平均优化算法SABO-Kmean-Transformer-GRU实现数据回归预测算法研究Matlab代码.rar

    1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手

    【java毕业设计】大学生就业服务平台源码(springboot+vue+mysql+说明文档).zip

    项目经过测试均可完美运行! 环境说明: 开发语言:java jdk:jdk1.8 数据库:mysql 5.7+ 数据库工具:Navicat11+ 管理工具:maven 开发工具:idea/eclipse

    【光伏预测】基于北方苍鹰优化算法NGO优化高斯过程回归GPR实现光伏多输入单输出预测附Matlab代码.rar

    1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手

    【创新未发表】Matlab实现灰狼优化算法GWO-Kmean-Transformer-BiLSTM组合状态识别算法研究.rar

    1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手

    计算机图形学之动画和模拟算法:Procedural Animation:物理基础:力与运动.docx

    计算机图形学之动画和模拟算法:Procedural Animation:物理基础:力与运动.docx

    【创新未发表】Matlab实现鱼鹰优化算法OOA-GRU实现风电数据预测算法研究.rar

    1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手

    【创新未发表】Matlab实现混沌博弈优化算法CGO-GRU实现风电数据预测算法研究.rar

    1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。 替换数据可以直接使用,注释清楚,适合新手

    2112312312321321

    2112312312321321

Global site tag (gtag.js) - Google Analytics