Java: Immutable Stack | Jorge's space

Java: Immutable Stack | Jorge's space

You might be thinking that a stack is by its very nature something that changes. A stack is an abstract data type with the interface:

IStack<T> push(T value); IStack<T> pop(); T peek(); boolean isEmpty();

You push stuff onto it, you pop stuff off of it, it changes. How can it be immutable?

Every time you need to make a data structure immutable, you use basically the same trick: an operation which "changes" the data structure does so by constructing a new data structure. The original data structure stays the same.

How can that possibly be efficient? Surely we'll be allocating memory all over the place! Well, actually, in this case, no. An immutable stack is every bit as efficient as a mutable stack. Even better: in some cases, it can be considerably more efficient, as we'll see.

Let's start by defining an interface for our immutable structure. While we're at it, we'll fix a problem with the stack ADT above, namely that you cannot interrogate the stack without changing it. And we'll make the stack enumerable just for the heck of it:

Read full article from Java: Immutable Stack | Jorge's space