Pilha baseada em array dinâmico em C

Question

Escrevi uma pilha dinâmica em C que usa um array como estrutura. Tentei manter O (1) para push and pop e acredito que fiz isso. Eu quero saber o que pode ser escrito de uma forma mais limpa e se há algum bug não trivial.

#include <stdio.h>
#include <stdlib.h>

int push(int val, int *c);
int pop(int *c);

int *stack;

int main(){
    int *c = malloc(sizeof(int));
    stack = malloc(sizeof(int));
    *c = 0;
    int i;
    for(;;){
       printf("1. Push\n2. Pop\n3. Stack\n4. Quit\n>>> ");
       scanf("%d", &i);
       if(i == 1){
           printf("Value: ");
           scanf("%d", &i);
           push(i, c);
       }
       else if(i == 2)
           printf("Value popped: %d\n", pop(c));
       else if(i == 3)
           for(int i = 0; i < *c; i++)
               printf("%d\n", stack[i]);
       else
           break;
    }
    free(stack);
    return 0;
}

int push(int val, int *c){
    int *r;
    r = realloc(stack, ((*c)+1)*sizeof(int));
    if (r == NULL){
        free(stack);
        exit(0);
    }
    stack = r;
    stack[*c] = val;
    ++(*c);
    return *c;
}

int pop(int *c){
    if (!(*c)) return -1;
    int x = stack[(*c)-1];
    stack[(*c)-1] = NULL;
    int *r;
    printf("%d\n", *c);
    r = realloc(stack, ((*c)-1)*sizeof(int));
    if(r == NULL){
        free(stack);
        exit(0);
    }
    --(*c);
    stack = r;
    return x;
}

```

Answer 1

A revisão de @G. Sliepen é bom e concordo com tudo o que foi dito lá. Além do que, além do mais:

• Nunca esconda os ponteiros atrás de um typedef! Isso torna a leitura do código muito confusa para programadores C, incluindo você. Você pode pensar que passa dados por valor quando não está, e em situações confusas semelhantes.

• ... = malloc(sizeof(int));É ineficiente alocar apenas 1 item e quase que imediatamente precisa realloc. Observe que toda localização de memória dinâmica é lenta após a criação e devemos dirigir para minimizar a quantidade de chamadas para malloc/ realloc. Chamá-los com frequência também leva à fragmentação do heap , o que pode levar ao desperdício de memória e a outros problemas.

  Em vez disso, aloque uma estimativa "grande o suficiente" na primeira vez que ligar malloc. Em vez disso, talvez 100 itens. E cada vez que você ficar sem memória, não reallocapenas mais 1 item, aloque muito mais e mantenha o controle de quanto espaço você alocou e quanto dessa memória você está usando.

  Da mesma forma, não há necessidade de reduzir a quantidade de memória alocada cada vez que você abre algo. A desalocação também é lenta. Apenas diminua um contador que monitora a quantidade de memória alocada que você está usando.

  Coisas como essas são o que realmente importa quando se trata de desempenho do programa. Teoria do "Big O", muito menos.

• stack[(*c)-1] = NULL;está incorreto, um bug. Você nunca deve atribuir NULL a variáveis ​​comuns, apenas a ponteiros. NULL também pode ser definido como um tipo de ponteiro e, em seguida, esse código será interrompido.

  Na verdade, você não precisa limpar a memória não usada, isso é inútil.

• Um problema de estilo, mas crie o hábito de sempre usar, { }mesmo quando houver apenas uma linha dentro da instrução seguinte if/elseou das instruções de loop. E evite frases simplistas, comoif (!(*c)) return -1;

• O nome da variável ideve ser usado apenas para iteradores de loop. O nome iem um loop na verdade significa iterador . Não o use para outros fins, como receber a entrada do usuário.

• Não use "números mágicos" no código, como else if(i == 3). Use constantes textuais em seu lugar. Por exemplo:

    enum
    {
      PUSH  = 1,
      POP   = 2,
      PRINT = 3,
      QUIT  = 4,
    };
  

• Com o enum acima, podemos limpar o loop for e as instruções if bastante, tornando o código um pouco mais longo, mas muito mais sustentável:

  int user_choice = 0;
  while(user_choice != QUIT)
  {
    printf("1. Push\n2. Pop\n3. Stack\n4. Quit\n>>> ");
    scanf("%d", &user_choice);
  
    switch(user_choice) 
    {
      case PUSH: 
      {
        printf("Value: ");
        scanf("%d", &i);
        push(i, c);
        break;
      }
  
      case POP:
      {
        printf("Value popped: %d\n", pop(c));
        break;
      }
  
      case PRINT:
      {
        for(int i = 0; i < *c; i++)
        {
          printf("%d\n", stack[i]);
        }
        break;
      }
  
      default:
        user_choice = QUIT; // defensive programming, quit upon all invalid choises
    } // switch(user_choice) 
  } // while(user_choice != QUIT)
  

  (Observe que eu deliberadamente não user_choicecriei um tipo de enum. Fiz isso apenas porque scanf("%d", &user_choice);em um enum não é seguro. Caso contrário, typedef enumseria preferível fazer um int.)

Answer 2

Crie um structque encapsule todos os detalhes de uma pilha

O problema é que sua pilha se parece apenas com um ponteiro para um int, indistinguível de outros ponteiros para ints. E o primeiro elemento para o qual aponta é tratado de forma diferente dos outros elementos. Nesse caso, é melhor criar uma estrutura que monitore a memória alocada e o tamanho dela, assim:

struct Stack {
    size_t size;
    int *data;
};

Você o inicializa da seguinte maneira:

struct Stack stack = {0, NULL};

Agora você deve mudar push()e pop()apontar para um struct stack:

void push(struct Stack *stack, int val) {
    stack->size++;
    int *new_data = realloc(stack->data, stack->size * sizeof *stack->data);

    if (!new_data) {
        // error handling here, or just
        abort();
    }
    
    stack->data = stack->new_data;
    stack->data[stack->size - 1] = val;
}

E semelhante para pop(). Observe que é comum ter funções que operam em um objeto que levam o ponteiro para esse objeto como o primeiro parâmetro. Além disso, fiz o retorno da função void, não há necessidade de retornar o tamanho da pilha que a informação já está disponível para o chamador.

Evite usar variáveis ​​globais

Você deve evitar o uso de variáveis ​​globais, se possível. Meu código de exemplo acima não requer mais que haja um global stack. Essa mudança permite que o código gerencie várias pilhas sem conflitos.

Adicione funções para criar e destruir pilhas

Em vez de exigir que o chamador saiba como inicializar corretamente um struct Stacke liberá-lo após o uso, crie funções que façam isso para você. Isso permite que você mude os internos de struct Stackmais tarde, sem ter que mudar todos os lugares onde uma pilha é usada.

Use um prefixo comum para evitar conflitos de nome

push()e pop()são nomes muito genéricos. Há muito mais coisas que podem ter operações push e pop, como filas FIFO. Eu recomendo que você use um prefixo comum para todas as estruturas de dados e funções de sua pilha. Isso pode ser simplesmente Stackou stackse você achar que é improvável que entre em conflito com qualquer outra coisa.