数据结构-------栈(数组、链表实现)

标签: 数据结构  java    链表  算法  

  1. 栈是一种先进后出的数据结构,是一种只能在一端进行插入和删除操作的线性表。

  2. 它按照先进后出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。

  3. 数据进入到栈的动作为压栈(入栈),数据从栈中出去的动作为出栈。

  4. 原理图:
    在这里插入图片描述

  5. 栈是一种逻辑结构,具体存储实现是考虑物理存储结构,即顺序存储结构(数组)和链式存储结构(链表)。

  6. 链表实现栈:

    import java.util.Iterator;
    
    /**
     * @author JIN
     * @description 栈
     **/
    public class Stack<T> implements Iterable<T>{
        //头节点
        private Node head;
        //栈内个数
        private int N;
    
        public Stack(){
            head = new Node(null,null);
            N = 0;
        }
    
        //判断是否为空
        public boolean isEmpty(){
            return N == 0;
        }
    
        //返回栈中个数
        public int size(){
            return N;
        }
    
        //入栈
        public void push(T t){
            //栈后进的元素是在前面,因此使用头插法。
            head.next = new Node(t,head.next);
            N++;
        }
        //出栈
        public T pop(){
            Node node = head.next;
            //安全性校验
            // 若没有这个校验,栈中若没有元素,即node == null
            //此时node.next将是空指针异常
            if(node == null){
                return null;
            }
            //把第一个元素取出,并让头节点指向第二个节点。
            head.next = node.next;
            N--;
            return node.data;
        }
    
        class Node{
            private T data;
            private Node next;
    
            public Node(T data, Node next){
                this.data = data;
                this.next = next;
            }
        }
    
        @Override
        public Iterator<T> iterator() {
            return new Iterator<T>() {
                private Node node = head;
    
                @Override
                public boolean hasNext() {
                    return node.next != null;
                }
    
                @Override
                public T next() {
                    node = node.next;
                    return node.data;
                }
            };
        }
    }
    
    
  7. 数组实现栈:

    import java.util.Iterator;
    
    /**
     * @author JIN
     * @description 栈
     **/
    
    public class Stack2<T> implements Iterable<T>{
        
        //数组用于模拟栈
        private T[] data;
        //实际存储的个数
        private int N;
        //数组的容量
        private int size;
    
        //默认构造函数,初始化数组大小为4
        public Stack2(){
            this(4);
        }
        //构造函数,可以设置数组大小
        public Stack2(int size){
            //因为是泛型,不能 new T[size];
            //因此只能先new Object再强转
            this.data = (T[])new Object[size];
            this.size = size;
            N = 0;
        }
        //判断是否为空
        public boolean isEmpty(){
            return N == 0;
        }
        //返回存储的个数
        public int size(){
            return N;
        }
        //入栈
        public void push(T t){
            //扩容
            if(N > size/2){
                size = size<<1;
                resize(size);
    
            }
            //入栈
            data[N++] = t;
        }
        //扩容
        public void resize(int size){
            //存储旧数据
            T[] olddata = data;
            this.data = (T[]) new Object[size];
            //把旧数据复制到新数组上
            for(int i = 0; i < N; i++){
                data[i] = olddata[i];
            }
        }
        //出栈
        public T pop(){
            //若无数据,直接返回
            if(N <= 0){
                return null;
            }
            //若数组大小有100,但是实际存储数据只有2个,那太浪费空间了
            //因此进行缩容,但若频繁扩容缩容会使整体性能下降
            if(N < size/4){
                size = size>>1;
               resize(size);
            }
            return data[--N];
        }
        
    
        @Override
        public Iterator<T> iterator() {
            return new Iterator<T>() {
                private int num = N;
                @Override
                public boolean hasNext() {
                    return num > 0;
                }
    
                @Override
                public T next() {
                    return data[--num];
                }
            };
        }
    }
    
    
版权声明:本文为xueyijin原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/xueyijin/article/details/108035244

智能推荐

JetBrains 系列开发工具,如何配置 `SCSS` `File Watcher` ,相关输出配置参数详解:webStorm phpStorm IDEA

