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

Question

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?

Solution 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.

Solution 2

You should use Deque instead of Stack.

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

See Oracle Doc

Solution 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.

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

Solution 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.

View more solutions

Comments

[fge]

Note: Stack is obsolete, you should use a Deque instead (for instance an ArrayDeque

[jtomaszk]

And what if you use pop() operation?

[nhahtdh]

In support of fge's comment, in the doc of Stack class: A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.

[nachokk]

see pop() Returns: The object at the top of this stack (the last item of the Vector object). the last item , so here u realize that is not the first in the structure inside, so when u iterate u should make a reverse iteration hihi, very bad design

[vincent mathew]

Why didn't they correct the bug when it can be done by just overriding the Iterator method?

[Bill the Lizard]

@vincentmathew Yes, they could have overridden the iterator() method just like in Prof. Sedgewick's code that you linked to in order to make it iterate in LIFO order (assuming the same internal representation).

[vincent mathew]

@BilltheLiazard Maybe they could not have. "It was an incorrect design decision to have Stack extend Vector ("is-a" rather than "has-a"). We sympathize with the submitter but cannot fix this because of compatibility."

[Bill the Lizard]

@vincentmathew Even if they had a different internal representation for the Stack (which is probable; I think they use an expanding array approach), they could have come up with some iterator() method that iterates in the expected order. I guess iteration order isn't really a part of the design contract of a stack data structure, but it still seems like a poor choice to me.

[MTilsted]

I know this is a very very old thread, but I just wanted to note that they could not invert the iterator, because that would break any code, which accepted a Vector if you gave that method a Stack. Which just goes to show that a Stack is not a vector, and it should not have extended Vector.