一、基本概念
栈是一种线性数据结构
二、特点
-
栈是"后进先出(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,不同返回false return 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
文章来源:https://www.toymoban.com/news/detail-811357.html -
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模板网!