【数据结构】特殊的线性表——栈

这篇具有很好参考价值的文章主要介绍了【数据结构】特殊的线性表——栈。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【数据结构】特殊的线性表——栈,数据结构,数据结构,java,开发语言,大数据,机器学习,spring
🧧🧧🧧🧧🧧个人主页🎈🎈🎈🎈🎈
🧧🧧🧧🧧🧧数据结构专栏🎈🎈🎈🎈🎈
🧧🧧🧧🧧🧧上一篇文章:从链表到LinkedList类🎈🎈🎈🎈🎈

1.前言

什么叫栈?要搞清楚这个概念,首先要明白“栈”原来的意思,如此才能把握本质。栈,存储货物或供旅客住宿的地方,可引申为仓库、中转站,所以引入到计算机领域里,就是指数据暂时存储的地方,所以才有进栈、出栈的说法。栈这个数据结构是一个特殊的线性表,他只能在栈顶进行增删操作。

2.栈(Stack)

2.1栈的概念

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

下面为图片说明:
【数据结构】特殊的线性表——栈,数据结构,数据结构,java,开发语言,大数据,机器学习,spring
生活中的例子:
枪压子弹:第一发打出去的子弹是最后压进去的子弹。
【数据结构】特殊的线性表——栈,数据结构,数据结构,java,开发语言,大数据,机器学习,spring

2.2栈的使用

2.2.1栈的方法:
push()
pop()
peek()
empty()
search()
需要掌握并且使用较多的只有这三种压栈push()出栈(删除栈顶数据)pop()查看栈顶数据pop()
【数据结构】特殊的线性表——栈,数据结构,数据结构,java,开发语言,大数据,机器学习,spring
2.2.2栈方法的代码实现:

public class ArrayTest {
     public static void main(String[] args) {
         Stack<Integer> stack = new Stack<>();
         //push 压栈/入栈
         stack.push(1);
         stack.push(2);
         stack.push(3);
         stack.push(4);
         //pop 出栈(相当于删除) 满足先进后出,后进先出。
         int ret = stack.pop();
         System.out.println(ret);
         //peek 与出栈一样,但不会删除,只是查看栈顶的数据
         int ret2 = stack.peek();
         System.out.println(ret2);
    }
}

2.2.3pop方法与peek方法的区别
前者不仅会返回栈顶的数据并且会将返回的那个栈顶数据在栈中删除,使得栈中没有这个数据,后者只是会返回栈中栈顶的数据不会删除。

我们来调试这个程序来看看这两个方法的区别:
1.pop:
未执行pop方法时栈顶的数据还在栈中。
【数据结构】特殊的线性表——栈,数据结构,数据结构,java,开发语言,大数据,机器学习,spring
执行pop方法之后,栈顶的数据4就被删除了,并返回了栈顶的数据,由ret接收。
【数据结构】特殊的线性表——栈,数据结构,数据结构,java,开发语言,大数据,机器学习,spring
2.peek:
未执行peek方法时栈顶的数据在栈中。
【数据结构】特殊的线性表——栈,数据结构,数据结构,java,开发语言,大数据,机器学习,spring
执行peek方法之后,栈顶的数据4并没有被删除了,而且还返回了栈顶的数据,由ret2接收。
【数据结构】特殊的线性表——栈,数据结构,数据结构,java,开发语言,大数据,机器学习,spring

2.3栈的模拟实现

我分三种方式去模拟实现栈分别是数组、单向链表、双向链表。
2…3.1用数组的来模拟实现栈
用数组去模拟实现栈我们需要一个数组,和一个记录数组中数据的有效个数变量。
1.先创建一个类,类中成员变量有一个数组,一个记录数组中数据的有效个数变量

public class ArrayStack {
    public int[] elem ;
    public int usedSize;//记录数组中有效数据的个数
    public static final int DEFAULT_CAPACITY = 10;
    public ArrayStack() {
        this.elem  = new int [DEFAULT_CAPACITY];
    }
}

2.实现push方法
先要判断栈中数据是否满,满了需要将数组的容量扩容。

public void push (int val) {
        //判断栈中是否满了
        if(is_Full()) {
            //扩容
            this.elem = Arrays.copyOf(elem,2*elem.length);
        }
        //将数据压入栈中
        elem[usedSize++] = val;
    }
    public boolean is_Full () {
        return usedSize == elem.length;
    }

