【数据结构】 栈(Stack)与栈的模拟实现

简介: 【数据结构】 栈(Stack)与栈的模拟实现

🍀栈(Stack)

🎋栈的概念

🎈栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底

栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则

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

比如下面数据的出栈与进栈

就像枪的弹匣一样,先压进去的子弹,最后出来

🎍栈的使用

在java中,提供了这些方法用于操作栈

使用如下:

import java.util.Stack;
public class Main {
    public static void main(String[] args) {
        Stack<Integer> s = new Stack();
        s.push(1);
        s.push(2);
        s.push(3);
        s.push(4);
        System.out.println(s.size()); // 获取栈中有效元素个数---> 4
        System.out.println(s.peek()); // 获取栈顶元素---> 4
        s.pop(); // 4出栈,栈中剩余1 2 3,栈顶元素为3
        System.out.println(s.pop()); // 3出栈,栈中剩余1 2 栈顶元素为3
        if(s.empty()){
            System.out.println("栈为空");
        }else{
            System.out.println(s.size());
        }
    }
}

🌳 栈的模拟实现

从下图中可以看到,Stack继承了Vector,Vector和ArrayList类似,都是动态的顺序表,不同的是Vector是线程安全的

接下来我们模拟实现一个栈

🚩栈的创建

我们创建一个MyStack的类,用于模拟实现我们的栈

  • 我们的这里的模拟栈用数组的形式给大家呈现
  • 创建一个int型的elem数组
  • 再创建一个usedSize的常数,用于记录栈中元素个数

  • 再给一个构造方法,构造栈初始的长度

代码实现如下:

public class MyStack {
    public int[] elem;
    public int usedSize;
    public MyStack() {
        this.elem = new int[10];
    }
}

🚩栈是否为空

若usedSize为0则为空,所以直接比较返回就好

代码实现如下

public boolean isEmpty() {
        return usedSize == 0;
    }

🚩压栈

做法如下:

  • 首先对现有栈进行判断是否为满,若满则需要进行扩容
  • 若没有满,则只需要将该元素放在数组elem下标为usedSize的位置
  • 然后usedSize加一即可

代码实现如下:

//压栈
    public void push(int val) {
        if(isFull()) {
            //扩容
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize++] = val;
    }
    public boolean isFull() {
        return usedSize == elem.length;
    }

🚩出栈

做法如下:

  • 首先得判断栈是否为空,若为空我们需要抛出异常
  • 这里我们自定义一个异常为EmptyException如下
public class EmptyException extends RuntimeException{
    public EmptyException() {
    }
    public EmptyException(String message) {
        super(message);
    }
}
  • 若不为空,则usedSize变为usedSize-1
  • 然后返回usedSize下标的元素即可

代码实现如下:

//出栈
    public int pop() {
        if(isEmpty()) {
            throw new EmptyException("栈是空的!");
        }
        return elem[--usedSize];
    }
    public boolean isEmpty() {
        return usedSize == 0;
    }

🚩获取栈顶元素

做法如下:

  • 我们同样需要对栈进行是否为空的判断
  • 若为空,抛出我们自定义栈为空的异常EmptyException
  • 若不为空,则返回数组elem下标为usedSize-1的元素

代码实现如下:

public int peek() {
        if(isEmpty()) {
            throw new EmptyException("栈是空的!");
        }
        return elem[usedSize-1];
    }

🚩MyStack完整代码实现

import java.util.Arrays;
public class MyStack {
    public int[] elem;
    public int usedSize;
    public MyStack() {
        this.elem = new int[10];
    }
    //压栈
    public void push(int val) {
        if(isFull()) {
            //扩容
            elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize++] = val;
    }
    public boolean isFull() {
        return usedSize == elem.length;
    }
    //出栈
    public int pop() {
        if(isEmpty()) {
            throw new EmptyException("栈是空的!");
        }
        return elem[--usedSize];
    }
    public boolean isEmpty() {
        return usedSize == 0;
    }
    public int peek() {
        if(isEmpty()) {
            throw new EmptyException("栈是空的!");
        }
        return elem[usedSize-1];
    }
}

自定义异常

public class EmptyException extends RuntimeException{
    public EmptyException() {
    }
    public EmptyException(String message) {
        super(message);
    }
}

🎄概念区分(栈、虚拟机栈、栈帧)

栈(stack)是只允许在一端进行插入或删除的线性表,满足后入先出的特点。

虚拟机栈逻辑结构,是具有特殊作用的一块内存空间 。 主管Java程序的运行,它保存方法的局部变量 (8种基本数据类型、对象的引用地址)、部分结果,并参与方法的调用和返回。

栈帧函数从调用过程到结束的体现,一个函数从调用到销毁其中占用的空间,内部的局部变量统一放在栈帧中。 每个函数在运行时,jvm都会创建一个栈帧,然后将栈帧压入到虚拟机栈中,当函数调用结束时,该函数对应的栈帧会从虚拟机栈中出栈。

⭕总结

关于《 【数据结构】 栈(Stack)与栈的模拟实现》就讲解到这儿,感谢大家的支持,欢迎各位留言交流以及批评指正,如果文章对您有帮助或者觉得作者写的还不错可以点一下关注,点赞,收藏支持一下!

相关文章
|
3月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
55 1
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
142 77
|
4天前
|
DataX
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
1月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
44 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
46 9
|
1月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
38 7
|
3月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
99 5
|
3月前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
116 21
|
3月前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
3月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
73 0

热门文章

最新文章