咸糖记录编程的地方

Do what you love and the money will follow.

目录
算法 栈的实现
/  

算法 栈的实现

  • 泛型: 集合类型的抽象数据类型 的一个关键性质我们可以存储任何类型的数据
  • 自动装箱: 将一个原始的数据类型转换为一个封装类型叫做自动装箱
package Chapter_1;

import algs4.StdIn;
import algs4.StdOut;

public class FixedCapacityStackOfString {
    private String[] a;
    private int N;
    public FixedCapacityStackOfString(int cap) {
        /**
          创建一个容量为cap的空栈
         **/
        a = new String[cap];
    }
    public boolean isEmpty(){
        return N==0;
    }
    public void push(String item){
        a[N++] = item;
    }
    public int size(){
        return N;
    }
    public String pop(){

        return a[--N];
    }

    public static void main(String[] args) {
        FixedCapacityStackOfString s;
        s = new FixedCapacityStackOfString(100);
        while (!StdIn.isEmpty()){
            String item = StdIn.readString();
            if (!item.equals("-")){
                s.push(item);
            }
            else if (!s.isEmpty()){
                StdOut.print(s.pop()+" ");
            }
        }
        StdOut.print("("+s.size()+"left on stack");
    }

}

主要采用指针进行栈顶的操作

push方法进行修改 当栈满了就将该栈
的长度*2

public void resize(int max) {
        Item[] temp = (Item[]) new Object[max];
        for (int i = 0; i < max; i++) {
            temp[i] = a[i];
        }
        a = temp;
    }
    public void push(Item item){
        if (N == a.length) resize(2*a.length);
        else a[N++] = item;
    }

使栈的使用率永远不会低于1/4

public Item pop(){
        Item item = a[--N];
        a[N] = null;
        if(N>0 && N==a.length/4) resize(a.length/2);
        return item;
    }
  • 垃圾游离:当一个用例不需要这个对象的时候
    数组中还是会存留这个对象 java的垃圾回收器无法
    知道这一点 除非这个引用被覆盖
    我们这里需要将游离的对象设置为null即可

  • 嵌套类是可可以访问到实例的变量的

public  class  ReveseArrayIterator implements Iterator<Item>{
        private int i = N;
        public boolean hasNext(){
            return i>1;
        }

        public Item next(){
            return a[i--];
        }
        public void remove(){

        }

    }
package Chapter_1;

import java.util.Iterator;

public class ResizingArrayStack<Item> implements Iterable<Item> {
    private  Item[] a = (Item[]) new Object[1];
    private int N = 0;
    public boolean isEmpty(){
        return N == 0;
    }
    public int size(){
        return N;
    }
    public void resize(int max){
        Item[] temp = (Item[]) new Object[max];
        for (int i = 0; i <a.length ; i++) {
            temp[i] = a[i];
        }
    }
    public void push(Item item){
        if(N==a.length) resize(2*a.length);
        a[N++] = item;
    }
    
    public Item pop(){
        Item item = a[N--];
        a[N] = null;
        if (N>0 && N == a.length/4) resize(a.length/2);
        return item;
    }
    private class ReverserArrayIterator implements Iterator{
        private int i = N;
        
        public boolean hasNext(){
            return i >0;
        }
        public Item next(){
            return a[--i];
        }
        public void remove(){}
        
    }
    @Override
    public Iterator<Item> iterator() {
        return new ReverserArrayIterator();
    }
    
}

这个stack api 的实现是所有集合类抽象数据类型的
模板 所有元素在数组中 并且动态调整栈和数组的大小


标题:算法 栈的实现
作者:xiantang
地址:http://xiantang.info/articles/2019/06/03/1559551102064.html

评论