foreach and stack, iterating from the bottom-up?

[WP]

Hello, I just tried a foreach loop with a Stack (Stack<String> to be
precise) and I was a bit surprised that it seems to iterate from the
bottom up. I thought it would go from the top down because, with
stacks, you usually have to remove what's on the top to get to the
bottom. Note that I didn't want to empty the stack itself, just
iterate over it. Why was it implemented this way? It's not an actual
problem, I simply adapted my logic in the method to this behavior,
but, as I said, I was surprised.

- WP

 

[Owen Jacobson]

Hello, I just tried a foreach loop with a Stack (Stack<String> to be
precise) and I was a bit surprised that it seems to iterate from the
bottom up. I thought it would go from the top down because, with
stacks, you usually have to remove what's on the top to get to the
bottom. Note that I didn't want to empty the stack itself, just
iterate over it. Why was it implemented this way? It's not an actual
problem, I simply adapted my logic in the method to this behavior,
but, as I said, I was surprised.

- WP

java.util.Stack is implemented by extending Vector, which is an auto-
resizing (and synchronizing) wrapper over an array. For efficiency,
stack items are added to and removed from the end of the array; the
iteration order as inherited from Vector is from the beginning of the
array.

Note this snippet in the documentation of Stack:

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. For example:

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

Using a Deque as your stack gives you more control over which order
iteration goes in: if you push and pop at the front of a deque, then
iteration over it will proceed from the top of the stack down; if you
push and pop at the back, then iteration will proceed from the bottom
up.

The Stack, Vector, Hashtable, and Enumeration classes have been
superseded by the Collections framework. Aside from Java 1
compatibility, there are no good reasons to use these classes in new
code.

-o

 

[Daniel Pitts]

Hello, I just tried a foreach loop with a Stack (Stack<String> to be
precise) and I was a bit surprised that it seems to iterate from the
bottom up. I thought it would go from the top down because, with
stacks, you usually have to remove what's on the top to get to the
bottom. Note that I didn't want to empty the stack itself, just
iterate over it. Why was it implemented this way? It's not an actual
problem, I simply adapted my logic in the method to this behavior,
but, as I said, I was surprised.

- WP

Stack extends Vector, Vector implements List, List.iterator has very
specific semantics.

Also, generally you don't "Iterate" stacks, you push onto and pop from them.

Third, Use LinkedList or ArrayList instead, Vector is deprecated.

 

[Knute Johnson]

Third, Use LinkedList or ArrayList instead, Vector is deprecated.

No it's not.

 

[Leonard Milcin]

No it's not.

It is considered a good practice to avoid whenever possible the use of
Vector or generic collections without supplying type information.

Regards,
Leonard

 

[Arne Vajhøj]

No it's not.

It is not deprecated in the Java sense of the word.

But I would consider it best practice to use ArrayList instead.

Arne

 

[Mike Schilling]

Most likely an unwelcome consequence of implementing Stack
as a subclass of Vector. Clearly, the "working end" of the
Stack would be at the high-index end of the Vector (to avoid
a lot of element copying), and Vector's iterator() method
naturally traverses from zero upwards, so ...

There's probably an object lesson in here somewhere.

Nicely phrased.

 

[Mike Schilling]

Stack extends Vector, Vector implements List, List.iterator has very
specific semantics.

Also, generally you don't "Iterate" stacks, you push onto and pop from
them.

It can make sense to iterate over a stack:

Say you're writing a compiler for a language that allows variables to be
declared in an inner scope, e.g.

int i;
{
float i;
{
String i;
...
char c = i.getChar(2);
}
}

One obvious way to implement this is with a stack of symbol tables. Every
time you see "{", you create a new table and push it onto the stack. Every
time you see "}", you pop the top table off the stack. To look up a
variable "v", you iterate over the stack, from top to bottom, and keep
looking for v until you find a match. As the OP noted, you need to iterate
from stack top to stack bottom. And as a few folks have noted, the actual
behavior (iteration from bottom to top) probably comes from Stack's being
implemented as a subclass of a List rather than from an analysis of what's
useful or expected.

 

[Knute Johnson]

It is not deprecated in the Java sense of the word.

But I would consider it best practice to use ArrayList instead.

Arne

The only good argument for not using Vector, since it is a full member
of the Java Collections Framework, is the performance hit from
synchronization. In modern JVMs the performance cost for un-contended
access is very small. And if synchronization is necessary for your
application then Vector is the simpler approach.