3.实现pop方法,首先需要判断栈中的数据是否为空,如果为空则不需要用到pop方法

 public int pop () {
        //判断栈中是否为空
        if(is_Empty()) {
            //抛异常
            throw new EmptyStackException("栈空异常!!");
        }
        //数据还是存在数组中,只是记录数组有效个数usedSize变化了,但重新压入栈的数据会覆盖之前的数据。
        usedSize--;
        return elem[usedSize];
    }
    public boolean is_Empty() {
        return  usedSize == 0;
    }

注意:这里出栈的方式是将数组的有效个数减1,事实上原先的数据还是存在数组中的,只是无法访问到而已,如果有新数据压入栈中也可以直接将之前的数据给覆盖。

4.实现peek方法首先需要判断栈中的数据是否为空,如果为空则不需要用到peek方法

public int peek() {
        //判断栈中是否为空
        if(is_Empty()) {
            //抛异常
            throw new EmptyStackException("栈空异常!!");
        }
        return elem[usedSize-1];
    }

5.这里我在判断栈是否为空的时候,我用到了一个抛出异常的方法,这样更直接的知道栈是否为空。
这是我实现栈为空异常的代码:

public class EmptyStackException extends RuntimeException{
    public EmptyStackException() {
    }

    public EmptyStackException(String message) {
        super(message);
    }
}

6.测试代码

public class ArrayTest1 {
    public static void main(String[] args) {
        ArrayStack arrayStack = new ArrayStack();
        arrayStack.push(1);
        arrayStack.push(2);
        arrayStack.push(3);
        int ret = arrayStack.pop();
        System.out.println(ret);
        int ret2 = arrayStack.peek();
        System.out.println(ret2);
    }
}

2.3.2用单向链表来模拟实现栈
1.先把这个单向链表最基本的节点结构构建出来,在这里我们采用了内部类,往大的说链表就是一个类,弹链表是由多个节点一个一个链接起来的,所以往小的说节点又是个类,该类中成员变量有存储节点的值,也有引用。

public class SinglyLinkedStack {
    static class ListNode {
        public int val;
        public ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
}

2.模拟实现push方法,在这里我们需要注意的是前面我们用数组的方式来模拟实现栈的时间复杂度为O(1)所以我们在用单向链表来模拟实现栈的时间复杂度也要保证为O(1)。在单向链表中有两种方式将数据存储在链表,一种是头插法,一种是尾插法,在这里只有头插法满足我们的要求,所以我们用头插法来实现压栈方法。

public void push(int val) {
        ListNode node = new ListNode(val);
        node.next = this.head;
        this.head = node;
    }

3.模拟实现pop方法,在删除节点的时候,我们也有两个方向来删除,一个是从头节点删,一个是从尾节点删,但需要满足时间复杂度O(1),我们采用删头节点的方式来实现pop方法。

public int pop() {
        int ret = head.val;
        this.head = head.next;
        return ret;
    }

4.模拟实现peek方法,可以直接去访问头节点的值。

public int peek() {
        return head.val;
    }

2.2.3用双向链表来模拟实现栈
在模拟之前我们可以先看看在LinkedList类中是有push、pop、peek方法的。
【数据结构】特殊的线性表——栈,数据结构,数据结构,java,开发语言,大数据,机器学习,spring
我们可以直接实列化LinkedList的一个对象来使用这些方法。

public class ListTest {
    public static void main(String[] args) {
        LinkedList<Integer> stack = new LinkedList<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack.pop());
        System.out.println(stack.peek());
    }
}

1.在模拟实现栈之前我们也需要将最基本的结构确定,和单向链表是相差不差的,只是多了一个前引用。

public class LinkedStack {
    static class ListNode {
        public int val;
        public ListNode prev;
        public ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
    public ListNode last;
}    

2.push方法在双向链表中不管是头插还是尾插,压栈的时间复杂度都是O(1)。
2.1头插法

//1.头插法
    public void push1(int val) {
        ListNode node = new ListNode(val);
        if(head == null) {
            head = node;
            last = node;
        }
        else {
            node.next = head;
            head.prev =node;
            head= node;
        }
    }

2.2尾插法

public void push2(int val) {
        ListNode node = new ListNode(val);
        if(head == null) {
            head = node;
            last = node;
        }
        else {
            node.prev = last;
            last.next =node;
            last = node;
        }
    }

3.pop方法的模拟实现,不管在头节点出还是在尾节点出时间复杂度都是O(1)
3.1删头节点

public int pop1() {
        ListNode cur = head.next;
        int ret = head.val;
        head = cur;
        return ret;
    }

3.2删尾节点

public int pop2() {
        ListNode cur = last.prev;
        int ret = last.val;
        last = cur;
        return ret;
    }

4.模拟实现peek方法,采用的头插法,直接返回头节点的值,采用的尾插法,直接返回尾节点的值。
4.1头插法

public int peek1() {
        return head.val;
    }

4.2尾插法

