Java: immutable stack?

Question

TERM Immutable Stack: I overuse stack. Poly's reply uses Collections.emptyList() as immutable list. No Collections.emptyStack(). Combining the words stack and immutability, from the last experiences, gets "immutable stack" (probably not related to functional prog).

Java Api 5 for list interface shows that Stack is an implementing class for list and arraylist, here. The java.coccurrent pkg does not have any immutable Stack data structure. The first hinted of misusing stack. The lack of immutabily in the last and poly's book recommendation leads way to list. Something very primitive, fast, no extra layers, with methods like emptyThing().

From Stack to some immutable data structure

1. How to get immutable Stack data structure? Can I box it with list?
2. Should I switch my current implementatios from stacks to Lists to get immutable?
3. Which immutable data structure is Very fast with about similar exec time as Stack?

No immutability to Stack with Final

import java.io.*;
import java.util.*;

public class TestStack{


        public static void main(String[] args)
        {
                final Stack<Integer> test = new Stack<Integer>();
                Stack<Integer> test2 = new Stack<Integer>();
                test.push(37707);
                test2.push(80437707);

                //WHY is there not an error to remove an elment
                // from FINAL stack?
                System.out.println(test.pop());
                System.out.println(test2.pop());
        }
}

[Added]

Overuse of stack

DataFile.java:  public Stack<DataFile> files;
FileObject.java:        public Stack<String> printViews = new Stack<String>();
FileObject.java://      private static Stack<Object> getFormat(File f){return (new Format(f)).getFormat();}
Format.java:            private Stack<Object> getLine(File[] fs,String s){return wF;}
Positions.java: public static Stack<Integer[]> getPrintPoss(String s,File f,Integer maxViewPerF)
Positions.java:         Stack<File> possPrint = new Stack<File>();
Record.java:    private String getFormatLine(Stack<Object> st)
SearchToUser.java:      public static final Stack<File> allFiles = findf.getFs();
View.java:      public Stack<Integer[]> poss = new Stack<Integer[4]>();

Answer 1

I think you want to use the Collections. unmodifiableList() method on your Stack to achieve the desired results.

Answer 2

A stack is a "last-in-first-out" data structure. Note how this is defined in terms of mutability (adding and removing items) - i.e. stack is mutable by definition.

The fastest immutable collection you can get is probably ArrayList wrapped by Collections.unmodifiableList().

Answer 3

I can't answer for Java specifically, but the catenable dequeue is probably a reasonable starting point for a data structure in a functional language to get reasonable performance on an immutable stack-like object. In order to implement it in Java, you'd have to find a way to represent the concept of lazy evaluation, which I would imagine would be non-trivial.

I'm not sure what benefit you'd have from an immutable stack in Java itself, because you'd need the somewhat tortuous abstraction of passing in an object representing the continuation to a "pop" function, and you'd break the basic interface that most OO-based stacks would adhere to. You could get passable results, by which I mean behaviorally, not in terms of performance characterstics, without implementing the whole catenable dequeue strcuture if your push function returned a reference to a new stack object, and your pop function returned a tuple-like object with a reference to the stack object and the popped item.

I might be missing something, or you might be describing something slightly different than what most functional programmers would mean when talking about an immutable stack.

Answer 4

Looking at your code it sounds like you want to simply prevent removal. The easiest way to do this is to extend Stack and make pop() and all methods which remove throw exceptions, or do nothing. Preferably throw exceptions.

Like harto said, final only works on the pointer, it does not prevent changes being made to the object being pointed at, an important distinction to remember.

I would caution however you reconfirm your theory that an immutable stack is the fastest possible implementation. I don't really see what benefit you get by explicitly denying removal, since simply not calling pop would have the same effect. Since Stack is a Vector, however, you're likely to see worse speeds than ArrayList or ArrayDeque (the latter even mentions in its documentation that it's faster). Perhaps if you could give us more details on exactly what your use case for the data structure is, we could suggest a better one, but based on what I know right now, I'd suggest one of the two above and if absolutely necessary overwrite the removal methods.

Answer 5

You're misunderstanding the purpose of the final keyword. It just makes a reference non-reassignable. It has nothing to do with const-correctness which you may be familair with from other languages.

­1. How to get immutable Stack data structure? Can I box it with list?

As Sugerman mentioned, if you want an immutable view of your stack, wrap it using Collections.unmodifiableList(..)

­2. Should I switch my current implementatios from stacks to Lists to get immutable?

java.util.Stack is already a List. There is no need to switch.

­3. Which immutable data structure is Very fast with about similar exec time as Stack?

java.util.Stack extends Vector. That's probably as fast as you're going to get short of assembly language.

Example of usage:

import java.util.*;

public class Sandbox {
    public static void main(String[] args) {
        MyClass myObj = new MyClass();
        List<Object> list = myObj.getObjects();
        list.clear(); // UnsupportedOperationException!
    }
}

class MyClass {
    private Stack<Object> stack = new Stack<Object>();
    public List<Object> getObjects() {
        return Collections.unmodifiableList(stack);
    }
}