下压(LIFO栈)_API

r囧r小猫 2022-07-12 12:36 146阅读 0赞

**栈**，先进后出(**FILO**—First-In/Last-Out):能够动态调整数组大小的实现。

**LIFO栈**几乎达到了任意集合类数据类型的实现的**最佳性能**：  
1. 每项操作的用时都与集合大小无关。  
2. 空间需求总是不超过集合大小乘以一个常数。  
无泛型的缺点在于某些push()和pop()操作会调整数组的大小：这项操作的耗时和栈大小成正比。

import java.util.Iterator;
    
    public class ResizingArrayStack<Item> implements Iterable<Item> { 
    
        private Item[] a = (Item[]) new Object[1];
        private int N = 0;
    
        private boolean isEmpty() {
            return N == 0;
        }
    
        private int size() {
            return N;
        }
    
        /** * 扩容 */
        private void resize(int max) {
            // 将栈移动到一个大小为max的新数组
            Item[] temp = (Item[]) new Object[max];
            for (int i = 0; i < N; i++) {
                temp[i] = a[i];
            }
            a = temp;
        }
    
        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;
        }
    
        @Override
        public Iterator<Item> iterator() {
            return new ReverseArrayIterator();
        }
    
        private class ReverseArrayIterator implements Iterator<Item> { 
            private int i = N;
    
            @Override
            public boolean hasNext() {
                return i > 0;
            }
    
            @Override
            public Item next() {
                return a[--i];
            }
    
            public boolean hasNest() {
                return i > 0;
            }
    
            public void remove() {
    
            }
    
        }
    
    }

这份泛型的可迭代的Stack API的实现是所有集合类抽象数据类型实现的模板。它将所有元素保存在数组中，并动态调整数组的大小以保持数组大小和栈大小之比小于一个常数。