public class SqStack {
    private Object[] stackElem;			//栈对象数组
    private int top;					//长度、下一个存储位置 等
}

public void push(Object x){
    if(top == stackElem.length){
        throw new RuntimeException("栈满");
    }else{
        stackElem[top] = x;
        top++;
    }
}

public void push(Object x){
    if(top == stackElem.length){
        throw new RuntimeException("栈满");
    }else{
        stackElem[top++] = x;
    }
}

public Object pop(){
    if(top == 0){
        return null;
    }else{
        top--;
        return statckElem[top];
    }
}

public boolean isEmpty(){
    return top == 0;
}
public Object pop(){
    if(isEmpty()){
        return null;
    }else{
        return statckElem[--top];
    }
}

public class LinkStack {
    private Node top;			//栈顶指针
}

public void push(Object x){
    Node p = new Node(x);
    p.next = top;
    top = p;
}

public Object pop(){
    if(top == null){
        return null;
    }else{
        Node p = top;
        top = top.next;
        return p.data;
    }

}

package hanoi;

public class TestHanoi {
    private static int count = 0;
    /**
     *
     * @param n 需要移动的盘子数
     * @param x 第一个柱子 起始
     * @param y 第二个柱子 过渡
     * @param z 第三个柱子 最后
     */
    public static void hanoi(int n, char x, char y , char z) {
        if(n == 1) {      //只有一个盘子
            move(x, 1, z);
        } else {
            hanoi(n-1, x, z ,y);     // n上面的盘子，从x柱子，通过z柱子，移动到y柱子
            move(x, n, z);              //n盘子，从x柱子，移动到z柱子
            hanoi(n-1, y, x, z);    // n上面的盘子目前在y柱子，从y柱子，通过x柱子，移动到z柱子。
        }
    }

    /**
     *
     * @param x 第一个柱子
     * @param n 需要移动的盘子号
     * @param z 第三个柱子
     */
    private static void move(char x, int n, char z) {
        count++;
        System.out.println("第"+count+"次移动"+n+"号盘子，从"+x+"柱子到"+z+"柱子");
    }

    public static void main(String[] args) {
        hanoi(4,'x','y','z');
    }
}

public Class CircleQueue {
    private Object[] queueElem;		//物理数组
    private int front;				//队首
    private int rear;				//队尾
}

public void offer(Object x) {
    if( (rear+1) % queueElem.length == front ) {  // 1.判断，如果已经满了，抛异常
        throw new RuntimeException('队列满了');
    } else {
        queueElme[ rear ] = x;					 // 2.没有满进行入队操作
        rear = (rear + 1) % queueElem.length;	 // 3.队尾rear累加1，但最后时需要归零
    }
}

public Object poll() {
    if( front == rear ) {						// 判断 空 返回null
        return null;
    } 
    
    Object data = queueElem[front];				// 如果不为空，获得队首front元素
    front = (front + 1) % queueElem.length;		// 队首+1，且需要归零  
    return data;
}

public class LinkQueue {
    private Node front;		//队首（出队/删除）
    private Node rear;		//队尾（入队/插入）
}

public void offer(Object x) {
    Node p = new Node(x);
    if(front == null) {		//空
        front = rear = p;
        //front = p;
        //rear = p;
    } else {				//非空
        rear.next = p;		//1.尾指针的指针域指向新结点
        rear = p;			//2.尾指针指向队尾
    }
}

public Object poll() {
    if(front != null) {		//非空
        Node p = front;				//记录队首元素
        front = front.next;			//队首移动到下一个
        if(p == rear) {					//只有一个元素时，队首和队尾相同
            rear = null;				//队首已经是null，队尾也应该是null
        }
        return p.data;				//返回之前队首元素的数据
    } else {				//空
        return null;
    }
}

/*
  { elem: a, priority: 1}
*/
public class PriorityData {
    public Object elem;				//数据元素的值
    public int priority;			//结点的优先级
}

public class PriorityQueue {
    private Node front;		//队首
    private Node rear;		//队尾
}

public void offer(PriorityData x) {
    Node s = new Node(x);				//构建新结点
   	// 如果空
    if(front == null) {		//空
        front = rear = s;
    } else {				//非空
        // 1) 移动：按照优先级进行移动，优先级大就需要继续移动
        Node p = front;		//用于记录前驱（之前的）
        Node q = front;		//用于记录下一个
        while( q != null && (x.priority >= q.data.priority )) {
            p = q;			//记录前驱
            q = p.next;
        }
        
        // 2) 插入
        if(q==front) {			// 2.1 队首
            s.next = front;			//新结点s指向队首front
            front = s;				//队首指针，指向队列的开始
        } else if (q == null) {	// 2.2 队尾
            rear.next = s;			//队尾指针域next,指向新结点
            rear = s;				//队尾指针，指向队尾
        } else {				// 2.3 中间
            p.next = s;
        	s.next = q;
        }
    }
}

package recursion;


public class TestSum {
    public static void main(String[] args) {
        System.out.println(sum(10));
    }

    /**
     * 求1-n的和
     * @param n
     * @return
     */
    private static int sum(int n) {
        if(n == 1) {
            return 1;
        }
        return n + sum(n-1);
    }
}

package recursion;


public class TestFactorial {
    public static void main(String[] args) {
        System.out.println(factorial(4));
    }

    private static int factorial(int n) {
        if(n == 1) {
            return 1;
        }
        return n * factorial(n-1);
    }
}

package recursion;


public class TestFibonacci {
    public static void main(String[] args) {
        // 斐波那契数列
        for(int i = 0 ; i <= 10 ; i ++) {
            System.out.print(fibonacci(i) + "、");
        }
    }

    /**
     * 计算斐波那契数列的第n项
     * f(0) = 0
     * f(1) = 1
     * ...
     * f(n) = f(n-1) + f(n-2)
     * @param n
     * @return
     */
    private static int fibonacci(int n) {
        if(n == 0) {
            return 0;
        }
        if(n == 1) {
            return 1;
        }
        return fibonacci(n-1) + fibonacci(n-2);
    }
}