return new ReverseArrayIterator(); 51    } 52 53    // an iterator, doesn't implement remove() since it's optional 54    private class ReverseArrayIterator implements Iterator<String> { 55        private int i = n-1; 56        public boolean hasNext()  { return i >= 0;                              } 57        public void remove()      { throw new UnsupportedOperationException();  } 58 59        public String next() { 60            if (!hasNext()) throw new NoSuchElementException(); 61            return items[i--]; 62        } 63    } 64 65 66 67   /*************************************************************************** 68    * Test routine. 69    ***************************************************************************/ 70    public static void main(String[] args) { 71        ResizingArrayStackOfStrings stack = new ResizingArrayStackOfStrings(); 72        while (!StdIn.isEmpty()) { 73            String item = StdIn.readString(); 74            if (!item.equals("-")) stack.push(item); 75            else if (!stack.isEmpty()) StdOut.print(stack.pop() + " "); 76        } 77        StdOut.println("(" + stack.size() + " left on stack)"); 78    } 79}

 

7

总结

 

以上总结了栈的两种基本实现方法，都是借助数组实现，一种是静态的，另一种可以动态扩容。这是最基本的实现思路，可以仔细体会下，能写出这些代码来，如果在面试中问到栈的知识，告诉面试官这些东西，会给你加不少分。

 

基于数组实现的栈结构都不是理想的，因为动态扩容时，每次都要复制老元素到新的位置上，这是耗费时间的。有没有更高效的实现方法呢？  

 

请看接下来的推送。