Reversed Stack Iterator

Question

I was wondering how can I iterate over the elements of a Stack starting from the top and going down without using any additional memory. I believe that the default iterator() goes from bottom to top. I noticed also that for Deque there is a descendingIterator. I haven't been able to find anything similar to this for a stack. I was just wondering whether is possible to do that, nothing in particular. If this is not possible which other Java data structures offer the functionality of a Stack with the ability the iterate it backwards (except Deque ofc)?

What's your intention? If you try to do that, then you shouldn't use a stack to begin with. — Luiggi Mendoza, Nov 14 '13 at 15:29
This seems like an odd choice. Why use a FILO when you want FIFO functionality? — Dragondraikk, Nov 14 '13 at 15:30
If you understand that a [stack](http://en.wikipedia.org/wiki/Stack_(abstract_data_type)) only gives you the item at the top (or bottom), then you should already understand the answer. And people here is not flaming, you even got an answer. Looks like your problem was thinking about what structure you use to implement the stack and using the power of this structure for different problems. If you see the structure as a stack (not as its implementation), then this isn't possible. If you see the structure as an array or double linked list, then it is possible. — Luiggi Mendoza, Nov 14 '13 at 15:39
@lnwvr The ability to iterate over a `Stack` is an accident (of the fact that it subclasses `Vector`---it actually violates [Liskov Substitution Principle](http://en.wikipedia.org/wiki/Liskov_substitution_principle)), and not a part of its design. If you really want to exploit this accident to the max, you can just use `listIterator(stack.size())` and use `hasPrevious()` and `previous()` on the returned `ListIterator`. But again, none of that is part of `Stack`'s design. — C. K. Young, Nov 14 '13 at 15:44
Again: you cannot do that in the stack. That's by concept. The fact that the technology (in this case, Java) helps you do this is just good (or bad, depending how you see/use it). Looks like you need to separate two things: the concepts about the data structure and the benefits (or pitfalls) from the technology. — Luiggi Mendoza, Nov 14 '13 at 15:45

score 2 · Answer 1 · answered Nov 14 '13 at 15:30

2

Stack is a really old class from before Java 1.2 (and the Java Collections Framework). I suggest, if you can, that you switch to using Deque, which as you say already has all the functionality you need.

answered Nov 14 '13 at 15:30

C. K. Young

219,335
46
382
435

2

@Sage OP asked in the end *Any suggestions?* and this is a valid suggestion. – Luiggi Mendoza Nov 14 '13 at 15:31
1

@Sage The OP knows about `Deque`, but I was more reinforcing that `Stack` is a really ancient class and it probably won't receive any further love from the Java maintainers. Like `Vector` and `Hashtable`, it's sorted of discouraged to use (even if not officially `@Deprecated`). – C. K. Young Nov 14 '13 at 15:43

score 1 · Accepted Answer · edited May 23 '17 at 11:45

I was wondering how can I iterate over the elements of a Stack starting from the top and going down without using any additional memory.

By concept, a stack cannot be iterated at least that you pop all its elements. Period.

The main problem here is that you are confusing this stack data structure with Java Stack, which offers you an iterator from its super class, Vector, probably confusing you. This is, in fact, a design issue that comes from Java 1. Usage of Vector class is discouraged as noted here: Why is Java Vector class considered obsolete or deprecated?, and since Stack extends from vector, its usage is also discouraged. Also, in the JavaDoc of the Stack class, the authors now add this info (emphasys mine):

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.

I noticed also that for Deque there is a descendingIterator ...

As noted in comments, the fact that the technology (in this case, Java) helps you iterating over a data structure is just good (or bad, depending how you see/use it).

Note that the Deque is a double ended queue, and can work as both a stack and a queue, depending how you want/need to use it.

Since Deque extends from Iterable, it should provide an Iterator in order that its elements can be visited using a specific behavior like the sequence of the elements, this iterator will visit the elements from first to last, like navigating through a queue. The descendingIterator returns an iterator to visit the elements from last to first, like navigating through a stack. But again, take into account that this is a benefit from the technology.

If this is not possible which other Java data structures offer the functionality of a Stack with the ability the iterate it backwards (except Deque ofc)?

Apart from its concurrent child, BlockingDeque, looks like not in the common Java interfaces. This is driven by this design: What does it mean to "program to an interface"?. Note that you can create a stack from scratch using ArrayList or another structure, or make it behave like one, but still is up to you.

Reversed Stack Iterator

2 Answers2