数据结构与算法(五,栈和栈的应用,递归思想)

栈

栈是只在尾部做添加和删除的线性表

栈的顺序结构方式

• 栈的顺序存储结构是使用数组实现的,Stack继承了Vector
• 添加元素时

public synchronized void addElement(E obj) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = obj;
    }

首先判断是否需要扩容
然后将elementCount位置即栈顶指针指向的位置,赋值为obj
然后将elementCount++,即栈顶指针上移一格,指向一格空地址

• 删除一个元素

 elementCount--;
 elementData[elementCount] = null; /* to let gc do its work */

首先将栈顶指针下移一格
然后将指针所指向的位置置空

• Vector和ArrayList的区别
  Vector是jdk1.0版的顺序表,当时考虑到要在很多场景使用,添加了大量的同步锁,是线程安全的
  但是后来发现,这些线程同步锁很多都用不到
  ArrayList是jdk1.2版本的,是去掉了同步锁的Vector

栈的链式结构方式

栈在计算机中的应用

1. 链表的倒序
   将链表存放到链式结构的栈中,进行入栈操作

s = first;//将链表头结点入栈
stack.top = s;
first = first.next();

2. 逆波兰表达式-->中缀表达式-->后缀表达式-->计算方式
   9+(3-1)X3+10/2
   标准四则运算表达式是中缀表达式

• 9 3 1 | + ( - )
• 9 3 1 - 3 | + X
• 9 3 1 - 3 X +10 2 | + /
  *9 3 1 - 3 X + 10 2 / +
• 计算机中首先将中缀表达式转换成后缀表达式
  转换方法:数字输出,符号入栈,括号匹配出栈,优先级高入栈,优先级低将栈内符号出栈,
• 计算后缀表达式
  数字入栈,符号就取两个数字出栈计算后再入栈
  9 3 1 | 3-1=2
  9 2 3 | 2X3 = 6
  9 6 | 9+6 = 15
  15 10 2 | 10/2 = 5
  15 5 | 15+5 = 20

递归的思想

• 程序调用自身
• 递归的边界条件,在满足边界条件之前,递归前进,满足边界条件之后,递归返回
• 将大型复杂问题分解成与原问题相似的规模小的问题

阶乘

• 前进段:n! = n*(n-1)!
• 边界条件1!=1
• 返回段:无

  public Long jc (int n){
        if (n<=1){
            return 1l;
        }else {
            return n*jc(n-1);
        }
    }

斐波那契数列

1 1 2 3 5 8
除前两项外,其他项等于前两项之和

• 前进段: f(n) = f(n-2)+f(n-1)
• 边界值:n<=1 n = 1
• 返回段:无

   public int fibonaaci(int n){
        if (n<=1){
            return 1;
        }else {
            return fibonaaci(n-2)+fibonaaci(n-1);
        }
    }

汉诺塔

将问题简化成两块砖(n1,n2),3根柱子(start,middle,end)
现将n2移动到middle,再将n1移动到end,再将n2移动到end

• 前进段: f(n-1,1,3,2)//n-1个通过第3根柱子移到第2根柱子
  f(1,1,2,3)//第n个通过第2根柱子移到第3根柱子
  f(n-1,2,1,3)//n-1个通过第1根柱子移到第3根柱子
• 边界值:f(1,1,2,3) = 1--->3
• 返回段:无

public void hannoi(int n,int start,int middle,int end){
        if (n<=1){
            System.out.println(start+"--->"+end);
        }else {
            hannoi(n-1,start,end,middle);
            System.out.println(start+"--->"+end);
            hannoi(n-1,middle,start,end);
        }
    }