说好的在暑假对数据结构进行一个通盘复习，结果还是没能做到。现在只能趁着学习间隙补上。
所谓栈，就是后进先出。 它的基本操作有创建栈、判断栈是否为空、入栈、出栈和取栈顶元素等等，不支持对指定位置的插入、删除等操作。从这方面看，栈似乎是一种操作受限的线性表。但为什么还要用这个呢？因为数组或者链表的接口过多，也会更加的不可控。所以，当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出或者先进后出的特性，首选栈这一种线性结构。
栈的应用 栈在实现嵌套调用和递归调用、实现非线性结构的深度遍历算法、以非递归算法实现递归算法等都有广泛应用。下面给出两个实例： （1）插号匹配的语法检查 括号可以嵌套，嵌套括号的原则是一个右括号与其前面最近的一个左括号匹配。假设表达式中只包含三种括号，圆括号()、方括号[]和花括号{}，并且它们可以任意嵌套。比如，{[{}]}或[{()}([])]等都为合法格式，而{[}()]或[({)]为不合法的格式。比如有一个字符串，ch是这字符串中的一个元素，如果ch是左括号，则ch入栈；如果ch是右括号，则出栈，若出栈字符为左括号，表示这一对括号可以匹配；若栈空或出栈字符不是左括号，表示缺少可以与ch匹配的左括号。 （2）计算算术表达式的值 从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较。如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取2个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。1、使用一个栈，将十进制装换为二进制或十六进制；
import java.util.Scanner; public class Lab021 { public static String transform(int x,int r){ Stack<Integer>stack=new SeqStack<Integer>(); //创建栈stack存储元素 int i=0; while(x!=0){ //转换到想要的进制 i=x%r; x=x/r; stack.push(i); //将i入栈 } while(!stack.IsEmpty()){ int j=stack.pop(); //将栈中元素输出，若小于10则直接输出 if(j<10) System.out.print(j); else{ switch(j){ case 10:System.out.println("A");break; case 11:System.out.println("B");break; case 12:System.out.println("C");break; case 13:System.out.println("D");break; case 14:System.out.println("E");break; case 15:System.out.println("F");break; } }} return (stack.IsEmpty())?"":"栈非空"; //返回为空即正确 } public static void main(String[] args) { System.out.print("请输入需要转换的数字："); Scanner reader=new Scanner(System.in); int x=reader.nextInt(); System.out.print("请输入想要转换为几进制的数字："); int r=reader.nextInt(); System.out.print(transform(x,r)); } }2、用递归算法实现角谷猜想的计算过程 描述：所谓角谷猜想，是指对于任意一个正整数，如果是奇数，则乘3加1，如果是偶数，则除以2，得到的结果再按照上述规则重复处理，最终总能够得到1。如，假定初始整数为5，计算过程分别为16、8、4、2、1。 程序要求输入一个整数，将经过处理得到1的过程输出来。 【输入】：一个正整数 【输出】：从输入整数到1的步骤，每一步为一行，每一部中描述计算过程 例如：输入为5，则输出为： 5*3+1=16 16/2=8 8/2=4 4/2=2 2/2=1 最后一行输出"End"，如果输入为1，直接输出"End"
public class Lab023 { public static int calculate(int x){ int End = 0; if(x<=0)throw new java.lang.IllegalArgumentException("x="+x); //抛出无效参数异常 if(x==1) return 1; //跳出递归 if(x%2==0){ //x为偶数 System.out.print(x); x=x/2; System.out.println("/2="+x); return calculate(x); }else{ System.out.print(x); //x为奇数 x=x*3+1; System.out.println("*3+1="+x); return calculate(x); } } public static void main(String[] args) { System.out.println("请输入一个正整数："); Scanner reader=new Scanner(System.in); int x=reader.nextInt(); calculate(x); System.out.println("End"); } }这一次的复习就到这里了，下一次就是队列了。若有错误，敬请指正。
