JAVA数据结构与算法基础学习笔记(二)

栈

1. 栈的定义
   栈是一种操作受限制的线性表，将允许进行插入、删除的一端称为栈顶，另一端称为栈底。
2. 栈的分类
   栈主要分为静态栈和动态栈，静态栈类似于数组，而动态栈类似于链表，但只能对链表的一端进行操作。这里主要说一下静态栈。
3. 静态栈的表示

#define stack_size 100
typedef int SDataType;//假设栈内元素为整型。

typedef struct stack

{

   SDataType array[stack_size];

   int top;

}stack;

1. 栈的操作

public class Class_Stack {

    private int  Length;//定义的长度
    private int  S_top;//栈顶位置
    private int[] stack ;//用数组表示



    //初始化栈 ，只需要传入栈的长度
    public Class_Stack(int length) {
        super();
        Length = length;
        S_top =0;
        stack = new int[Length];
    }

    //判断栈是否为满
    public     boolean isFull()
    {
        if(S_top==Length)
        {
            return true;
        }
        return false;
    }

    //判断栈是否为空
    public boolean isEmpty()
    {
        if(S_top==0)
        {
            return true;
        }
        return false;
    }

    //入栈
    public void S_push(int x)
    {
        if(!isFull())
        {
            stack[S_top] = x;
            S_top++;
        }else {
            System.out.println("栈已满");    
        }
    }

    //出栈
    public int S_pop()
    {
        int ele=-1;
        if(!isEmpty())
        {
             ele=stack[S_top-1];
             S_top--;
        }
        return ele;
    }

    //打印栈元素
    public void S_print()
    {
        for(int i=0;i<S_top;i++)
        {
            System.out.println(stack[i]);
        }
    }
}

队列

1. 入队
2. 出队
3. 判断是否为空

   单链表

4. 什么是单链表
5. 节点的删除
6. 节点的插入

   循环链表

   双循环

   递归

7. 什么是递归？
8. 斐波那契数列
9. 汉诺塔问题

package demo3;
public class TestHanoi{
  public static void main(String[] args){
    hanoi(5,'A','B','C');
  }

  /**
  * @param n 共有N个盘子
  * @param from 开始的柱子
  * @param in 中间的柱子
  * @param to 目标柱子
  */

  public static void hanoi(int n,char from,char in,char to){
    //只有一个盘子
    if(n==1){
      System.out.println("第1个盘子从"+from+"移动到"+to);
      //无论有多少个盘子，都认为只有两个。上面的所有盘子和最下面一个盘子
    }else{
      //移动上面所有的盘子到中间位置
      hanoi(n-1,from,to,in);
      //移动下面的盘子
      System.out.println("第"+n+"个盘子从"+from+"移动"+to);
      //把上面的所有盘子从中间位置移动到目标位置
      hanoi(n-1,in,from,to);
    }
  }
}