 public int peek2() {
        return last.val;
    }

希望大家可以给我点点关注,点点赞,并且在评论区发表你们的想法和意见,我会认真看每一条评论,你们的支持就是我的最大鼓励。🌹🌹🌹🌹🌹🌹🌹🌹🌹🌹🌹🌹🌹🌹文章来源地址https://www.toymoban.com/news/detail-840107.html

到了这里,关于【数据结构】特殊的线性表——栈的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Java数据结构学习和源码阅读(线性数据结构)

    链表的数据结构 一组由节点组成的数据结构,每个元素指向下一个元素,是线性序列。 最简单的链表结构: 数据 指针(存放执行下一个节点的指针) 不适合的场景: 需要循环遍历将导致时间复杂度的提升 链表分类—单向链表 链表结构: 数据 指针 Next(指向下一个节点)

    2024年02月12日
    浏览(43)
  • C语言数据结构——线性表之栈和队列

    为什么会定义栈和队列这两种数据结构呢? 原因在于: 之所以会定义栈和队列这样的数据结构 是因为他们有两大特性 : 第一: 他们可以保存程序运行路径中各个点的信息,以便用于回溯操作或其他需要访问已经访问过的节点信息的操作。 比如: 栈用于解决迷宫问题,就

    2023年04月11日
    浏览(110)
  • 【Dev-c++】C语言数据结构实验——线性表

    实验一 线性表 一、实验目的     1、深刻理解线性结构的特点,以及在计算机内的两种存储结构。     2、熟练掌握线性表的顺序存储结构和链式存储结构,及其它们的基本操作,重点掌握查找、插入和删除等操作。 二、实验要求     1、认真阅读程序, 将未完成的代码补

    2024年02月07日
    浏览(37)
  • 52.【Java 数据结构——线性表】

    线性表是最基本、最简单、也是最常用的一种数据结构。线性表(linear list)是数据结构的一种, 一个线性表是n个具有相同特性的数据元素的有限序列 。 线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的

    2024年02月20日
    浏览(39)
  • 【Java数据结构】线性表-队列

    队列 :只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(FirstIn First Out) 入队列:进行插入操作的一端称为 队尾(Tail/Rear) 出队列:进行删除操作的一端称为 队头(Head/Front) 在Java中, Queue是个接口,底层是通过链表实现的。

    2023年04月15日
    浏览(52)
  • 【数据结构初阶】六、线性表中的队列(C语言 -- 链式结构实现队列)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】五、线性表中的栈(C语言 -- 顺序表实现栈)_高高的胖子的博客-CSDN博客  

    2024年02月08日
    浏览(41)
  • 【数据结构初阶】七、非线性表里的二叉树(堆的实现 -- C语言顺序结构)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】六、线性表中的队列(链式结构实现队列)-CSDN博客  ===========================

    2024年02月08日
    浏览(44)
  • 【数据结构初阶】二、 线性表里的顺序表(C语言实现顺序表)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】一. 复杂度讲解_高高的胖子的博客-CSDN博客  =======================================

    2024年02月08日
    浏览(42)
  • 数据结构入门(C语言版)线性表带头双向循环链表接口实现

    在上一篇博客我们讲述了链表的概念和结构,还实现了无头单向非循环链表接口写法,那么这一章节,我们来实现另一种常用的链表组成结构——带头双向循环链表。 如果对前面的链表基本概念还是不了解,可以看作者的上一篇博客: 线性表中链表介绍及无头单向非循环链

    2023年04月12日
    浏览(45)
  • 【数据结构初阶】五、线性表中的栈(C语言 -- 顺序表实现栈)

    ========================================================================= 相关代码gitee自取 : C语言学习日记: 加油努力 (gitee.com)  ========================================================================= 接上期 : 【数据结构初阶】四、线性表里的链表(带头+双向+循环 链表 -- C语言实现)_高高的胖子的博客

    2024年02月08日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包