JetBrains 系列开发工具,如何配置 SCSS File Watcher ,相关输出配置参数详解:webStorm phpStorm IDEA 前言 你目前已经了解了如何使用 SCSS 进行开发,了解了该文章的内容:『 SCSS 日常用法 』 在 JetBrains 系列开发工具中通过 FileWatcher 进行编译的 SCSS 文件都是通过 sass 这个程序进行的。『 如何添加 Fil...

C语言小函数—二进制与十六进制

测试如下 “` int main() { long int num = 15; } “`...

仿微博或微信的文章多图显示(自定义MultiImageView)

按照一般的规矩,先上张图来供大伙看看 如果大致是大伙们需要实现的功能,不烦一观 自定义MultiImageView 工具类 具体使用 app.gradle中添加依赖 implementation 'com.github.bumptech.glide:glide:4.8.0' AndroidManifest.xml中配置联网权限 <uses-permission android:name=&q...

经典进程同步和互斥问题

经典进程同步与互斥问题 前言 一、生产者-消费者问题 1.问题描述 2.问题分析 3.代码 二、读者-写者问题 1.问题描述&&分析 2.代码 三、哲学家进餐问题 1.问题描述&&分析 2.代码 四、理发师问题 1.问题描述&&分析 2.代码 前言 在多道程序设计环境中,进程同步是一个非常重要的问题,下面讨论几个经典的进程同步问题。 一、生产者-消费...

java设计模式——ThreadLocal线程单例

1、定义一个ThreadLocal线程单例,代码如下: 2、定义一个多线程类,代码如下: 3、定义一个测试类,代码如下: 4、输出结果,如下图:...

猜你喜欢

【tensorflow】线性模型实战

线性模型:y = 1.477 * x + 0.089   1. 采样数据 采样噪声eps在均值0,方差0.01的高斯分布中,而后在均匀分布U(0,1)中,区间[-10,10]进行n=100次随机采样:   2. 计算误差 循环计算每个点的预测值与真是值之间差的平方并累加,从而获得训练集上的均芳误差损失值。   3. 计算梯度   4. 梯度更新 对权重w和偏...

常见损失函数和评价指标总结(附公式&代码)

网上看到一篇很实用的帖子关于常见损失函数和评价指标,收藏下来 本文转载于https://zhuanlan.zhihu.com/p/91511706 ------------------------------------------------------------------------------------------------------------------------------...

为什么 4G/5G 的直播延时依然很高

通信技术的发展促进了视频点播和直播业务的兴起,4G 和 5G 网络技术的进步也使得流媒体技术变得越来越重要,但是网络技术并不能解决流媒体直播的高延迟问题。 本文不会介绍网络对直播业务的影响,而是会分析直播中常见的现象 — 主播和观众之间能够感觉到的明显网络延迟。除了业务上要求的延迟直播之外,有哪些因素会导致视频直播的延迟这么高呢? live-streaming  图 1 - ...

springboot 过滤器Filter vs 拦截器Interceptor 详解

1 前言       最近接触到了过滤器和拦截器,网上查了查资料,这里记录一下,这篇文章就来仔细剖析下过滤器和拦截器的区别与联系。 2 拦截器与过滤器之间的区别 从上面对拦截器与过滤器的描述来看,它俩是非常相似的,都能对客户端发来的请求进行处理,它们的区别如下: 作用域不同 过滤器依赖于servlet容器,只能在 servlet容器,web环境下使用 拦截器依赖于sp...

IDEA环境--JavaWeb项目【分页功能实现】

参考链接:https://www.jianshu.com/p/d108d0cd9acf 1、前言 最近在写一些项目,遇到要使用分页功能的地方,就简单的学习了一下,在此总结一下具体实现的过程以及遇到的问题。 分页功能:当我们写一下web项目时会遇到一个页面要显示很多数据,一下子都显示出来效率会很低,也不美观。这就要用到分页,其作用也就是将数据分割成多个页面来进行显示。 2、项目介绍 这只是一个简单的...