Is there a bug in java.util.Stack's Iterator?

问题:

Today I was trying to push in java.util.Stack class and then use the Iterator to iterate (without using pop) through the items. I was expecting LIFO property but got surprised.

Here is the code that I was trying.

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 + " ");
    }

}

The output the above program is given below:

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

In the above code jstack uses the default Java implementation and rstack uses the implementation provided by Robert Sedgewick for his Algorithm class. I found that Prof. Robert's implementation works fine but the java.util.Stack implementation fails.

Is it a bug or is it by design?

回答1:

See Bug ID 4475301 : RFE: java.util.Stack.iterator() iterates the wrong way. This behavior is by (bad) design. Java's built-in Stack iterator methods are inherited from other classes, so they don't behave as you'd expect.

回答2:

You should use Deque instead of Stack.

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

See Oracle Doc

回答3:

Well by principle, you should not iterate over a Stack, but only push on top or pop from top. As for actual implementation, most languages, including Java, use another collection type to implement a Stack. From strict requirements point of view, it should allow constant time push, top and pop operation.

Any additional features (or bug in this case), should just be ignored and not relied upon for coding.

回答4:

Perhaps, you can use .get() to print items within stack from top to bottom.

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
*/

回答5:

Eclipse Collections includes a mutable stack implementation where the iterator returns values from top to bottom. This code prints 3, 2, then 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 does not extend MutableCollection or Collection, so that you can't remove from the middle of the stack, for example. Methods that implement internal iteration patterns like forEach(), select(), collect(), anySatisfy(), allSatisfy(), etc. also process elements from top to bottom. This code prints the same thing.

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

Note: I am a committer for Eclipse collections.

回答6:

Stack inherits .listIterator() from AbstractList which allows inverse order iteration.

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