Por que são dois conceitos diferentes ambos os chamados “amontoado”?

Question

Por que a pilha de tempo de execução usado para alocação dinâmica de memória em linguagens de estilo C e a estrutura de dados ambos chamados "pilha"? Existe alguma relação?

Answer 1

Donald Knuth diz (The Art of Computer Programming, Third Ed, Vol 1, p 435...):

Vários autores começou há cerca de 1975 para chamar o pool de memória disponível um "amontoado".

Ele não diz que autores e não dá referências a quaisquer documentos específicos, mas diz que o uso do termo "pilha" em relação às filas de prioridade é o sentido tradicional da palavra.

Answer 2

Eles têm o mesmo nome, mas eles realmente não são semelhantes (mesmo conceitualmente). A pilha de memória é chamado de um monte da mesma forma que você iria se referir a um cesto de roupa como uma "pilha de roupas". Este nome é usado para indicar um lugar um pouco confuso onde a memória pode ser alocada e desalocada à vontade. A estrutura de dados (como o link Wikipedia você faz referência a pontos fora) é bem diferente.

Answer 3

O nome de colisão é lamentável, mas não tudo o que misteriosa. Heap é uma palavra pequena, comum usado para significar uma pilha, coleção, grupo, etc. O uso da palavra para a estrutura de dados pré-data (eu tenho certeza) o nome do pool da memória. Na verdade, piscina teria sido uma melhor escolha muito para o último, na minha opinião. Heap conota uma estrutura vertical (como uma pilha), que se encaixa com a estrutura de dados, mas não o pool de memória. Nós não pensamos de uma pilha de memória de piscina como hierárquico, enquanto que a ideia fundamental por trás da estrutura de dados é manter o maior elemento no topo da pilha (e sub-montes).

Heap a estrutura de dados remonta a meados dos anos 60; montão o pool de memória, os primeiros da década de 70. O termo pilha (que significa pool de memória) foi utilizado, pelo menos, tão cedo quanto 1971 por Wijngaarden nas discussões sobre Algol.

Possivelmente o uso mais antigo da pilha como uma estrutura de dados é encontrado sete anos antes, em
Williams, J. W. J. 1964. "Algoritmo 232 - heapsort", Communications of the ACM 7 (6): 347-348

Answer 4

Na verdade, lendo sobre a memória maneira é alocado (veja camarada Blocos ) me lembra de uma pilha em estruturas de dados.

Answer 5

IMO é apenas um acidente / coincidência que essas duas coisas completamente alheios ter o mesmo nome. É como gráfico e gráfico .

Answer 6

Heap-como estrutura de dados é usado pelo algoritmo de encontrar a alocação de memória disponível. A seguir foi extraído de http://www.cprogramming.com/tutorial/virtual_memory_and_heaps.html.

Quando new é invocado, ele começa a procurar um bloco de memória livre que se encaixa o tamanho para o seu pedido. Supondo que o bloco tal de memória é encontrado, ele é marcado como reservados e um ponteiro para esse local é retornado. Existem vários algoritmos para fazer isso, porque um compromisso tem que ser feita entre a digitalização de toda a memória para encontrar o bloco livre menor maior do que o tamanho de seu objeto, ou retornando o primeiro em que a memória necessária se encaixa. A fim de melhorar a velocidade de obtenção de um bloco de memória, as áreas livres e reservada da memória são mantidos em uma estrutura de dados semelhante ao árvores binárias chamados um montão.

Answer 7

Os termos coloquiais pilha memória e memória heap não são usados ??no padrão C ++. As utilizações comuns de armazenamento estático, armazenamento fio, de armazenamento automático e armazenamento dinâmico.

Mais podem ser encontradas em armazenamento Duraction seção do padrão .

Assim, a partir da linguagem e ponto de biblioteca padrão de vista, não há confusão.

Answer 8

Q. O que é um amontoado? A. A pilha é uma coleção de objetos colocar em cima uns dos outros.

resposta à sua pergunta: Ambos pilha de memória e pilha de binário utiliza o mesmo conceito que você sabe. Os dados são armazenados na forma de uma pilha na memória na mesma ordem como está escrito no programa enquanto heap binário é uma estrutura de dados que segue o mesmo conceito de armazenar dados em uma maneira ordenada na forma de uma pilha (Dados no topo do outro). Deixe-me saber o que você pensa na seção de comentários.

Answer 9

Talvez a primeira pilha de memória implementada foi gerido por uma estrutura de pilha?