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?

Note: Stack is obsolete, you should use a Deque instead (for instance an ArrayDeque — fge
– fge, Commented Jun 7, 2013 at 20:54
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. — nhahtdh
– nhahtdh, Commented Jun 7, 2013 at 20:58
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 — nachokk
– nachokk, Commented Jun 7, 2013 at 21:00

Community · Accepted Answer · 2023-11-10 19:48:45Z

36

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.

edited Nov 10, 2023 at 19:48

CommunityBot

11 silver badge

answered Jun 7, 2013 at 20:58

Bill the Lizard

407k213 gold badges579 silver badges892 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

vincent mathew Over a year ago

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

Bill the Lizard Over a year ago

@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 Over a year ago

@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 Over a year ago

@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 Over a year ago

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.

Bashir · Accepted Answer · 2014-12-15 19:33:06Z

14

You should use Deque instead of Stack.

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

See Oracle Doc

answered Dec 15, 2014 at 19:33

Bashir

2763 silver badges10 bronze badges

Comments

Shamim Hafiz - MSFT · Accepted Answer · 2013-06-07 21:01:30Z

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.

answered Jun 7, 2013 at 21:01

Shamim Hafiz - MSFT

22.2k44 gold badges122 silver badges183 bronze badges

Comments

William Han · Accepted Answer · 2015-07-14 19:31:11Z

2

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

edited Jul 14, 2015 at 19:31

answered Jul 14, 2015 at 19:19

William Han

213 bronze badges

Comments

tbraun · Accepted Answer · 2014-06-19 09:52:19Z

1

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

answered Jun 19, 2014 at 9:52

tbraun

2,66633 silver badges26 bronze badges

Comments

Donald Raab · Accepted Answer · 2017-02-13 20:06:07Z

1

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.

edited Feb 13, 2017 at 20:06

Donald Raab

6,8362 gold badges40 silver badges47 bronze badges

answered Sep 3, 2013 at 15:22

Craig P. Motlin

26.8k18 gold badges105 silver badges128 bronze badges

Comments

ceving · Accepted Answer · 2020-09-15 10:28:14Z

0

Instead of a Stack you can use a LinkedList and use the push and pop methods.

answered Sep 15, 2020 at 10:28

ceving

24.2k15 gold badges120 silver badges201 bronze badges

Comments

Allan Juan · Accepted Answer · 2022-10-22 20:33:33Z

Here's a stack implementation with built-in reverse order iteration.

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

Collectives™ on Stack Overflow

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

8 Answers 8

5 Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

8 Answers 8

5 Comments

Comments

Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related