电子商务网站建设与维护总结,网站建设明细价单,龙岗网站设计案例,wordpress百科主题一、基本概念
栈是一种线性数据结构
二、特点 栈是后进先出(LIFO---Last In First Out)的数据结构(盘子的叠放#xff1a;当服务员将新的盘子放在餐桌上时#xff0c;他们通常会将盘子放在已有的盘子堆的顶部。当顾客用完盘子后#xff0c;服务员会从堆顶取走…一、基本概念
栈是一种线性数据结构
二、特点 栈是后进先出(LIFO---Last In First Out)的数据结构(盘子的叠放当服务员将新的盘子放在餐桌上时他们通常会将盘子放在已有的盘子堆的顶部。当顾客用完盘子后服务员会从堆顶取走盘子。这个过程就类似于栈的入栈和出栈操作。) 规定只能从栈顶添加元素,也只能从栈顶取出元素
栈可以解决:递归,括号匹配的问题,表达式求值的问题
三、基本操作 创建的MyArray类(数据结构---数组) 创建一个接口,里面实现栈相关操作 public interface Stack_1T {// 入栈void push(T ele);// 出栈的接口T pop();// 查看栈顶元素T peek();// 判断栈是否为空boolean isEmpty();// 获取栈中元素个数int getSize();
} 创建一个以数组作为栈的底层的类 public class ArrStackT implements Stack_1T{} 定义全局变量 private MyArrayT 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;}// 创建栈StackCharacter 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();}
}
