(一)、栈
1.栈的定义(Stack):
栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。(先进后出)
2.栈链式储存结构的进栈出栈
链式栈的基本思路:是把添加的元素直接放在链表的第一个节点。出栈的时候也是直接把第一个节点进行出栈
设置链表:
public class Node { Node next; T item; public Node(T item, Node next) { this.item = item; this.next = next; } }
压栈:（压栈压的是头节点的下一个结点）
public void push(T t) { Node Insert = new Node(t, null); if (this.size == 0) { this.head.next = Insert; } else { //获取原先的第一个结点 Node before = this.head.next; //开始进行链接 this.head.next = Insert; Insert.next = before; } this.size++; }
出栈:（不用this.size-- 操作）
public T pop() { //出栈的话不用-- //获取第一个结点 Node first = this.head.next; if (this.size == 1) { return first.item; } else { //获取第二个结点 Node second = first.next; //开始断链 this.head.next = second; //进行数量控制: return first.item; } }
类方法：
public class LinkeStack<T> { public class Node { Node next; T item; public Node(T item, Node next) { this.item = item; this.next = next; } } Node head; int size; public LinkeStack() { this.size = 0; this.head = new Node(null, null); } //获取个数 public int getSize() { return this.size; } //进行压栈操作（实际上就是直接压入头节点的下一个结点） public void push(T t) { Node Insert = new Node(t, null); if (this.size == 0) { this.head.next = Insert; } else { //获取原先的第一个结点 Node before = this.head.next; //开始进行链接 this.head.next = Insert; Insert.next = before; } this.size++; } //进行出栈的操作: public T pop() { //出栈的话不用-- //获取第一个结点 Node first = this.head.next; if (this.size == 1) { return first.item; } else { //获取第二个结点 Node second = first.next; //开始断链 this.head.next = second; //进行数量控制: return first.item; } } }
3.栈顺序储存结构的出栈和进栈
类方法:（继承了顺序表的函数）
import java.util.ArrayList; public class SquenceStack<T> extends SquenceLisr { public SquenceStack(int capacity){ super(capacity); } //进行入栈 public void push(T t){ Insert(t); } //进行出栈 public T pop(){ return (T)remove(getLength()-1); } }
主方法:
import java.sql.SQLOutput; import java.util.*; import java.awt.*; import java.lang.Math; public class hello { public static void main(String []avgs) { SquenceStack<String> stack=new SquenceStack<>(10); stack.push("aa"); stack.push("bb"); stack.push("cc"); stack.push("dd"); for(int i=0;i<4;i++){ System.out.println(stack.pop()); } } }
4.栈的实践操作（计算器）
4.1基础操作(两数相加)
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="7)8"; //进行分步取解 //获取数字1； char numStr1=express.charAt(0); //获取第二个数字: char numStr2=express.charAt(2); //获取中间的字符 char operation=express.charAt(1); //进行字符串的转换 int num1=Integer.parseInt(numStr1+""); //只能转换字符串，所以这样做 int num2=Integer.parseInt(numStr2+""); try { int reuult= Caluat(num1,num2,operation); System.out.println(reuult); } catch (Exception e) { System.out.println("输入的符号有错"); } } 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; } } }
4.2进阶操作(10以内的，多数相加)
基本思路:创建两个栈、一个是数字栈、另一个是字符栈。然后通过对字符串的遍历得到对应的字符，然后通过判断字符，如果是逻辑表达式，那么就进入字符栈，如果是数字字符，那么就进入数字栈。然后再进行对最后进入的三个字符进行依次出栈，得到结果后，再进行入栈操作。直到最后字符栈为空就最后一次数字出栈。
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="1+2+3+5"; //设置数字栈 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)){ //压入符号栈 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(num1,num2, 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; } } }
