栈的定义
栈是限定在表尾进行插入和删除操作的线性表(底层也是动态数组)，把允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom),不含任何元素的栈叫做空栈，栈又称为后进先出的线性表，简称LIFO结构，栈本身就是一个线性表，其数据元素具有线性关系，只不过他是一种特殊的关系
栈的插入操作，叫做进栈，也称为压栈,入栈
栈的删除操作，叫做出栈，也称为弹栈
因为我们之前实现过线性表ArrayList,栈的底层也是动态数组，所以我们可以将栈的底层也变为线性表ArrayList来实现
Stack接口的实现
package List接口实现;
//支持泛型，继承Iterable接口
public interface Stack<E> extends Iterable<E> {//获取栈的容量public int size();//判断栈是否为空public boolean isEmpty();//进栈一个元素public void push(E element);//弹栈一个元素public E pop();//弹栈一个元素并且返回这个元素public E peek();//清空当前这个栈public void clear();
}
ArrayStack类实现Stack接口
package 动态数组;import List接口实现.Stack;import java.util.Iterator;public class ArrayStack<E> implements Stack<E> {//栈的内部就是由一个线性表来实现private ArrayList<E> list;//创建一个默认容量的栈(默认容量的线性表)public ArrayStack(){list = new ArrayList<E>();}//由用户指定一个容量的线性表public ArrayStack(int capacity){list=new ArrayList<>(capacity);}//获取栈中有效元素的个数@Overridepublic int size() {//线性表中有多少个有效元素，栈中就有多少个有效元素return list.size();}
//判断栈是否为空@Overridepublic boolean isEmpty() {return list.isEmpty();}//入栈一个元素(在线性表的表尾添加一个元素)@Overridepublic void push(E element) {list.add(element);//默认在表尾添加元素}
//弹栈一个元素并返回(在线性表的表尾删除一个元素)@Overridepublic E pop() {return list.remove(list.size()-1);}//获取 当前的栈顶元素(不删除)@Overridepublic E peek() {return list.get(list.size()-1);}
//清空栈就是清空线性表@Overridepublic void clear() {list.clear();}//获取底层线性表的迭代器@Overridepublic Iterator<E> iterator() {return list.iterator();}public String toString(){StringBuilder sb =new StringBuilder(String.format("ArrayList:%d/%d[",size(),list.getCapacity()));if(isEmpty()){sb.append("]");//ArrayList:0/10[]}else{//ArrayList:0/10[1,2,3,4,5]for(int i=0;i<size();i++){sb.append(list.get(i));if(i!=size()-1){sb.append(',');}else{sb.append(']');}}}return sb.toString();}
}
栈的应用
十进制转十六进制
需求：输入一个非负的十进制整数，打印输出与其等值的十六进制数
package 动态数组;
import java.util.Scanner;
//十进制转十六进制
public class DecToHex {public static void main(String[] args) {//1,获取用户输入一个非负的整数Scanner input =new Scanner(System.in);System.out.println("Enter a number");int number =input.nextInt();//2,创建一个栈来存储余数ArrayStack<Character> stack =new ArrayStack<>();//3,开始计算余数int mod;while(number!=0){mod =number%16;//获取一个余数0-9或者10-15--->A-Fif(mod<10){//数字0-9//'0'+3表示字符0之后第三个位置的字符编码，同理'3'-'0'=3stack.push((char)('0'+mod));}else{//数字10-15-->A-F//'A'+15-10='A'+5表示的是字符A之后第5个位置的字符F的编码stack.push((char)('A'+mod-10));}number/=16;//4,按照顺序弹栈即可while(!stack.isEmpty()){System.out.print(stack.pop());}}}
}
十六进制转十进制
package 动态数组;
import java.util.Scanner;
public class HexToDec {public static void main(String[] args) {//1,获取用户的输入，输入一个十六进制的字符串Scanner scanner =new Scanner(System.in);System.out.println("Enter a hex string");String hex =scanner.nextLine();//2,创建一个栈，存储一个数字ArrayStack<Character> stack =new ArrayStack<>();//3,将字符串中的字符依次进栈for(int i=0;i<hex.length();i++){stack.push(hex.charAt(i));}//4,依次弹栈，并累加计算的结果int sum =0;int exponent =0;//幂数int c;while(!stack.isEmpty()){c=stack.pop();sum+=getNumber(c)*Math.pow(16,exponent);//exponent表示幂数exponent++;}System.out.println(sum);}private static int getNumber(int c) {//验证字符是否合法if(!('0'<=c && c<='9'||c>='A'&&c<='F')){throw new IllegalArgumentException("字符错误");}//转换数字字符为数字if(c>='0'&&c<='9'){return c-'0';}//转换字母字符为数字else{return c-'A'+10;}}
}
用栈来判断回文
package 动态数组;
import java.util.Scanner;
public class 判断回文 {public static void main(String[] args) {//判断回文//1,获取用户的输入字符串Scanner input =new Scanner(System.in);System.out.println("Enter a text");String s=input.nextLine();//2.创建一个栈ArrayStack<Character> stack =new ArrayStack<>();//3,开始遍历遍历字符串,并做出出栈和入栈的操作char c;for(int i=0;i<s.length();i++){//当前字符串的长度是否奇数,如果是奇数的话，直接跳过此迭代if(s.length()%2==1 && i==s.length()/2){continue;}c=s.charAt(i);//4，如果是空栈,直接放元素if(stack.isEmpty()){stack.push(c);}//5,如果不为空，将元素弹出来进行比较else{if(c==stack.peek()){stack.pop();//相等的就相消}else{stack.push(c);//不相等就往栈里面放}}}//栈是空，说明相消完了，说明是匹配的if(stack.isEmpty()){System.out.println("是回文字符串");}else{//栈不为空，就没有相消完，说明不是回文System.out.println("不是回文字符串");}}
}
匹配括号
package 动态数组;
public class 匹配括号 {public static void main(String[] args) {String text ="{[<>]()}";//1,创建一个栈ArrayStack<Character> stack =new ArrayStack<>();//2.开始遍历text做出栈入栈的操作char c;char top;for(int i=0;i<text.length();i++){c=text.charAt(i);//3,如果栈为空，直接进if(stack.isEmpty()){stack.push(c);}else{top =stack.peek();//top-c==-1||top-c==-2是否是一对if(top-c==-1||top-c==-2){//是一对，弹栈stack.pop();}else{//不是一对，进栈stack.push(c);}}}if(stack.isEmpty()){System.out.println("这是匹配的");}else{System.out.println("这不是匹配的");}}
}
中缀表达式
是一个通用的算术或者逻辑公式的表示方法，操作符是以中缀的形式处于操作数的中间（例如 3+4）,与前缀表达式(例如 +3 4 )或后缀表达式(例如 3 4+)相比，中缀表达式不容易被计算机解析，但仍被许多程序语言使用，因为它符合人们的普遍用法
与前缀或后缀记法不同的是，中缀记法中括号是必须的
栈实现中缀表达式
package 动态数组;
import 动态数组.ArrayStack;
public class 中缀表达式 {public static void main(String[] args) {String expression = "(20+30/2*8/9+40-90/3*4)+40-50*6+(50*2-3)";//1，格式化表达式expression = insertBlanks(expression);//2.对字符串进行截取String [] tokens =expression.split(" ");//3,创建两个栈//数字栈ArrayStack<Integer> numberStack =new ArrayStack<>();//操作符栈ArrayStack<Character> operatorStack =new ArrayStack<>();//4,对字符串进行foreach遍历for(String token:tokens){//如果是空字符串的话，直接跳过当前当前循环if(token.length()==0){continue;}//如果是'+'或者是'-',让操作符栈中的所有操作符进行运算if(token.charAt(0)=='+'||token.charAt(0)=='-'){while(!operatorStack.isEmpty()&&(operatorStack.peek()=='+'||operatorStack.peek()=='-'||operatorStack.peek()=='*'||operatorStack.peek()=='/')){processAnOperator(numberStack,operatorStack);}operatorStack.push(token.charAt(0));}//如果是'*'或者是'/',让操作符栈中的* 和 /操作符进行运算else if(token.charAt(0)=='*'||token.charAt(0)=='/'){while(!operatorStack.isEmpty()&&(operatorStack.peek()=='*'||operatorStack.peek()=='/')){processAnOperator(numberStack,operatorStack);}operatorStack.push(token.charAt(0));}//如果遍历到的是'(',就把它放到栈里else if(token.charAt(0)=='('){operatorStack.push('(');}//如果遍历到的是')',就把它放到栈里,只要栈顶元素不是'(',就一直进行运算，知道遇到'(',然后将'('弹栈即可else if(token.charAt(0)==')'){while (operatorStack.peek()!='('){processAnOperator(numberStack,operatorStack);}operatorStack.pop();}else{//如果是数字直接进栈numberStack.push(new Integer(token));}}//两个栈还有元素没有运行完,需要继续进行运算while(!operatorStack.isEmpty()){processAnOperator(numberStack,operatorStack);}//打印最后的结果，最后的结果放到栈里System.out.println(numberStack.pop());}//在数字栈中弹出两个数字和在操作符栈中弹出一个字符，做运算private static void processAnOperator(ArrayStack<Integer> numberStack, ArrayStack<Character> operatorStack) {char op =operatorStack.pop();int num1 =numberStack.pop();int num2 =numberStack.pop();if(op=='+'){numberStack.push(num2+num1);}else if(op=='-'){numberStack.push(num2-num1);}else if(op=='*'){numberStack.push(num2*num1);}else if(op=='/'){numberStack.push(num2/num1);}}private static String insertBlanks(String expression) {StringBuilder sb = new StringBuilder();char c;//如果遇到符号，就前后加空格，如果是数字，就不加空格，直接appendfor (int i = 0; i < expression.length(); i++) {c = expression.charAt(i);if (c == '+' || c == '-' || c == '*' || c == '/'||c=='('||c==')') {sb.append(' ');sb.append(c);sb.append(' ');} else {//是数字sb.append(c);}}return sb.toString();}
}
后缀表达式
也叫逆波兰表达式，将运算符写在操作数之后
中缀转后缀的代码示例
package 动态数组;import java.util.Arrays;
public class 中缀转后缀表达式 {public static void main(String[] args) {String infixExpression = "(20-40/2*3/8+20)/20+8/2*3-(10*4/5-6)/2";//中缀表达式转后缀表达式String suffixExpression = infixToSuffix(infixExpression);//打印转化后的结果System.out.println(suffixExpression);}private static String infixToSuffix(String infixExpression) {//创建一个字符栈ArrayStack<String> opStack =new ArrayStack<>();//创建一个中缀表达式的列表ArrayList<String> suffixList =new ArrayList<>();//格式化字符串infixExpression = insertBlanks(infixExpression);//切割字符串String [] tokens =infixExpression.split(" ");System.out.println(Arrays.toString(tokens));//遍历字符串for(String token:tokens){//过滤空字符串if(token.length()==0){continue;}if(isOperator(token)){//如果是操作符while(true){//这里是需要执行多次，所以要用到while(true)if(opStack.isEmpty()||"(".equals(opStack.peek())){opStack.push(token);break;}if(priority(token)>priority(opStack.peek())){opStack.push(token);break;}//除了以上的情况之外，如果操作符比栈中操作符优先级小,将操作符弹栈并且添加到列表里suffixList.add(opStack.pop());}}else if(isNumber(token)){//如果是数字suffixList.add(token);}else if("(".equals(token)){//如果是（opStack.push(token);}else if(")".equals(token)){//如果是）//栈顶元素是"("while (true){if("(".equals(opStack.peek())){opStack.pop();break;}else{suffixList.add(opStack.pop());}}}else {throw new IllegalArgumentException("wrong identifer"+token);}}while (!opStack.isEmpty()){suffixList.add(opStack.pop());}StringBuilder sb =new StringBuilder();for(int i=0;i<suffixList.size();i++){sb.append(suffixList.get(i)+" ");}return sb.toString();}private static int priority(String token) {if("*".equals(token)||"/".equals(token)){return 1;}if("+".equals(token)||"-".equals(token)){return 0;}return -1;}private static boolean isNumber(String token) {return token.matches("\\d+");// \\d+表示匹配多个数字}private static boolean isOperator(String token) {return "+".equals(token)||"-".equals(token)||"*".equals(token)||"/".equals(token);}private static String insertBlanks(String infixExpression) {StringBuilder sb =new StringBuilder();//遍历表达式char c;for(int i=0;i<infixExpression.length();i++){c=infixExpression.charAt(i);if(c=='+'|| c=='-'||c=='*'||c=='/'||c=='('||c==')'){sb.append(' ');sb.append(c);sb.append(' ');}else{sb.append(c);}}return sb.toString();}}
后缀计算器的实现
package 动态数组;public class 后缀表达式计算器 {public static void main(String[] args) {//转换后的后缀表达式String expression ="20 40 2 / 3 * 8 / - 20 + 20 / 8 2 / 3 * + 10 4 * 5 / 6 - 2 / - ";//新建一个数字栈ArrayStack<Integer> stack =new ArrayStack<>();String [] tokens = expression.split(" ");for(String token:tokens){//如果是数字直接进if(isNumber(token)){stack.push(new Integer(token));}//如果是操作符则弹出两个数字，进行计算，然后将新的结果入栈else{processAnOperator(stack,token);}}//打印最后的结果System.out.println(stack.pop());}//运算过程private static void processAnOperator(ArrayStack<Integer> stack, String token) {int num1 = stack.pop();int num2 =stack.pop();switch (token){case "+":stack.push(num2+num1);break;case "-":stack.push(num2-num1);break;case "*":stack.push(num2*num1);break;case "/":stack.push(num2/num1);break;}}private static boolean isNumber(String token) {//表示匹配的是数字return token.matches("\\d+");}}