1. 栈
1.1 分类
顺序栈:顺序线性表实现
链式栈:单向链表存储堆栈
1.2栈的应用
1)数制转换
import java.util.Scanner; import java.util.Stack; public class Tran{ public static void main(String arg[]){ Scanner y=new Scanner(System.in); System.out.println("请输入十进制数"); int b=y.nextInt(); Tran j=new Tran(); j.ErJinZhi(b); j.BaJinZhi(b); j.ShiLiuJinZhi(b); } //转化成二进制 void ErJinZhi(int a){ Stack<Integer> s=new Stack<Integer>(); String str=""; while(a>0) { s.push(a%2); a=a/2; } while(!s.isEmpty()){ str=str+s.pop(); } System.out.println("二进制是"+str); } //转化成八进制 void BaJinZhi(int a){ Stack<Integer> s=new Stack<Integer>(); String str=""; while(a>0) { s.push(a%8); a=a/8; } while(!s.isEmpty()){ str=str+s.pop(); } System.out.println("八进制是"+str); } //转化成十六进制 void ShiLiuJinZhi(int a){ int c=0; String str=""; Stack<Character> s=new Stack<Character>(); while(a>0) { c=a%16; switch(c){ case(10):s.push('A');break; case(11):s.push('B');break; case(12):s.push('C');break; case(13):s.push('D');break; case(14):s.push('E');break; case(15):s.push('F');break; default:s.push((char)(a%16+48)); } a=a/16; } while(!s.isEmpty()){ str=str+s.pop(); } System.out.println("十六进制是"+str); } }
2)表达式的转换
中缀表达式: a+b*c ; 前缀表达式: +a*bc; 后缀表达式: acb*+
参考: http://blog.csdn.net/antineutrino/article/details/6763722/
3)递归
4)递归的非递归实现
2. 队列
2.1 队列基本操作
2.2 顺序队列 和链式队列
3. Stack类
import java.util.*; public class StackDemo { static void showpush(Stack st, int a) {
st.push(new Integer(a));
System.out.println("push(" + a + ")");
System.out.println("stack: " + st);
} static void showpop(Stack st) {
System.out.print("pop -> ");
Integer a = (Integer) st.pop();
System.out.println(a);
System.out.println("stack: " + st);
} public static void main(String args[]) {
Stack st = new Stack();
System.out.println("stack: " + st);
showpush(st, 42);
showpush(st, 66);
showpush(st, 99);
showpop(st);
showpop(st);
showpop(st);
try {
showpop(st);
} catch (EmptyStackException e) {
System.out.println("empty stack");
}
}
}
stack: [ ]
push(42)
stack: [42]
push(66)
stack: [42, 66]
push(99)
stack: [42, 66, 99]
pop -> 99
stack: [42, 66]
pop -> 66
stack: [42]
pop -> 42
stack: [ ]
pop -> empty stack