数据结构---栈(Stack)

发布时间:2024年01月21日

一、基本概念

栈是一种线性数据结构

二、特点

  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 仅由括号 '()[]{}' 组成

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();
 ?  }
}
文章来源:https://blog.csdn.net/2302_77527700/article/details/135721170
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。