What is the java class stack growth policy?

Asked

Viewed 66 times

2

I am doing a work on different Tacks and what I am studying increases its size to double when we introduce the (2 n+)1 element.

But what is the growth policy of java.util.Stack and java.util.Arraydeque?

  • Are you referring to java.util.Stack and java.util.ArrayDeque?

  • Yes @Victorstafusa

1 answer

2

Stack

The class java.util.Stack stretches java.util.Vector, which will define much of its functionality.

Vector allows specifying in its constructor both the initial capacity and the increment of the internal vector when the capacity is exceeded, but such constructor is not available in the subclass Stack.

This means that the internal vector will always start with the amount of standard elements, which is 10, and double in size when expanding: 20, 40, 80, ...

However, the method ensureCapacity(n) can force faster growth. Basically, the method expands the vector to ensure that it can receive at least more n elements without bursting capacity. In the current implementation, the method first checks whether doubling capacity is sufficient, otherwise it resizes the internal vector to capacidade atual + n. This also means that it is not possible to expand the vector by less than double, not to create an alternative implementation.

Arraydeque

Already the class java.util.ArrayDeque will always have the size of the internal vector being a power of 2, as your documentation states.

Alternative

For linear growth, the class can be used java.util.LinkedList, which implements java.util.Deque, the same interface implemented by java.util.arrayDeque.

Comparisons

It is never enough to remember that each implementation has its advantages and disadvantages.

For example, vector-based implementations are faster for random access and for inserting multiple elements in sequence, especially when the quantity is known and since the quantity is not as large as, say, half of the available memory.

Chain-based lists may be required when the list is too large, occupying most of the memory and is changed quite often so it is not possible to use vectors, since making a vector copy would occupy more than 100% of the memory.

Browser other questions tagged

You are not signed in. Login or sign up in order to post.