Sei que a pilha estática é implementada através de vetores e a dinâmica em que difere?
Uma é estática e a outra dinâmica.
Próxima.
1 curtida
Uma pesquisada já resolvia.
Quem não sabe pesquisar, jamais será um programador … na verdade não servirá pra muitas outras funções hoje em dia.
Aprendam a usar os recursos de busca, hoje á informação está bem acessível, não fique na dependência de alguém lhe passar de mão-beijada.
Pesquise, pense, se persistir dúvidas, muitas vezes devido ao excesso de opções, aí sim é hora de pedir ajuda.
Neste caso custava pesquisar sobre pilha dinâmica? Pelo texto não pesquisou nada.
Leve este post como uma critica construtiva.
[quote=asousaj]Uma pesquisada já resolvia.
Quem não sabe pesquisar, jamais será um programador … na verdade não servirá pra muitas outras funções hoje em dia.
Aprendam a usar os recursos de busca, hoje á informação está bem acessível, não fique na dependência de alguém lhe passar de mão-beijada.
Pesquise, pense, se persistir dúvidas, muitas vezes devido ao excesso de opções, aí sim é hora de pedir ajuda.
Neste caso custava pesquisar sobre pilha dinâmica? Pelo texto não pesquisou nada.
Leve este post como uma critica construtiva.
[/quote]
Amigo vc acha mesmo que eu já não tinha visto este material?
Eu gostaria de definições e outras exemplificações então não venha falar merda na minha dúvida.
[quote=kabs][quote=asousaj]Uma pesquisada já resolvia.
Quem não sabe pesquisar, jamais será um programador … na verdade não servirá pra muitas outras funções hoje em dia.
Aprendam a usar os recursos de busca, hoje á informação está bem acessível, não fique na dependência de alguém lhe passar de mão-beijada.
Pesquise, pense, se persistir dúvidas, muitas vezes devido ao excesso de opções, aí sim é hora de pedir ajuda.
Neste caso custava pesquisar sobre pilha dinâmica? Pelo texto não pesquisou nada.
Leve este post como uma critica construtiva.
[/quote]
Amigo vc acha mesmo que eu já não tinha visto este material?
Eu gostaria de definições e outras exemplificações então não venha falar merda na minha dúvida.[/quote]
RSRS eu ri!
[quote=kabs]Amigo vc acha mesmo que eu já não tinha visto este material?
Eu gostaria de definições e outras exemplificações então não venha falar merda na minha dúvida.[/quote]
Cara, depois de um link desse qual pode ser a sua dúvida?
Pelo texto da sua pergunta leva a entender que não pesquisou.
Não escrevi merda alguma, é a pura realidade.
Partindo do principio que sabe o que é uma pilha, no caso a estática.
Na dinâmica, funciona como uma lista simplesmente encadeada.
Cada item(objeto) adicionado terá uma referencia ao próximo item, que no caso é o que está no topo antes deste ser adicionado.
Não tem limite de tamanho como a estática, basta que cada elemento saiba quem é o próximo.
Tentando exemplificar.
#4º objeto da pilha, a variável que faz referencia ao próximo aponta para o 3º objeto
#3º objeto da pilha, a variável que faz referencia ao próximo aponta para o 2º objeto
#2º objeto da pilha, a variável que faz referencia ao próximo aponta para o 1º objeto
#1º objeto da pilha, a variável que faz referencia ao próximo está null pois é o 1º
[color=red]Explicação + link … Mais do que isso só desenhando mesmo.[/color]
[quote=Rodrigo Sasaki]
Cara, depois de um link desse qual pode ser a sua dúvida?[/quote]
Então cara, na pilha estática eu implemento ela em um vetor estaticamente mas na parte dinâmica é minha maior dúvida,
no link, o exemplo ele cria um menu que chama uma classe pilha mas qual a vantagem de usar a pilha desta maneira(dinamicamente)?
Outra coisa,
Qual a função dos atributos desta classe?
[code]private static class PILHA {
public int num;
public PILHA prox;
}[/code]Bom, acho que você precisa pesquisar o que é uma lista encadeada primeiro, aí vai entender.
A vantagem dessa abordagem é que a pilha pode crescer e diminuir conforme a necessidade, enquanto um array é fixo.
A lista encadeada é uma estrutura de dados onde cada nó (ou elemento) tem a referência do próximo, sempre indo passo a passo, o google pode te explicar bem melhor 
[quote=Rodrigo Sasaki]Bom, acho que você precisa pesquisar o que é uma lista encadeada primeiro, aí vai entender.
A vantagem dessa abordagem é que a pilha pode crescer e diminuir conforme a necessidade, enquanto um array é fixo.
A lista encadeada é uma estrutura de dados onde cada nó (ou elemento) tem a referência do próximo, sempre indo passo a passo, o google pode te explicar bem melhor :)[/quote]
Ok amigo,
Já abriu minha mente, vou pesquisar sobre listas encadeadas.
Obrigado pela resposta e pela paciência.
Vantagem das estruturas de dados estáticas:
- São dispostas sequencialmente na memória, o que permite um tempo de iteração muito curto;
- São fáceis de implementar;
- Tem pouco overhead, isso é, você quase não gasta memória para coisas que não são os dados.
Desvantagens:
- Na implementação simples, tamanho fixo. Implementações mais flexíveis (como o ArrayList do Java ou o std::vector do C++) incluem um alto custo de expansão e pré-alocação de memória que pode não ser usada;
- Custo alto para remover ou inserir elementos no meio da estrutura de dados. Isso exige que os demais elementos sejam movidos. No caso da pilha, esse não é um problema, já que as inserções / remoções são só no fim.
Vantagens das estruturas de dados dinâmicas:
- Alocação é feita a medida que a estrutura é preenchida;
- Baixo custo de remoção ou inserção de elementos no meio da estrutura;
Desvantagens:
- Maior overhead. Cada elemento é associado a um ou dois ponteiros para controle do próximo/anterior, mas o ponteiro para o próprio no em si;
- Os dados ficam dispersos na memória. Isso aumenta o tempo de iteração;
- A memória é alocada no momento da inserção e desalocada no momento da remoção, e isso representa um custo maior nessas operações quando ocorrem nos extremos da estrutura;
Vini, esse detalhe dos dados estarem dispostos sequencialmente ou dispersos chega a ser perceptível hoje em dia?
Isso só vai ser perceptível em aplicações que fazem muito acesso a dados - o que não é o caso das aplicações comerciais. Na verdade, a maior parte desse prós e contras vai ser pouco perceptível para esse tipo de aplicação.
Mas no caso de aplicações gráficas e/ou com grandes volumes de dados a serem processados (como as que estou acostumado a trabalhar), é BASTANTE perceptível. O fato dos dados estarem espalhados compromete o uso da memória cache, e isso tem um impacto drástico na performance. Outro detalhe é que aplicações com esse perfil tendem a copiar muitos dados de uma área de memória para outra e, em estruturas sequenciais, há funções especializadas do SO que fazem isso em modo kernel (como a memcpy do C).
As vezes, o que se faz é criar estruturas hibridas. O C++ tem um tipo chamado std::deque (double ended queue), que na verdade combina um arraylist com um linkedlist. São nós de pequenos vetores. A idéia desse tipo de estrutura é tentar uma solução que seja adequada a maior parte dos casos (embora não seja ótima para nenhum deles).
PS: Isso fica ainda mais difícil de medir quando a aplicação usa um garbage collector. O garbage collector desfragmenta dados da memória, e usa um heap pré-alocado - o que atenua o custo percebido de um LinkedList, ao custo de um custo arbitrário e imprevisível quando o gc roda.
O custo de desalocação do gc também é mascarado: a memória só é removida na hora que o gc quer, do contrário do que acontece em linguagens não gerenciadas, onde a memória é removida no momento em que se dá “delete”… além disso, o gc consegue reaproveitar áreas de memória recém excluídas, pois ele recicla objetos de vida curta.
Se quiserem ver mais detalhes sobre isso, leiam:
- A brief history of garbage collection: http://www-106.ibm.com/developerworks/java/library/j-jtp10283/
- Garbage collection and performance: http://www-106.ibm.com/developerworks/java/library/j-jtp01274.html
- Garbage collection in the 1.4.1 JVM: http://www-106.ibm.com/developerworks/java/library/j-jtp11253/
Esses artigos só não cobrem aspectos de paralelismo do garbage-first, incluído no Java 7, mas é possível achar um paper (beeeem mais técnico), sobre ele na internet.
É, eu imaginei que fosse algo do tipo. Como nunca trabalhei com nada tão crítico assim (nem perto disso), nunca percebi diferenças nessas coisas, apesar de sempre querer entender como elas funcionam.
Nesse quesito existe alguma situação em que a lista encadeada é uma escolha melhor? Ou uma implementação como a do ArrayList seria preferível? Sendo que sempre gera arrays, mesmo que tenha que recriá-los diversas vezes
Por falar em deque, o java também tem a interface Deque e as implementações: ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque e LinkedList.
[quote=A H Gusukuma]Por falar em deque, o java também tem a interface Deque e as implementações: ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque e LinkedList.
[/quote]
Sim, mas não sei se a implementação do deque do Java é igual a do C++ (não pesquisei). Talvez seja só uma lista duplamente encadeada comum.
Respondendo ao Eric. A lista encadeada é bem útil quando você remove ou adiciona muitos elementos do meio da lista. É o caso de caches dinâmicos, ou listas de agentes em games (onde um inimigo pode morrer a qualquer momento).
[quote=ViniGodoy][quote=A H Gusukuma]Por falar em deque, o java também tem a interface Deque e as implementações: ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque e LinkedList.
[/quote]
Sim, mas não sei se a implementação do deque do Java é igual a do C++ (não pesquisei). Talvez seja só uma lista duplamente encadeada comum.
[/quote]
Também não pesquisei, como em Java a gente vai pela API e não pela implementação…hehehe
Pela descrição do ArrayDeque, parece ser similar a do C++.
É bem interessante. Dá para implementar vários comportamentos como fila e pilha.