序
去年在二手书网店买课本的时候看到本java数据结构书,一直没看,最近翻出来看看,书如下图,看上去是哪个大学的课本,第一章概念里还有画线笔记
表
- 略
栈和队列
栈的实现
- 发现按我的思路写的代码比书上的代码短不少,只有书上的三分之一
public interface Stack<T> {
//入栈
void push(T data);
//输出并删除
T pop();
//size
int size();
default boolean isEmpty(){
return size() == 0;
}
}
//顺序栈实现
public class SeqStack<T> implements Stack<T>{
private Object[] stackArray;
private int size;
private final static int MAX_SIZE = 1024 * 1024;
//初始化
public SeqStack(){
size = 0;
stackArray = new Object[16];
}
@Override
public void push(T data) {
if(size() == MAX_SIZE) throw new IllegalArgumentException("over max size");
//判断是否超出数组,超出数组就扩
if(size == stackArray.length){
stackArrayExtend();
}
stackArray[size] = data;
size++;
}
@Override
@SuppressWarnings("unchecked")
public T pop() {
//size为0时不能pop
if(isEmpty()){
throw new IllegalArgumentException("empty static can not pop");
}
var tmp = stackArray[size-1];
stackArray[size-1] = null; //clear
size--;
return (T) tmp;
}
@Override
public int size() {
return this.size;
}
private synchronized void stackArrayExtend(){
int extendArrayLength = stackArray.length * 2;
var stackArrayTmp = new Object[extendArrayLength];
for (int i = 0; i < size ; i++) {
stackArrayTmp[i] = stackArray[i];
}
this.stackArray = stackArrayTmp;
}
}
//链栈的实现
public class LinkStack<T> implements Stack<T> {
private LinkStack<T> next;
private T data;
private int size;
public LinkStack(){
}
@Override
public void push(T data) {
//每次新来上个,都复制自己到下一个上去
LinkStack<T> next = new LinkStack<>();
next.size = this.size;
next.data = this.data;
next.next = this.next;
this.next = next;
this.data = data;
this.size += 1;
}
@Override
public T pop() {
if(this.size == 0) throw new IllegalArgumentException("empty stack can not pop");
var data = this.data;
this.data = next.data;
this.size = next.size;
this.next = next.next;
return data;
}
@Override
public int size() {
return this.size;
}
}
栈的应用
十进制转换二进制,8进制,16进制
- 实现
//十进制转其他进制
public static String convertDec(Integer number,Integer system){
if(number < 0) throw new IllegalArgumentException("只能转换大于0的数");
if(number < system) return "" + number;
Stack<Integer> stack = new SeqStack<>(); //顺序栈和链栈都可以
//相除取余进栈
while (true){
var remainder = number % system;
stack.push(remainder);
number = number / system;
if(number < system && number!= 0){
stack.push(number);
break;
}
}
var result = "";
while (!stack.isEmpty()) result += stack.pop();
return result;
}
- spock测试用例
class StackApplyTest extends Specification {
@Unroll
def "convertDec2BinTest"() {
expect:
def result = StackApply.convertDec(number,system)
println result
if(system == 2) {
result == Integer.toBinaryString(number)
}else if(system == 8){
result == Integer.toOctalString(number)
}
where:
number|system
10|2
10|8
1111|8
2222|8
1|2
16|8
}
}
括号匹配问题
- 实现
//括号是否匹配问题,碰到左边括号进栈,碰到右边括号和出栈括号对比
//{[(
public static boolean checkBrackets(String input){
if( input == null || input.equals("")) throw new IllegalArgumentException("empty string");
var leftBrackets = "{[(";
var rightBrackets = "}])";
Stack<String> stack = new LinkStack<>();
for (int i = 0; i < input.length(); i++) {
var item = input.substring(i,i+1);
if(leftBrackets.contains(item)){
stack.push(item);
}
if(rightBrackets.contains(item)){
//直接映射判断
if(leftBrackets.indexOf(stack.pop()) != rightBrackets.indexOf(item)) return false;
}
}
return true;
}
- spock 测试用例
def "checkBracketsTest"(){
expect:
def result = StackApply.checkBrackets(input)
result == expectResult
where:
input|expectResult
"{(1)11}"|true
"{(1)11}{(1)11}{(1)11}{(1)11}{(1)11}{(1)11}{(1)11}{(1)11}{(1)11}"|true
"{(111}"|false
}
队列实现
树
实现
- 每个节点记录左右子节点