数据结构---栈(Stack)

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

一、基本概念

栈是一种线性数据结构

二、特点

  1. 栈是"后进先出(LIFO---Last In First Out)"的数据结构(盘子的叠放:当服务员将新的盘子放在餐桌上时,他们通常会将盘子放在已有的盘子堆的顶部。当顾客用完盘子后,服务员会从堆顶取走盘子。这个过程就类似于栈的入栈和出栈操作。)

  2. 规定只能从栈顶添加元素,也只能从栈顶取出元素

栈可以解决:递归,括号匹配的问题,表达式求值的问题

三、基本操作

  1. 创建的MyArray类(数据结构---数组)

  2. 创建一个接口,里面实现栈相关操作

    public interface Stack_1<T> {
        //  入栈
        void push(T ele);
    
        //  出栈的接口
        T pop();
    
        //  查看栈顶元素
        T peek();
    
        //  判断栈是否为空
        boolean isEmpty();
    
        //  获取栈中元素个数
        int getSize();
    }
  3. 创建一个以数组作为栈的底层的类

    public class ArrStack<T> implements Stack_1<T>{}
  4. 定义全局变量

    private MyArray<T> data;//  容器
    int size;//  栈中实际存放的元素的个数
  5. 对数组栈的构造方法进行重写

    public ArrStack() {
        //  将容器进行初始化
        this.data = new MyArray<>(100);
        //  将栈中实际存放的元素的个数初始化
        this.size = 0;
    }
  6. 入栈操作

    @Override
    public void push(T ele) {
        //  在数组尾部添加元素
        this.data.add(ele);
        //  更新实际存放元素的个数
        this.size++;
    }
  7. 出栈操作

    @Override
    public T pop() {
        //  判断栈是否为空
        if (isEmpty()) {
            return null;
        }
        //  栈不为空时,现将实际元素个数更新
        this.size--;
        //  将最后一个元素出栈
        return this.data.removeFromLast();
    }
  8. 查看栈顶元素

    @Override
    public T peek() {
        //  获得最后一个元素的值
        return this.data.getLastValue();
    }
  9. 判断栈是否为空

    @Override
    public boolean isEmpty() {
        //  栈中实际存放元素个数与0相比,相同返回true,不同返回false
        return this.size == 0;
    }
  10. 获取栈中元素个数

    @Override
    public int getSize() {
        //  返回栈中实际存放个数
        return this.size;
    }

四、特殊

单调栈

单调栈实际上还是栈,只是利用了一些巧妙的逻辑,使得每次新元素入栈后,栈内元素都保持单调.

处理Next Greater Element类型的问题

五、相关题

力扣第20题--有效的括号

给定一个只包括 '('')''{''}''['']' 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。

  2. 左括号必须以正确的顺序闭合。

  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1:

输入:s = "()"

输出:true

示例 2:

输入:s = "()[]{}"

输出:true

示例 3:

输入:s = "(]"

输出:false

提示:

  • 1 <= s.length <= 104

  • s 仅由括号 '()[]{}' 组成文章来源地址https://www.toymoban.com/news/detail-811357.html

class Solution {
   public boolean isValid(String s) {
        //  使用栈(括号匹配)
        if (s == null || s.length() == 0) {
            return true;
        }
        //  创建栈
        Stack<Character> stack = new Stack<>();
        int strLength = s.length();
        for (int i = 0; i < strLength; i++) {
            //  获取字符
            char c = s.charAt(i);
            //  遇到左边入
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                //  遇到右边出栈--出站时要判断栈是否为空
                if (stack.isEmpty()) {
                    return false;
                }
                char topC = stack.pop();
                if (!(c == ')' && topC == '(') && !(c == ']' && topC == '[') && !(c == '}' && topC == '{')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

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

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

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

相关文章

  • 【算法与数据结构】494、LeetCode目标和

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :本题和这道题【算法与数据结构】1049、LeetCode 最后一块石头的重量 II类似,同样可以转换成01背包问题。下面开始论述。假设添加正号的整数子集和为 p o s i t i v e positive p os i t

    2024年01月20日
    浏览(44)
  • 【算法与数据结构】62、LeetCode不同路径

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :机器人只能向下或者向右移动,那么到达(i,j)位置的路径和(i-1,j)以及(i,j-1)有关。那么我们就得到的动态规划的表达式 d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + d p [ i ] [ j − 1 ] dp[i][

    2024年01月18日
    浏览(68)
  • 数据结构算法leetcode刷题练习(1)

    给定一个三角形 triangle ,找出自顶向下的最小路径和。 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标

    2023年04月24日
    浏览(54)
  • 【python与数据结构】(leetcode算法预备知识)

    笔记为自我总结整理的学习笔记,若有错误欢迎指出哟~ 1.数字类型: 整数(int):表示整数值,例如 1、-5、100。 浮点数(float):表示带有小数部分的数字,例如 3.14、-0.5、2.0。 复数(complex):表示实部和虚部的复数,例如 2+3j。 2.布尔类型(bool): 表示真(True)或假(

    2024年02月08日
    浏览(39)
  • 【算法与数据结构】377、LeetCode组合总和 Ⅳ

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :本题明面上说是组合,实际上指的是排列。动态规划排列组合背包问题需要考虑遍历顺序。 d p [ i ] dp[i] d p [ i ] 指的是nums数组中总和为target的元素排列的个数。 d p [ i ] dp[i] d p [

    2024年01月23日
    浏览(41)
  • 【算法与数据结构】63、LeetCode不同路径 II

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :参考【算法与数据结构】62、LeetCode不同路径的题目,可以发现本题仅仅是多了障碍物。我们还是用动态规划来做。有障碍物的地方无法到达,因此路径数量为0,只需要将障碍物位

    2024年02月02日
    浏览(57)
  • 【算法与数据结构】226、LeetCode翻转二叉树

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :这道题的思路很简单,本质上就是遍历每一个节点,然后交换左右节点。我们可以用前中后遍历或者是层次遍历法来做,参考这两篇文章,【算法与数据结构】144、94、145LeetCode二

    2024年02月16日
    浏览(41)
  • 【算法与数据结构】518、LeetCode零钱兑换 II

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :本题的硬币是无数的,因此本题可以抽象成一个完全背包问题。完全背包和01背包的不同之处在于完全背包式从前往后遍历的。在本题的完全背包问题中,amount代表背包的最大重量

    2024年01月23日
    浏览(43)
  • 【算法与数据结构】28、LeetCode实现strStr函数

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :首先判断字符串是否合法,然后利用for循环,取出子字符串利用compare函数进行比较。    程序如下 : 复杂度分析: 时间复杂度: O ( n ∗ m ) O(n * m) O ( n ∗ m ) ,假设haystack的长

    2024年02月12日
    浏览(45)
  • 【算法与数据结构】232、LeetCode用栈实现队列

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :这道题要求我们用栈模拟队列(工作上一定没人这么搞)。程序当中,push函数很好解决,直接将元素push进输入栈当中。pop函数需要实现队列先进先出的操作,而栈是先进后出。只

    2024年02月12日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包