Estou a fazer um trabalho sobre diferentes stacks e o que estou a estudar, aumenta o seu tamanho para o dobro quando vamos introduzir o (2^n+)1 elemento.
Mas qual é a politica de crescimento da java.util.Stack e java.util.ArrayDeque?
Stack Overflow em Português é um site de perguntas e respostas para programadores profissionais e entusiastas. Leva apenas um minuto para se inscrever.
Inscreva-se para participar desta comunidadeA classe java.util.Stack
estende java.util.Vector
, o que vai definir grande parte de sua funcionalidade.
Vector
permite especificar em seu construtor tanto a capacidade inicial como o incremento do vetor interno quando a capacidade é excedida, porém tal construtor não está disponível na subclasse Stack
.
Isto significa que o vetor interno sempre vai iniciar com a quantidade de elementos padrão, que é 10
, e dobrar de tamanho ao expandir: 20
, 40
, 80
, ...
Entretanto, o método ensureCapacity(n)
pode forçar um crescimento mais acelerado. Basicamente, o método expande o vetor para garantir que ele possa receber pelo menos mais n
elementos sem estourar a capacidade. Na implementação atual, o método primeiro verifica se dobrar a capacidade é suficiente, caso contrário ele redimensionar o vetor interno para capacidade atual + n
. Isto também significa que não é possível expandir o vetor em menos do que o seu dobro, não ser criar uma implementação alternativa.
Já a classe java.util.ArrayDeque
terá sempre o tamanho do vetor interno sendo uma potência de 2
, como declara sua documentação.
Para um crescimento linear, pode ser utilizada a classe java.util.LinkedList
, a qual implementa java.util.Deque
, a mesma interface implementada por java.util.arrayDeque
.
Nunca é demais lembrar que cada implementação tem suas vantagens e desvantagens.
Por exemplo, as implementações baseadas em vetores são mais velozes para acesso aleatório e para inserção de vários elementos em sequência, principalmente quando a quantidade é conhecida e desde que a quantidade não seja tão grande quanto, digamos, metade da memória disponível.
Listas baseadas em cadeias de elementos pode ser necessárias quando a lista é muito grande, ocupando a maior parte da memória e é alterada bastante frequentemente de modo não é possível usar vetores, já que fazer uma cópia do vetor iria ocupar mais de 100% da memória.
java.util.Stack
ejava.util.ArrayDeque
? – Victor Stafusa 14/04/17 às 15:41