java.util.Stack的迭代器中是否有错误？

Question

今天我试图推动java.util.Stack类，然后使用Iterator迭代(不使用pop)通过项目。我期待后进先出属性，但感到惊讶。

这是我正在尝试的代码。

import java.util.*;
import java.util.Stack;
public class Main {
    public static void main(String[] args) {
        RobStack<Integer> rstack = new RobStack<Integer>(); // Correct Implementation
        Stack<Integer> jstack = new Stack<Integer>(); // Default Java Implementation
        rstack.push(0); jstack.push(0);
        rstack.push(1); jstack.push(1);
        rstack.push(2); jstack.push(2);
        rstack.push(3); jstack.push(3);
        System.out.print("Algo Stack: ");
        for (int i : rstack)
            System.out.print(i + " ");
        System.out.print("nJava Stack: ");
        for (int i : jstack)
            System.out.print(i + " ");
    }
}

上述程序的输出如下所示:

Algo Stack: 3 2 1 0 
Java Stack: 0 1 2 3 

在上面的代码中，jstack使用默认的Java实现，rstack使用Robert Sedgewick为他的算法类提供的实现。我发现Robert教授的实现工作得很好，但java.util.Stack的实现失败了。

这是一个错误还是由设计?

Answer 1

参见Bug ID 4475301: RFE: java.util.Stack.iterator()迭代方式错误。这种行为是(糟糕的)设计。Java的内置Stack迭代器方法是从其他类继承的，因此它们的行为与您期望的不同。

Answer 2

你应该使用Deque而不是Stack。

Deque<Integer> stack = new ArrayDeque<Integer>();

参见Oracle Doc

Answer 3

原则上，您不应该遍历Stack，而应该只在顶部推送或从顶部弹出。至于实际实现，大多数语言，包括Java，使用另一个collection type来实现Stack。从严格的要求来看，它应该允许恒定时间的push, top and pop操作。

任何额外的特性(或错误)，应该被忽略，而不是依赖于编码。

Answer 4

也许，您可以使用.get()从上到下打印堆栈中的项。

Stack<Integer> stack = new Stack<Integer>();
stack.push(3);
stack.push(2);
stack.push(1);
// print from top to bottom
for(int i = stack.size() - 1; i >= 0; i--){
   System.out.println(stack.get(i));
}
/*
output
1
2
3
*/

Answer 5

Stack从AbstractList继承. listtiterator ()，允许逆序迭代。

Stack<Integer> stack = new Stack<Integer>();
stack.push(1);
stack.push(2);
stack.push(3);
for (ListIterator<Integer> iterator = stack.listIterator(stack.size()); iterator.hasPrevious();) {
    Integer integer = iterator.previous();
    System.out.println(integer);
}
// Output: 3 2 1

Answer 6

Eclipse Collections包含一个可变堆栈实现，其中迭代器从上到下返回值。这段代码打印3,2,1。

MutableStack<Integer> stack = ArrayStack.newStack();
stack.push(1);
stack.push(2);
stack.push(3);
for (Iterator<Integer> iterator = stack.iterator(); iterator.hasNext(); )
{
    Integer each = iterator.next();
    System.out.println(each);
}

MutableStack不扩展MutableCollection或Collection，所以你不能从堆栈的中间删除，例如。实现内部迭代模式的方法，如forEach()、select()、collect()、anySatisfy()、allSatisfy()等，也从上到下处理元素。下面的代码输出相同的内容。

stack.forEach(Procedures.println(System.out));

注意:我是Eclipse集合的提交者。

Answer 7

您可以使用LinkedList代替Stack，并使用push和pop方法。

Answer 8

这是一个内置逆序迭代的堆栈实现。

public class PowerStack<T> implements Iterable {
    private List<T> items = new ArrayList<T>();
    
    void push(T item) {
        items.add(item);
    }
    
    void pop() {
        this.items.remove(this.topElementIndex());
    }
    
    T top() {
        return items.get(this.topElementIndex());
    }
    
    private int topElementIndex() {
        return items.size() - 1;
    }
        
    @Override
    public Iterator<T> iterator() {
        return new ReverseOrderIterator<T>(items);
    }
}
public class ReverseOrderIterator<T> implements Iterator<T> {
    private List<T> items;
    private int index;
    
    public ReverseOrderIterator(List<T> items) {
        this.items = items;
        this.index = items.size() - 1;
    }
    
    public boolean hasNext() {
        return this.index > 0;
    }
    
    public T next() {
        return this.items.get(index--);
    }
}