4.3进阶操作(10以内的±/*)
基本思路:
首先在2的基础上添加一个操作,在操作运算符的时候。进行判断加入话:优先级高的话,那么就直接在添加运算的时候就进行出栈和入栈的操作。然后继续正常操作。
peek(),进行查看前一个栈顶元素.
import java.sql.SQLOutput; import java.util.*; import java.awt.*; import java.lang.Math; public class hello { public static void main(String[] avgs) { String express="2*2/3*5+6"; //设置数字栈 Stack<Integer> nums=new Stack<>(); //设置字符栈 Stack<Character> operation=new Stack(); //进行压栈操作: for(int i=0;i<express.length();i++) { char ch=express.charAt(i); if (Judge(ch)){ //压入符号栈 if(operation.empty()){ operation.push(ch);}else{ char c=operation.peek(); //获取已经插入栈顶的符号,但是不是出栈 if(Grade(ch)<=Grade(c)) { //假如说栈顶的优先级低于栈底 char operation4=operation.pop(); //那么取出栈顶元素(并不是待插入的栈顶元素) int num3 = nums.pop(); int num4 = nums.pop(); //得出结果 int result = Caluat(num4, num3, operation4); //把结果进行压栈操作 nums.push(result); }operation.push(ch); } }else{ //压入数字栈 nums.push(Integer.parseInt(ch+"")); } } //进行出栈的操作 while (!operation.empty()) { int num1=nums.pop(); //出栈数字1 int num2=nums.pop(); //出栈数字2 char operation1=operation.pop(); //出栈字符 nums.push(Caluat(num2,num1, operation1)); //得出结果再入栈 } System.out.println(nums.pop()); } public static boolean Judge(char ch){ return ch=='+'||ch=='-'||ch=='*'||ch=='/'; } public static int Caluat(int num1,int num2,char operation){ switch(operation){ case '+': return num1+num2; case '-': return num1-num2; case '*': return num1*num2; case '/': return num1/num2; default: return -0; } } public static int Grade(char ch){ if(ch=='+'||ch=='-')return 1; else if (ch=='*'||ch=='/')return 2; else return 0; } }
(二)、队列
1.队列的定义:
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。(前端(队尾)删除 后端(队头)插入).------(先进先出)
2.顺序队列
基本思路:头标和尾标初始位置都为0,每次插入一个元素的时候尾标就会后移一格,删除一个元素的时候就会后移一格。
类文件:
public class Front <T>{ //定义队列数组 T [] elem; //定义头部游标 int head; //定义尾部游标: int tail; //定义队列的长度: int size; //定义队列的容量: int capctity; //进行初始化: public Front(int capctity){ this.elem=(T[])new Object[capctity]; this.size=0; //初始化游标的位置 this.head=0; this.tail=0; } //进行入队列的操作 public boolean offer(T item){ //直接把添加的元素放在队尾的位置 elem[this.tail]=item; this.tail++; //当插入的之后尾下标需要后移 this.size++; if(this.tail==capctity){return false;} return true; } //进行出队的操作: public T leave(){ if(this.size==0){return null;} T item=elem[this.head]; this.size--; this.head++; //当删除的时候头部下标会后裔 return item; } public int size(){ return this.size; } }
测试类:
import java.sql.SQLOutput; import java.util.*; import java.awt.*; import java.lang.Math; public class hello { public static void main(String[] avgs) { Front<String> s=new Front<>(10); s.offer("aa"); s.offer("bb"); s.offer("cc"); while (s.size()>0) { //因为这里是出队,出队之后个数会减少。并不是顺序表中的遍历 System.out.println(s.leave()); } } }
3.线性队列:
基本思路:头指针和尾指针,初始化是在第一个结点,并不是头节点。插入元素的时候,插入的位置是尾标的下一位。插入之后需要把尾标移动到新插入的元素下面。在出队的时候,
JavaBean类:
public class Front <T>{ class Node{ Node next; T item; public Node(T item,Node next){ this.item=item; this.next=next; } } Node head; int size; Node tail; public Front(){ this.size=0; } public boolean offer(T t){ Node node=new Node(t,null); if(size==0){ //假如说是第一个 this.tail=node; //在这初始化 this.head=node; }else { this.tail.next = node; //尾标的后一个添加 this.tail=node; //然后把尾标指向添加的这个位置 } this.size++; return true; } public T leave(){ if(this.head==null){ //假如说没有了 throw new RuntimeException("没有元素了"); } Node node=this.head; //移动头坐标到下一位 this.head=this.head.next; if(node.next==null){ //假如说node 后面没有了 this.tail=null; } this.size--; return node.item; } }
测试类:
import java.sql.SQLOutput; import java.util.*; import java.awt.*; import java.lang.Math; public class hello { public static void main(String[] avgs) { Front<String> s=new Front<>(); s.offer("aa"); s.offer("bb"); s.offer("cc"); while (s.size>0){ System.out.println(s.leave()); } } }
4.循环队列:
基本思路:当添加的受taill后移,取出的时候head后移。然后0和1的位置被控出来了。然后通过借助0和1的位置进行添加元素。
JavaBean类
public class Dui <T>{ T []elem; int size; int head; int tail; int capitcy; public Dui(int capitcy){ elem=(T[])new Object[capitcy]; //千万不能写this. this.head=0; this.size=0; this.tail=0; this.capitcy=capitcy; } public boolean add(T t){ if(this.size==this.capitcy){ throw new RuntimeException("循环队列已满"); } //添加元素 elem[this.tail]=t; this.tail++; //取模求循环后的个数,当取出来的时候就空出来了 this.tail=this.tail%this.capitcy; this.size++; return true; } //进行出队 public T remove(){ if(this.size==0){ throw new RuntimeException("队列中已经没有元素了"); } T s=elem[this.head]; this.head++; this.head=this.head%this.capitcy; this.size--; return s; } }
主类:
import java.awt.event.KeyEvent; import java.awt.event.KeyListener; import java.sql.SQLOutput; import java.util.*; import java.awt.*; import java.lang.Math; public class hello { public static void main(String[] avgs) { Dui<String> s=new Dui<>(3); s.add("aa"); s.add("bb"); s.add("cc"); while(s.size>0){ System.out.println(s.remove()); } s.add("dd"); System.out.println(s.remove()); } }