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*, mas isso vale pra toda memória, não só 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" a compressão e acesso.

# Pilha

### Alocação

Em condições normais, **o *stack* é alocado no início da execução 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 reservado para um segmento 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, mas há [indireções][4] também.

![alocação stack][5]

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 **automática** de alocação (muitas vezes confundida com estática que é alocação que ocorre junto ao execução logo na sua carga. Tecnicamente existe 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, o seu gerenciamento é automático.

# 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 no *stack* tem algumas restrições). 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 deva ocorrer no *heap*.

Linguagens de alto nível predeterminam isto. Outras deixam o programador ter mais controle, podendo até mesmo abusar do *stack* se for útil e o programador 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, em alguns casos se a linguagem prover mecanismos que permitam, haver *overflow* de um dado em cima de outro que venha a seguir na pilha. Execuções recursivas descontroladas causam *stack overflow*.

### 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.

# 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 disponível para seu processo.

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

De certa forma podemos dizer que o *stack* como um todo é o primeiro objeto alocado no *heap*.

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 e evita chamadas ao sistema operacional que troca contexto e costuma ser bem mais lento. Em geral todo sistema de alocação da memória aloca mais do que precisa e vai dando acesso à aplicação conforme ela precisa, em alguns casos, ele quase simula um *stack*, por algum tempo, ou fazer reorganização da memória (através de um GC compactador).

### 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*][6] 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][7].

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, e mesmo quando não precisa do SO ainda tem um algoritmo complexo para alocar. Desalocar, ou disponibilizar de volta uma área também tem seu custo, em alguns casos para a alocação custar mais barata a liberação custa bem cara (ironicamente pode ser controlada por várias pilhas).

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 alguns casos 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][8]

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 de forma transparente.

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

Note que no exemplo, um objeto do tipo `class1` é alocado no *heap*. Mas há uma referência para este objeto, que é alocada no *stack* (em alguns casos poderia não estar).

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), ou 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, e isto pode ser feito só usando registradores, super rápido.

# 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][10] 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://pt.stackoverflow.com/q/181032/101
  [5]: https://i.sstatic.net/9UshP.png
  [6]: https://pt.stackoverflow.com/q/255769/101
  [7]: https://pt.stackoverflow.com/q/135572/101
  [8]: https://i.sstatic.net/0Obi0.png
  [9]: https://i.sstatic.net/NS0k7.jpg
  [10]: https://stackoverflow.com/questions/79923/what-and-where-are-the-stack-and-heap