I did a simple test to see what the performance looked like on my
computer. I wrote a program to create an ArrayList or Vector, add
200,000 String elements and then remove them, one at a time from the top
of the list. There was no appreciable difference in execution time
between Vector, ArrayList or ArrayList synchronized with the
Collections.synchronizedList() method.

And as we all know, if performance is really the issue, then any list is
a poor choice compared to an array.

I would be willing to bet that the bandwidth used in this never ending
discussion is a bigger performance hit than using Vector.

 

[Arne Vajhøj]

The only good argument for not using Vector, since it is a full member
of the Java Collections Framework, is the performance hit from
synchronization. In modern JVMs the performance cost for un-contended
access is very small. And if synchronization is necessary for your
application then Vector is the simpler approach.

I did a simple test to see what the performance looked like on my
computer. I wrote a program to create an ArrayList or Vector, add
200,000 String elements and then remove them, one at a time from the top
of the list. There was no appreciable difference in execution time
between Vector, ArrayList or ArrayList synchronized with the
Collections.synchronizedList() method.

And as we all know, if performance is really the issue, then any list is
a poor choice compared to an array.

I would be willing to bet that the bandwidth used in this never ending
discussion is a bigger performance hit than using Vector.

I don't think the performance is a good reason in most cases.

But you have two classes that implement the same interface with
more or less the same semantics.

It makes sense to use the same class instead of both.

The Vector class is a leftover from Java 1.0/1.1 and I have
no doubt that the intention from SUN is for people to use
ArrayList instead of Vector.

I am also convinced that most people use ArrayList which also
points to using it.

And thirdly the synchronized part of Vector often misleads
developers to write thread unsafe code, because they think
the use of Vector handles it, when it very rarely does.

Arne

 

[Andreas Leitgeb]

It's possible to achieve what you want, ...

If the OP was using a sufficiently new Java (>=1.6), then he
could use method "descendingIterator()" offered by a couple
of the collection classes/interfaces. (Deque,NavigableSet,
LinkedList,TreeSet,...)

the descendingIterator() is another argument in favour of
allowing for-loops with iterators, not just iterables.

For the time being (since "for" does not directly work with
iterators) the following short but ugly code works around:

for (Integer i: new Iterable<Integer>() { public Iterator<Integer> iterator() { return dequeVar.descendingIterator(); } } )
{ ... loop body ... }

Any typoes found become property of the finder.

 

[Andreas Leitgeb]

For loops are allowed with iterators. The enhanced for loop is syntactic
sugar designed for one common use, only.

Technically 100% correct.
It's just the fact behind the "only" which I'm ranting about.

Just do:
for ( Iterator <Foo> iter = deq.descendingIterator(); iter.hasNext(); )
{ Foo foo = iter.next();

Ok, it's about equally ugly, than mine, but I admit it's more efficient.
This is the idiom, for which to avoid the syntactic sugar was added.
Even more such idioms could have easily been sugar-coated as well, but
were left out, back then in the days of 1.5, probably because those
descending iterators were only "invented" later (with 1.6) for Java.

The whole concept of the Iterable interface has one sore point, that
it cannot deal with a pluralism of ways to iterate something.
It's the same "problem" for which Comparator's exist besides
the Comparable interface, except of course, that this thread
is only about sugar coating, not about new functionality.

Extending the syntactic sugar to not be crippled by that limitation
of Iterable, would be a "good thing", imo. However, I admit that it
is *not* a necessity, as it may have looked like from my previous posting.

PS: My sample was already much smaller than the one I followed up to.

 

[Arne Vajhøj]

Really, not even any reason.

It is a reason traditional often given.

Except that Vector contains warts leftover from pre-Collections days.

And fourth, Vector contains machinery outside the Collections framework,
which is superfluous to that in the framework. Why use a class that has
methods and interfaces (Enumeration, protected fields) that you don't
need? It is just more stuff to manage - better to use the leaner,
meaner List and its proper implementations.

If we were to dump all classes that had more methods than their
"primary" interface, then we would be missing a lot of classes !

Arne

 

[Roedy Green]

It's not an actual
problem, I simply adapted my logic in the method to this behavior,
but, as I said, I was surprised.

Look inside how Stack is implemented. If uses an array, naturally
element 0 is the bottom of the stack.

 

[Arne Vajhøj]

Nope. Just the ones for which a suitable replacement is in the standard
API.

But if that rule were to be followed in its uttermost consequence, then
new classes would be written where extra functionality existed and in
the end interfaces would not be necessary at all.

You do:

Map m = new HashMap();

to be sure that you do not use any methods on m that are
not in Map.

But then you can not also argue that HashMap should not have any
other methods.

Arne