Um *stack* ou pilha, neste contexto, é uma forma otimizada para organizar dados na memória alocados em sequência e abandonados (sim, normalmente não há desalocação) em sequência invertida a da entrada.

[![Pilha][1]][1]

Um *heap* ou monte (ok, ninguém traduz isso) é a organização de memória mais flexível que permite o uso de qualquer área lógica disponível.

[![Monte][2]][2]

#De que pilha estamos falando?

Existem alguns conceitos de pilha muito difundidos em computação, para citar alguns:

 - Existe a **pilha de execução** de alguma arquitetura onde as instruções e dados vão sendo empilhados e após executar algo ali, ocorre o desempilhamento.
 - Existe a **pilha de chamadas de funções**, que se confunde com o gerenciamento de memória, onde as funções vão sendo chamadas e empilhadas e quando sua execução termina, ela sai da pilha.
 - Existe a [**estrutura de dados genérica**][3] que empilha dados diversos. [Exemplo em C#][3].

#Conceito abstrato

Os dois conceitos da pergunta são abstratos. Não existe fisicamente uma área da memória específica para o *stack* (e muito menos sua área é fisicamente empilhada) e não existe uma área reservada para o *heap*, pelo contrário, ele costuma ser bastante fragmentado. Usamos o conceito para entender melhor o funcionamento e suas implicações, principalmente no caso da pilha.

A maioria das arquiteturas de computadores modernos e populares não tem grandes facilidades para manipular esse *stack* de memória (costuma ter só o registrador de ponteiro de pilha), assim como o *heap*, apesar que neste caso, instruções que ajudam manipular memória virtual de uma certa forma ajudam a organizar o *heap*.

#Ficando um pouco mais concreto

Já o sistema operacional está bem ciente destes conceitos e é fundamental que eles possuam alguma forma, mesmo que limitada, para manipular a memória das aplicações. Principalmente nos sistemas modernos e de utilidade geral. Os sistemas modernos possuem um gerenciamento complexo através do que se convencionou chamar de memória virtual que também é um conceito abstrato, muitas vezes mal compreendido.

#Onde mexemos diretamente

Em *assembly* ou C é muito comum ter contato com esse gerenciamento de memória. Em *assembly* é comum manipular o *stack* quase diretamente e em ambas linguagens pelo menos a alocação e desalocação do *heap* devem ser feitas manualmente através da API do sistema operacional. Em C o *stack* é gerenciado pelo compilador, salvo alguma operação incomum que seja necessária.

Nada impede que se use alguma biblioteca que abstraia essa manipulação, mas isso só é comum em linguagens de mais alto nível. De fato é muito comum que outras linguagens usem internamente a API do OS para fazer o gerenciamento pesado da memória mas o acesso da memória no "varejo" é feito por um gerenciador próprio, em geral chamado de *garbage collector* através de técnicas de contagem de referências para um objeto no *heap* (há quem considere que isto não é uma técnica de *garbage collector*) ou de verificação posterior se há referências para o objeto no *heap*. Mesmo usando uma biblioteca mais abstrata, os conceitos permanecem.

Quanto mais alto nível, menos precisam gerenciar tudo isso, mas entender o funcionamento geral é importante em todas linguagens.

Linguagens que não precisam de performance pode deixar tudo no *heap* e "facilitar".

#Pilha

###Alocação

Em condições normais, **o *stack* é alocado no início da aplicação**, mais precisamente no início da *thread*, mesmo que a aplicação só tenha a *thread* principal.

O *stack* é uma porção contígua de memória reservada para empilhar os dados necessários durante a execução de blocos de código.

Cada necessidade de alocação é um trecho do *stack* que vai sendo usado sempre em sequência determinado por um marcador, ou seja, um apontador, um **ponteiro**, se "movimenta" para indicar que uma nova parte na sequência desta porção reservada está comprometida.

Quando algo alocado não é mais necessário, este marcador se movimenta em direção contrária a sequência de dados indicando que alguns desses dados podem ser descartados (sobrepostos com novos dados).

A alocação de cada trecho da memória não existe no *stack*, é apenas o movimento deste ponteiro indicando que aquela área será usada por algum dado.

A grosso modo podemos dizer que a aplicação tem total controle sobre o *stack, exceto quando acaba o espaço disponível nele.

Existem recursos para alterar manualmente o tamanho do *stack*, mas isso é incomum.

#Funcionamento

A pilha funciona usado uma forma LIFO (Last in First Out) ou UEPS (Último a entrar, primeiro a sair).

O escopo de uma variável costuma definir o tempo de alocação no *stack*. Os dados usados como parâmetros e retorno de funções são alocados no *stack*. Por isso a pilha de chamadas de função se confunde com a pilha da memória.

Podemos dizer que os parâmetros são as primeiras variáveis de uma função alocadas no *stack*. O acesso aos dados no *stack* costuma ser feito de forma direta.

![alocação stack][4]

Deu para entender que cada *thread* tem seu próprio *stack*, certo? E o tamanho do *stack* de cada *thread* criada pode ter seu tamanho definido antes da criação. Um valor *default* costuma ser usado.

O *stack* é considerado uma forma **estática** de alocação. Embora tecnicamente exista outra área da memória que realmente seja estática, que seja alocada antes do início da execução. A área efetivamente estática não pode ser manipulada, não pode ser escrita (pelo menos não deveria poder). O *stack* em si é estático, apesar de que seus dados não sejam, afinal eles vão sendo colocados e abandonados conforme o seu uso.

#Decisão sobre onde alocar

Assim como no *heap*, não é possível alocar dados no *stack* antes de saber seu tamanho (não precisa saber na hora de compilar, mas sim na hora de executar a alocação). Mas se o tamanho for indeterminado em tempo de compilação ou pode ser determinado como **possivelmente** grande (talvez poucas dezenas de *bytes*), provavelmente a alocação deve ocorrer no *heap*.

Linguagens de alto nível pré-determinam isto. Outras deixam o programador ter mais controle, podendo até mesmo abusar do *stack* se for útil e ele souber o que está fazendo.

###Stack overflow

O famoso *stack overflow* ocorre quando você tenta alocar algo no *stack* e não há espaço reservado disponível. Também pode haver *overflow* de um dado em cima de outro que venha a seguir na pilha.

###Outra pilha

Também existe uma pilha de chamadas que é onde são armazenados os endereços para onde o ponteiro da pilha deve retornar quando termina a execução de uma função. Execuções recursivas descontroladas causam *stack overflow*.

#Heap

###Alocação

O *heap*, ao contrário do *stack*, não impõe um modelo, um padrão de alocação de memória. Isso não é muito eficiente mas é bastante flexível.

O *heap* é considerado **dinâmico**. Em geral você aloca ou desaloca pequenos trechos de memória, só para a necessidade do dado. Esta alocação pode ocorrer fisicamente em qualquer parte livre da memória.

O gerenciamento de memória virtual do sistema operacional, auxiliado por instruções do processador, ajudam a organizar isto.

Efetivamente estas alocações reais costumam ocorrer em blocos de tamanho fixo chamados de páginas. Isso evita a aplicação fazer dezenas ou centenas de pequenas alocações que fragmentaria a memória de forma extrema.

###Desalocação

A desalocação do *heap* costuma acontecer:

 - manualmente (correndo o risco de bugs), embora isto não esteja disponível para algumas linguagens;
 - através do tal *garbage collector* que identifica quando uma parte do *heap* não é mais necessária;
 - quando uma aplicação se encerra.

###Depende de implementação

Até existem linguagens que possuem *heaps* especializados que podem ter um comportamento um pouco diferente, mas vamos simplificar para os casos comuns.

#Conceito abstrato

Fica claro que o *heap* não é uma área da memória. Mesmo conceituando abstratamente, ele é um conjunto de pequenas áreas da memória. Fisicamente ele costuma ser fragmentado por toda a memória. Essas partes são muito flexíveis no tamanho e tempo de vida.

Por razões de segurança é bom saber que desalocar é um conceito abstrato também. Costuma ser possível acessar dados de uma aplicação mesmo depois que ela tenha terminado. O conteúdo só é apagado por pedido manual ou quando uma área disponível seja escrita novamente.

###Custo do *heap*

A **alocação no *heap* "custa" caro**. Muitas tarefas devem ser realizados pelo sistema operacional para garantir a perfeita alocação de uma área para um trecho dele, principalmente em ambientes concorrentes, muito comuns hoje em dia. Desalocar, ou disponibilizar de volta uma área também tem seu custo.

Até existem formas de evitar as chamadas ao sistema operacional para cada alocação necessária, mas ainda assim o "custo" de processamento disto é considerado alto. Manter listas (em geral ligadas) de áreas ou páginas alocadas não é algo trivial para o processador, pelo menos comparando com o movimento do ponteiro que é necessário no *stack*.

###Funcionamento

![alocação heap][5]

O *heap* é acessado através de ponteiros. Mesmo em linguagens que não exista o conceito de ponteiros disponíveis para o programador, isto é realizado internamente.

![exemplo de alocação geral][6]

Note que no exemplo, um objeto do tipo `class1` é alocado no *heap*. Mas há uma referência para este objeto, que é alocada no *stack*.

Esta alocação é necessária porque o tamanho do objeto pode ser muito grande para caber no *stack* (ou pelo menos ocupar uma parte considerável), e porque ele pode sobreviver por mais tempo do que a função que criou ele.

Se estivesse no *stack* a única forma de mantê-lo "vivo" seria copiando para a função chamadora, e assim sucessivamente para todas as outras, onde ele seja necessário. Imagine como isso sai "caro". Da forma como é organizado, só a referência, que é curta, é que precisa ser copiada.

#Conclusão

Então o *runtime* de uma linguagem de programação se comunica com o OS para gerenciar a memória. Se esse *runtime* é exposto para o programador depende do objetivo da linguagem. Em linguagens chamadas "gerenciadas", tudo isso ocorre, os dois conceitos existem e precisam ser entendidos, mas você não tem que manipular manualmente o *heap*. Ele passa ser tão transparente quanto o *stack* é em outras linguagens mais baixo nível (exceto *assembly*).

A alocação de ambos costumam ser realizados na RAM, mas nada impede que seja alocado em outro local. A memória virtual pode colocar todo ou parte do *stack* ou do *heap* em memória de massa, por exemplo.

"Roubei" algumas imagens [desta resposta do SO][7] que são muito boas para ilustrar tudo isso.


  [1]: https://i.sstatic.net/lN2Fx.png
  [2]: https://i.sstatic.net/iwwjW.jpg
  [3]: https://pt.stackoverflow.com/questions/8972/como-funciona-e-se-usa-o-stack-em-c/15063#15063
  [4]: https://i.sstatic.net/9UshP.png
  [5]: https://i.sstatic.net/0Obi0.png
  [6]: https://i.sstatic.net/NS0k7.jpg
  [7]: https://stackoverflow.com/questions/79923/what-and-where-are-the-stack-and-heap