栈的基本操作

栈是一种基于后进先出(LIFO)策略的集合类型,例如上网点击超链接浏览器会跳到另一个页面(将它压入栈中),点击后退可以回到以前的页面(从栈中弹出),栈的后进先出策略正好提供了这种所需要的行为.当遍历栈中的元素时,元素的处理顺序和它们被压入的顺序正好相反.

定容栈

实现起来比较简单,它指定了栈的容量大小,当N=0时栈为空,栈的顶部位于a[N-1],当栈满时插入元素栈会上溢.

public class FixedCapacityStackOfStrings implements Iterable<String> {
    private String[] a;  // holds the items
    private int N;       // number of items in stack

    // create an empty stack with given capacity
    public FixedCapacityStackOfStrings(int capacity) {
        a = new String[capacity];
        N = 0;
    }

    public boolean isEmpty()            {  return N == 0;                    }
    public boolean isFull()             {  return N == a.length;             }
    public void push(String item)       {  a[N++] = item;                    }
    public String pop()                 {  return a[--N];                    }
    public String peek()                {  return a[N-1];                    }
    public Iterator<String> iterator()  { return new ReverseArrayIterator(); }


    public class ReverseArrayIterator implements Iterator<String> {
        private int i = N-1;

        public boolean hasNext() {
            return i >= 0;
        }

        public String next() { 
            if (!hasNext()) throw new NoSuchElementException();
            return a[i--];
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }
    }


    public static void main(String[] args) {
        int max = Integer.parseInt(args[0]);
        FixedCapacityStackOfStrings stack = new FixedCapacityStackOfStrings(max);
        while (!StdIn.isEmpty()) {
            String item = StdIn.readString();
            if (!item.equals("-")) stack.push(item); 
            else if (stack.isEmpty())  StdOut.println("BAD INPUT"); 
            else                       StdOut.print(stack.pop() + " ");
        }
        StdOut.println();

        // print what's left on the stack
        StdOut.print("Left on stack: ");
        for (String s : stack) {
            StdOut.print(s + " ");
        }
        StdOut.println();
    } 
}

View Code

能够动态调整数组大小的实现

我们修改数组的实现,动态调整a[]的大小,使得它即足以保存所有元素,又不至于浪费过多空间.

1.在push()操作中,检查数组的大小.具体说就是检查栈大小N和数组长度a.length是否相等,如果相等则判断没有多余空间,此时将数组大小加倍,然后可以像以前一样用 a[N++] = item 进行插入操作了.

2.在pop()操作中,首先删除栈顶元素,如果数组太大我们就将它长度减半,检测条件是栈的大小是否小于数组的四分之一(因为数组长度减半之后,它的状态约为半满,在下次需要改变数组大小之前仍能进行多次push()和pop()操作).

在这个实现中,栈永远不会溢出,使用率也不会低于四分之一(除非栈空,这是数组大小为1).

java的垃圾回收策略是回收所有无法访问的内存,在pop()实现中,被弹出的元素仍然存在于数组中,这个元素不会再被访问,但java的垃圾收集器不知道这一点,除非引用被覆盖,这种情况称为游离.要避免对象游离很简单,只要把被弹出的数组元素值设为null.

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; }
    //获取栈大小
    public int size(){ return N;}
    //调整栈大小,将栈元素移动到一个大小为max的数组中
    private void resize(int 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;
    }
    
    //实现迭代器
    public Iterator<Item> iterator(){
        return new ReverseArrayIterator();
    }
    
    //支持后进先出的迭代
    private class ReverseArrayIterator implements Iterator<Item>{
        private int i = N;
        public boolean hasNext(){
            return i > 0;
        }
        public Item next(){
            return a[--i];
        }
        public void remove(){}
    }
}

View Code

性能:每项操作用时都与集合大小无关,空间需求总是不超过集合大小乘以一个常数. 缺点在于某些push()和pop()会调整数组的大小,这项操作耗时和栈大小成正比.

链表实现

所需空间总是和集合大小成正比.

操作所需时间总是和集合大小无关.

public class Stack<Item>{
    
    private Node first;    //栈顶
    private int N;    //元素数量
    //节点定义
    private class Node{
        Item item;
        Node next;
    }
    public boolean isEmpty(){ return first == null ;}
    public int size(){ return N;}
    //入栈
    public void push(Item item){
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
        N++;
    }
    //出栈
    public Item pop(){
        Item item = first.item;
        first = first.next;
        N--;
        return item;
    }      
}

View Code