Construindo uma pilha vinculada dinâmica em C: implementação e armadilhas

A maioria dos iniciantes presume que as estruturas de dados são estáticas. Eles não são. Uma pilha vinculada é uma fera dinâmica. Ela cresce e encolhe na hora. Você não pré-aloca memória. Você pega quando precisa. Solte-o quando terminar.

Este exemplo usa números inteiros. Altere typedef int stack_data para float ou char se desejar. A lógica permanece a mesma.

A interface

Veja o cabeçalho. É um contrato.

stack_init configura a bagunça. stack_clear apaga tudo. stack_empty informa se sobrou alguma coisa. push insere os dados. pop os arranca.

Simples. Limpar.

O motor

O arquivo de código esconde a coragem.

top aponta para o item mais novo. NULL significa vazio.

stack_init apenas redefine top para NULL. Feito.

stack_clear aparece até ficar vazio. É um ciclo. É barato.

stack_empty verifica se top é NULL. Retorna 1 se for verdadeiro. 0 se falso.

stack_push faz o trabalho pesado.

Ele aloca memória. Define os dados. Vincula-o ao topo antigo. Atualiza top.

stack_pop inverte o processo.

Ele captura os dados. Move de cima para baixo. Libera o nó antigo. Retorna o valor.

Se a pilha estiver vazia? Ele retorna lixo. Não saia de uma pilha vazia.

Ocultação de informações

Isto é fundamental.

Você vê apenas o cabeçalho. Você não vê o código.

A pilha poderia usar matrizes. Ponteiros. Arquivos. Uma lista vinculada. Não importa.

Contanto que a interface funcione, você não se importa como ela é construída.

Isso é ocultação de informações. Não é apenas uma palavra da moda. É como você constrói um software que não quebra quando você altera os componentes internos.

C pegadinhas

C não perdoa erros.

1. Parênteses são importantes. (*p).i não é o mesmo que *p.i. Um deles desreferencia o ponteiro primeiro. O outro acessa o membro e então desreferencia. Se errar, você travará.
2. Vazamentos de memória. Nunca defina apenas top = NULL. Você deixa todos os nós da lista órfãos. Você perde os dados. Você perde a memória. Use grátis. Sempre.
3. Incluir cabeçalhos. NULL reside em stdio.h. Se você esquecer, seu código poderá ser compilado em alguns compiladores. Não acontecerá com os outros. Ou definirá NULL como zero de uma forma estranha. Inclua se você usar ponteiros.

O que vem a seguir?

A pilha básica é simples. As pilhas reais precisam de mais.

Adicione dup. Duplique o elemento superior. Adicione contagem. Retorne o número de itens. Adicione adicionar. Abra os dois primeiros, adicione-os e empurre o resultado.

Crie um programa de driver. Escreva um makefile. Compile-o. Execute-o.

Se travar, você perdeu um free. Ou você acessou a memória liberada. Depure-o.

A verificação da realidade

A alocação dinâmica é rápida. Até que não seja.

malloc e free têm sobrecarga. Em loops apertados, isso aumenta.

Mas para uso geral? É flexível. É padrão. É o que você verá na maioria das bases de código C.

A pilha vinculada é um bloco de construção.

Você o usará para chamadas de função. Para avaliação de expressão. Para botões de desfazer.

Está em todo lugar.

Apenas lembre-se: se você alocar, você o libera. Ou então.

“Código é como humor