Creating a fixed-size Stack

Question

I want to create a Stack in Java, but fix the size. For example, create a new Stack, set the size to 10, then as I push items to the stack it fills up and when it fills up to ten, the last item in the stack is pushed off (removed). I want to use Stack because it uses LIFO and fits my needs very well.

But the setSize() method that Stack inherits from Vector doesn't seem to actually limit the size of the Stack. I think I am missing something about how Stacks work, or maybe Stacks weren't meant to be constrained so it is impossible. Please educate me!

Answer 1

You can subclass Stack and override the appropriate method(s) to implement this custom behavior. And make sure to give it a clear name (e.g. FixedStack).

Answer 2

You can use LinkedHashMap and override its removeEldestEntry method:

public class FixedStack extends LinkedHashMap<Long, String> {

    private final int capacity;

    public FixedStack(int capacity) {
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(final Map.Entry<Long, String> eldest) {
        return super.size() > capacity;
    }
}

And to test it:

    public static void main(String[] args) {

        FixedStack stack = new FixedStack(10);

        long added = 0;
        for (Locale locale : Locale.getAvailableLocales()) {
            if (locale.getDisplayCountry().length() > 0) {
                stack.put(added, locale.getDisplayCountry());
                System.out.println(locale.getDisplayCountry());
                added++;
            }
        }
        System.out.println(String.format(">>>>>>>>> %s added",
                added));
        Iterator<Entry<Long, String>> iterator = stack.entrySet().iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next().getValue());
        }
    }

You just have to decide what you want to use as the key, I used a simple counter in the example.

Answer 3

A LinkedBlockingDeque is one simple option. Use the LinkedBlockingQueue(int) constructor where the parameter is the your stack limit.

---

As you observed, Stack and Vector model unbounded sequences. The setSize() method truncates the stack / vector. It doesn't stop the data structure from growing beyond that size.

Answer 4

You can create a very simple stack like this:

public class FixedStack<T>
{
    private T[] stack;
    private int size;
    private int top;

    public FixedStack<T>(int size)
    {
        this.stack = (T[]) new Object[size];
        this.top = -1;
        this.size = size;
    }

    public void push(T obj)
    {
        if (top >= size)
            throw new IndexOutOfBoundsException("Stack size = " + size);
        stack[++top] = obj;
    }

    public T pop()
    {
        if (top < 0) throw new IndexOutOfBoundsException();
        T obj = stack[top--];
        stack[top + 1] = null;
        return obj;
    }

    public int size()
    {
        return size;
    }

    public int elements()
    {
        return top + 1;
    }
}

Answer 5

A pure stack would not limit its size, as for many of the problems stacks solve you don't know how many elements you are going to need.

You could write a custom stack that implements the needs you described. However, you will break LIFO if you do. If the max size is met, and you push something new on the stack, you just lose the previously added item. So if you then start popping items off your stack, you'll miss some.

Answer 6

What you need is a double-ended queue like LinkedList. This wouldn't automatically drop elements at the front though, but by subclassing/decorating it you could add that functionality.