栈的初步认识

栈的设计

Stack接口

因为栈可以用顺序存储实现也可以用链式存储实现，所以把共性抽取定义出Stack接口

ArrayStack类(栈的顺序存储具体实现)

因为栈本身是一种特殊的线性表，所以我们可以用上一篇博客中完成的ArrayList来实现我们的ArrayStack

public class ArrayStack<E> implements Stack<E> {//栈的内部用线性表来实现private ArrayList<E> list;/*** 创建默认容量的线性表*/public ArrayStack(){list=new ArrayList<E>();}/*** 创建指定容量的线性表* @param capacity*/public ArrayStack(int capacity){list=new ArrayList<>(capacity);}/*** 获取线性表中元素个数* @return*/@Overridepublic int size() {return list.size();}/*** 判断栈是否为空* @return*/@Overridepublic boolean isEmpty() {return list.isEmpty();}/*** 压栈，在表尾添加* @param element*/@Overridepublic void push(E element) {list.add(element);}/*** 弹栈一个元素并且返回(在线性表的末尾删除一个元素并且返回)* @return*/@Overridepublic E pop() {return list.remove(list.size()-1);}/*** 查看当前栈顶元素(不删除)* @return*/@Overridepublic E peek() {return list.get(list.size()-1);}/*** 清空栈*/@Overridepublic void clear() {list.clear();}@Overridepublic Iterator<E> iterator() {return list.iterator();}@Overridepublic String toString() {StringBuilder builder = new StringBuilder(String.format("ArrayStack:%d/%d[", size(),list.getCapacity()));if (isEmpty()) {builder.append("]");//ArrayList:0/10;} else {for (int i = 0; i < size(); i++) {builder.append(list.get(i));if (i != size() - 1) {builder.append(",");} else {builder.append("]");}}}return builder.toString();}
}

十进制和十六进制的互相转换

十进制转为十六进制

public class DecToHex {public static void main(String[] args) {Scanner scanner=new Scanner(System.in);System.out.println("请输入一个十进制数:");int num=scanner.nextInt();/*** 因为会涉及到数字和字母，比如A,B这样的，所以泛型应该是Charcater* 创建一个栈来存储余数*/ArrayStack<Character> stack=new ArrayStack<>();int mod;while (num!=0){//余数入栈//余数可能是0~9也可能是A~Fmod=num%16;if (mod<10){//数字0到9stack.push((char)(mod+'0'));}else {//否则是数字10到15，要转换成A到Fstack.push((char)('A'+mod-10));}num/=16;}//按照顺序弹栈while (!stack.isEmpty()){Character pop = stack.pop();System.out.print(pop);}}
}

十六进制转为十进制

public class HexToDec {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);System.out.println("请输入一个十六进制的字符串:");String num = scanner.nextLine();//创建一个栈，存储每一个字符ArrayStack<Character> stack = new ArrayStack<>();for (int i = 0; i < num.length(); i++) {stack.push(num.charAt(i));}
//        System.out.println(stack);//依次弹栈并累加计算结果int sum = 0;//幂数int exponent = 0;char c;while (!stack.isEmpty()) {c = stack.pop();sum += Math.pow(16, exponent) * getNumber(c);exponent++;}System.out.println(sum);}/*** 把字符转换为对应的数字* 字符是0~9或A~F** @param c* @return*/private static int getNumber(char c) {if (!(c >= '0' && c <= '9' || c >= 'A' && c <= 'F')) {throw new IllegalArgumentException("错误的输入十六进制数 " + c);}//说明字符是符合十六进制的数字要求的if (c >= '0' && c <= '9') {return c - '0';} else {return 'A' + c - 10;}}
}

判断回文

public class JudgeHw {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);System.out.println("请输入一个字符串:");String str = scanner.nextLine();//创建栈ArrayStack<Character> stack=new ArrayStack<>();char c;for (int i = 0; i < str.length(); i++) {//判断字符串的长度是奇数还是偶数//如果是奇数的话，则把中间数据过滤掉，不需要压栈if (str.length()%2==1&& i==str.length()/2){continue;}c=str.charAt(i);//如果栈空，则入栈if (stack.isEmpty()){stack.push(c);}else{if (stack.peek()==c){stack.pop();}else {//不相等则入栈stack.push(c);}}//栈如果非空，则比较栈顶元素和待入栈元素是否相等，如果不相等，则入栈//如果相等，则出栈}//如果最后栈空，则是回文if (stack.isEmpty()){System.out.println("是回文");}else{System.out.println("不是回文");}}
}

有效的括号

20.有效的括号
思路分析

• 遇到左括号就入栈
• 如果遇到右括号
  • 看看栈顶是否有元素 ，如果栈为空，说明无法匹配
  • 如果栈顶有元素，但是括号不匹配，则说明无法匹配
• 所有字符扫描完毕后，如果栈空，说明有效，否则无效

class Solution {public boolean isValid(String s) {Stack<Character> stack=new Stack<>();int len=s.length();for (int i = 0; i < len; i++) {char c=s.charAt(i);if(c=='('||c=='['||c=='{'){//入栈stack.push(c);}else{//否则就是右括号//如果栈是空的，则无法匹配if (stack.isEmpty()) return false;//如果栈非空，则出栈进行匹配Character pop = stack.pop();if (pop=='(' && c!=')') return  false;if (pop=='{'&& c!='}') return false;if (pop=='['&& c!=']') return false;}}//所有字符扫描完毕后，如果栈空，说明有效，否则无效return stack.isEmpty();}
}

逆波兰表达式求值

根据 逆波兰表示法，求表达式的值。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

注意 两个整数之间的除法只保留整数部分。

可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/evaluate-reverse-polish-notation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题目可以遍历一下字符串，如果是字符是数字的话，则入栈，如果为运算符，则把栈顶的两个元素弹出，进行运算，注意它们的顺序，栈是后进先出的特点，如果是减法或除法，注意：是后面弹出的数减去或者除去前面弹出的一个数，然后把运算结果存入栈中

class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();for(int i = 0; i <tokens.length;i++){String str = tokens[i];//获取下标为 i 字符串元素if(isOperator(str)){// 如果 str 是运算符 为 true，否则为falseint num2 = stack.pop();// 获取 栈顶 的 两个数字数据（出栈）int num1 = stack.pop();switch(str){// 判断 str 具体是 哪一个字符串，就执行对应的运算，并将其结果入栈case "+":stack.push(num1 + num2);break;case "-":stack.push(num1 - num2);break;case "*":stack.push(num1 * num2);break;case "/":stack.push(num1 / num2);break;}}else{// 将 数字字符转换成 整形数据 存入 栈中stack.push(Integer.parseInt(str));}}return stack.pop();// 返回/出栈   最终存入栈中的结果}public boolean isOperator(String s){// 判断 str 是运算符 返回 true；否则，返回 falseif(s.equals("+") || s.equals("-")|| s.equals("*") || s.equals("/")){return true;}return false;}
}