2
\$\begingroup\$

I wrote a dynamic stack in C that uses an array as a structure. I tried to maintain O(1) for push and pop and believe I have done so. I want to know what can be written in a cleaner way and if there are any non-trivial bugs.

#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;
}

```
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Realloc is O(n), because it has to copy n elements from old array to new array (n is the smaller of new and old size). Since both push and pop call it in almost all cases, they are O(n) themselves. To get armotized O(1) you should realloc by doubling the size when n is power of two instead of adding one space for every new element. \$\endgroup\$ – slepic Sep 11 '20 at 3:45
  • 1
    \$\begingroup\$ @slepic Good points and suggestions. push O(n) okay, but pop's realloc will not need to do an actual copy. "The function may move the memory block to a new location" so indeed can be said to be O(1). A stack as linked list of oversized fixed-length arrays might even be better. \$\endgroup\$ – Joop Eggen Sep 11 '20 at 7:24
1
\$\begingroup\$

The review by @G. Sliepen is sound and I agree with everything said there. In addition:

  • Never hide pointers behind a typedef! This makes the code very confusing to read for C programmers including yourself. You might think you pass data by value when you aren't, and similar confusing situations.

  • ... = malloc(sizeof(int)); It is inefficient to just allocate 1 item and then almost immediately have to realloc. Note that all dynamic memory location is slow upon creation, and we should drive to minimize the amount of calls to malloc/realloc. Calling them frequently also leads to heap fragmentation, which can lead to wasted memory use and other problems.

    Instead, allocate a "large enough" estimate the first time you call malloc. Maybe 100 items instead. And each time you run out of memory, don't realloc just 1 item more, allocate a lot more and keep track of how much room you have allocated, and how much of that memory you are using.

    Similarly, there is no need to shrink the amount of allocated memory each time you pop something. Deallocation is also slow. Just decrease a counter that keeps track of how much of the allocated memory you are using.

    Stuff like this is what's actually matters when it comes to program performance. "Big O" theory, far less so.

  • stack[(*c)-1] = NULL; is incorrect, a bug. You should never assign NULL to common variables, only to pointers. NULL might as well be defined as a pointer type and then this code would break.

    In fact you don't need to clear non-used memory at all, that's pointless.

  • A style issue, but make it a habit to always use { } even when there is just a single line inside the statement following if/else or loop statements. And avoid sloppy one-liners such as if (!(*c)) return -1;

  • The variable name i should only be used for loop iterators. The name i in a loop actually stands for iterator. Don't use it for other purposes like taking user input.

  • Don't use "magic numbers" in the code, such as else if(i == 3). Use textual constants instead. For example:

      enum
      {
        PUSH  = 1,
        POP   = 2,
        PRINT = 3,
        QUIT  = 4,
      };
    
  • With the above enum, we can clear up the for loop and if statements quite a bit, making the code a bit longer but far more maintainable:

    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)
    

    (Note that I deliberately didn't make user_choice an enum type. I did this only because scanf("%d", &user_choice); on an enum isn't safe. Otherwise, a typedef enum would have been preferable to int.)

\$\endgroup\$
5
\$\begingroup\$

Create a struct that encapsulates all the details of a stack

The problem is that your stack just looks like a pointer to an int, indistinguishable from other pointers to ints. And the first element it points to is treated differently from the other elements. In this case, it is better to create a struct that keeps track of the allocated memory and the size of it, like so:

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

You initialize it as follows:

struct Stack stack = {0, NULL};

Now you should change push() and pop() to take a pointer to a 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;
}

And similar for pop(). Note that it is common to have functions that operate on an object take the pointer to that object as the first parameter. Also, I made the function return void, there is no need to return the size of the stack size that information is already available to the caller.

Avoid using global variables

You should avoid using global variables if possible. My example code above no longer requires there to be a global stack. This change allows the code to manage multiple stacks without conflicts.

Add functions to create and destroy stacks

Instead of requiring the caller to know how to properly initialize a struct Stack and to free it after use, create functions that do this for you. That allows you to change the internals of struct Stack later, without having to change all the places where a stack is used.

Use a common prefix to avoid name conflicts

push() and pop() are very generic names. There are many more things that can have push and pop operations, such as FIFO queues. I recommend you use a common prefix for all data structures and functions for your stack. This can simply be Stack or stack if you think that is unlikely to conflict with anything else.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.