数据结构---栈(Stack)

2026/8/10 23:09:58 拓冰建站浏览量

一、基本概念

栈是一种线性数据结构

二、特点

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

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

三、基本操作

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

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

public interface Stack_1<T> {//  入栈void push(T ele);//  出栈的接口T pop();//  查看栈顶元素T peek();//  判断栈是否为空boolean isEmpty();//  获取栈中元素个数int getSize();
}

创建一个以数组作为栈的底层的类

public class ArrStack<T> implements Stack_1<T>{}

定义全局变量

private MyArray<T> data;//  容器
int size;//  栈中实际存放的元素的个数

对数组栈的构造方法进行重写

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

入栈操作

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

出栈操作

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

查看栈顶元素

@Override
public T peek() {//  获得最后一个元素的值return this.data.getLastValue();
}

判断栈是否为空

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

获取栈中元素个数

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

四、特殊

单调栈

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

处理Next Greater Element类型的问题

五、相关题

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

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 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();}
}

建站实战干货