Estruturas de dados dinâmicas: a pilha

Um computador pessoal ou estação de trabalho tem normalmente, algo entre 16 e 64 megabytes de RAM instalados. Usando uma técnica chamada memória virtual, o sistema pode fazer trocas entre a memória e o disco rígido, criando para a CPU a ilusão de que ela possui mais memória, por exemplo, 200 a 500 megabytes. Enquanto esta ilusão se completa para a CPU, ela pode tornar as coisas extremamente lentas para o usuário. Apesar desta desvantagem, a memória virtual é uma técnica extremamente útil para "aumentar" a quantidade de RAM em uma máquina de um modo bem barato. Vamos supor, para fins de argumentação, que um computador tradicional possui espaço de memória total de, por exemplo, 50 megabytes (independentemente de a memória ser implementada no formato RAM físico ou virtual).

O sistema operacional em uma máquina está encarregado dos 50 megabytes de espaço de memória. O sistema operacional usa o espaço de diversas maneiras, como exemplificamos aqui:

O sistema operacional e diversos aplicativos, juntamente com suas variáveis globais e espaços de pilha, consomem partes da memória. Quando um programa completa a execução, libera sua memória para ser reutilizada por outros programas. Observe que parte do espaço de memória permanece inutilizada em qualquer momento.

Isto, obviamente, é uma idealização, porém os princípios básicos estão corretos. Como vocÊ pode ver, a memória contém o código executável para os diferentes aplicativos em execução na máquina, junto com o código executável do próprio sistema operacional. Cada aplicativo tem determinadas variáveis globais associadas a ele. Estas variáveis também consomem memória. Finalmente, cada aplicativo usa uma área da memória chamada pilha, que mantém todas as variáveis locais e parâmetros usados por qualquer função. A pilha também mantém a ordem de execução das funções, para que os retornos das funções ocorram corretamente. Sempre que uma função é executada, suas variáveis locais e parâmetros são "empurrados" sobre a pilha. Quando a função retorna, estes locais e parâmetros são "lidos e removidos". Por isso, o tamanho da pilha de um programa flutua constantemente conforme a execução do programa, mas tem um tamanho máximo.

Ao terminar a execução de um programa, o sistema operacional descarrega o programa, seus globais e seu espaço de pilha da memória. Um novo programa pode usar aquele espaço posteriormente. Desta forma, a memória em um sistema de computador é constantemente "reciclada" e reutilizada por programas, à medida que são executados e concluídos.

Em geral, cerca de 50% do espaço total de memória do computador pode estar ocioso em um dado momento. O sistema operacional possui e administra a memória não utilizada, coletivamente denominada de pilha. A pilha é extremamente importante, pois está disponível para aplicativos durante a execução usando as funções em C malloc (alocação de memória) e free. A pilha permite que programas aloquem a memória exatamente quando precisarem dela, durante a execução de um programa, em vez de pré-alocar a memória com uma declaração de matriz de tamanho específico.