高效的宝安网站推广,绵阳城区大建设,wordpress域名更换插件,网站建设的所需解决的技术问题一、概念 栈也是一种线性数据结构#xff0c;最主要的特点是入栈顺序和出栈顺序是相反的#xff0c;操作时只能从栈顶进行操作#xff0c;在Java中给我们提供了一个泛型栈——Stack#xff0c;其中最常用的方法有#xff1a;
void push(E):进栈E pop():退栈E peek():查看…一、概念 栈也是一种线性数据结构最主要的特点是入栈顺序和出栈顺序是相反的操作时只能从栈顶进行操作在Java中给我们提供了一个泛型栈——Stack其中最常用的方法有
void push(E):进栈E pop():退栈E peek():查看栈顶元素int getSize():返回栈的元素数量isEmpty():检查栈是否为空
二、栈的实现 因为栈也是一种线性结构所以这里可以利用之前我们写的数组这里可以用接口的方式来实现我们自己的顺序栈下面进行代码演示。
数据结构Java版1——数组-CSDN博客
栈的接口
public interface Stack_i Elem{public abstract boolean push(Elem e);public abstract Elem pop();public abstract Elem peek();public abstract int getLength();public abstract boolean isEmpty();
} 通过接口的方式对stack中的方法进行重写实现功能
public class ArrStackE implements Stack_iE{private MyArrayE stack;private int length;public ArrStack() {this.stack new MyArray(16);length 0;}Overridepublic boolean push(E e) {try {stack.add(e);}catch (Exception exception){return false;}this.length;return true;}Overridepublic E pop() {if(this.getLength()0) return null;E e;try {e stack.removeByIndex(this.length - 1);}catch (Exception exception){return null;}this.length--;return e;}Overridepublic E peek() {if(this.getLength()0) return null;E e;try {e stack.getValueByIndex(this.length - 1);}catch (Exception exception){return null;}return e;}Overridepublic int getLength() {return this.length;}Overridepublic boolean isEmpty() {return this.length0;}
} 对自己的顺序栈进行代码测试
import java.util.ArrayList;
import java.util.List;
import java.util.Random;public class testMyStack {public static void test(ArrStackInteger stack, ListInteger list){Random random new Random();for(int i 0;i 10;i){stack.push(random.nextInt(1000));System.out.println(stack.peek()——现在还有stack.getLength()个元素);}Integer temp;while ((temp stack.pop())!null){list.add(temp);}System.out.println();}public static void main(String[] args) {ListInteger list new ArrayList();ArrStackInteger stack new ArrStack();test(stack,list);for (Integer i:list) {System.out.println(i);}}
}
输出结果 在测试中我们使用循环对栈先进行入栈入栈元素分别为377、338、269、107、129、66、101、760、977、786之后我们又循环出栈到list集合中出栈顺序为786、977、760、101、66、129、107、268、338、377从案例中可以看出栈这种数据结构的特点——先进后出。
三、栈可以解决的问题
1.括号匹配问题
例题20. 有效的括号 - 力扣LeetCode 这种类型的题就适合用栈这种数据结构这里我用数组集合的做法和栈的做法做比较
数组做法
import java.util.ArrayList;class Solution {public static boolean isValid(String s) {ArrayListCharacter list new ArrayList();int length 0;while(length s.length()) {if(list.size()0){list.add(s.charAt(length));continue;}if(list.get(list.size()-1).equals(()s.charAt(length))){list.remove(list.size()-1);length;continue;}if(list.get(list.size()-1).equals([)s.charAt(length)]){list.remove(list.size()-1);length;continue;}if(list.get(list.size()-1).equals({)s.charAt(length)}){list.remove(list.size()-1);length;continue;}list.add(s.charAt(length));}return list.isEmpty();}
}
输出结果 栈做法
class Solution {public boolean isValid(String s) {StackCharacter stack new Stack();char[] chars s.toCharArray();for(int i 0;i chars.length;i){if(chars[i](||chars[i][||chars[i]{) stack.push(chars[i]);if(chars[i])||chars[i]]||chars[i]}){if(stack.isEmpty()){return false;}char char_temp stack.pop();if(char_temp(chars[i]!)) return false;if(char_temp[chars[i]!]) return false;if(char_temp{chars[i]!}) return false;}}return stack.size()0;}
} 输出结果 这里简单说明一下这道题的思路因为要判断括号是否匹配则左括号和右括号都是一一对应的若出现了不对应的情况则视为不匹配我们可以遇到左括号时进栈而遇到右括号时出栈此时若括号匹配则栈中现在只有左括号我们只用判断出栈元素是否与当前循环元素匹配就行循环结束后栈应该为空。在这其中只要有一次匹配失败则返回false。总结一下我们一个需要注意这几个要求
入栈元素为左括号遇到右括号出栈判断出栈元素与当前循环元素是否匹配循环结束后栈是否为空
