Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
#include <stdio.h>
#include <stdlib.h>

struct Stack {
  int value;
  int is_empty;
  struct Stack *next;
};

int pop(struct Stack **stack) {
  if ((*stack)->is_empty == 1) {
    printf("Stack is empty!\n");
    abort(); // not sure what this does
  } else {
    int value = (*stack)->value;
    // outer pointer (static) points to new stack now
    *stack = (*stack)->next;
    return value;
  }
}

void push(struct Stack **stack, int value) {
  // malloc is used so this memory can be accessed outside of scope
  struct Stack *head = malloc(sizeof(struct Stack*));
  if (head != NULL) {
    head->value = value;
    // head's next is pointer to stack
    head->next = *stack;
    head->is_empty = 0;
    // stack now holds pointer to head
    *stack = head;
  } else {
    printf("push memory no alloc");
  }
}

struct Stack *empty() {
  struct Stack *head = malloc(sizeof(struct Stack *));
  if (head != NULL) {
    head->value = 0;
    head->is_empty = 1;
    head->next = NULL;
    return head;
  } else {
    return NULL;
  }
}

int main() {
  struct Stack *init = empty();
  struct Stack **stack = &init;
  push(stack, 3);
  push(stack, 2);
  push(stack, 1);
  int one = pop(stack);
  printf("one: %d\n", one);
  int two = pop(stack);
  printf("two: %d\n", two);
  int three = pop(stack);
  printf("three: %d\n", three);
  //int hmm = pop(stack);
}

I'm not sure pointers to pointers is the best way to do this. I also feel like I'm writing code in a Java-y way, and would like to know how to improve my C style.

Also, are there any edge cases I am missing?

share|improve this question
add comment

2 Answers

up vote 12 down vote accepted

Things you did well:

  • Overall the code looks very nice and well organized.

  • You used comments well.

Things you could improve:

Syntax:

  • typedef your structs.

    struct Stack {
      int value;
      int is_empty;
      struct Stack *next;
    };
    

    The typedef means you no longer have to write struct all over the place. That not only saves some space, it also can make the code cleaner since it provides a bit more abstraction.

    typedef struct
    {
        int value;
        int is_empty;
        struct Stack *next;
    } Stack;
    
  • You can simplify your NULL checks.

    if (head != NULL)
    

    Since NULL is defined as (void *)0, we can treat is as a comparison to 0, making the != NULL a redundant check.

    if (head)
    
  • If you don't take in any variables as parameters, you should declare them as void.

    int main(void)
    

Error handling:

  • Don't use abort(). The function raises the SIGABRT signal. This, if uncaught, causes the program to terminate returning a platform-dependent unsuccessful termination error code to the host environment. The program is terminated without destroying any object and without calling any of the functions passed to atexit or at_quick_exit. It would be much better to return an error indicator and have the calling function handle it.

    return -1; // we have an error
    

Memory usage:

  • You never free() your init value.

    struct Stack *init = empty();
    
    // within empty()
    struct Stack *head = malloc(sizeof(struct Stack *));
    return *head;
    

    You should probably free() it before your program terminates. Failure to deallocate memory using free() leads to buildup of non-reusable memory, which is no longer used by the program. This wastes memory resources and can lead to allocation failures when these resources are exhausted.

    free(init);
    

Returning:

  • You don't return a value from main(), even though you state you do.

    int main() {
        // no return value... no indication of successful exit
    }
    

    Returning 0 is usually a typical indication of a successful exit.

    return 0;
    
share|improve this answer
    
I also never free head, in push. Should I do that, and if so, where? EDIT: That may be a stupid question. Rather, should I be freeing memory in pop somewhere? –  dysruption Feb 26 at 4:27
    
@dysruption You return the allocated memory (head) and assign it to init, so init is the only variable you have to free(). See this answer for more clarification. –  syb0rg Feb 26 at 4:29
    
how about in pop? is there dead memory there? –  dysruption Feb 26 at 4:31
    
@dysruption When you typedef your struct, and get rid of all the superfluous struct text, you will get a warning: "Incompatible pointer types assigning to struct Stack * from Stack *". I'll leave that up to you to fix though. –  syb0rg Feb 26 at 4:39
1  
@dysruption Lines 18 and 29. If compiling with GCC, enable compiler warnings with -Wall. –  syb0rg Feb 26 at 4:57
show 1 more comment

Your calls to malloc(sizeof(struct Stack *)) are wrong. That does not allocate enough memory to hold one stack element. Rather, it allocates enough memory to contain one pointer. You want malloc(sizeof(struct Stack)).

You provide push() and pop(), but those two operations aren't enough to make a useful stack. At the minimum, you should also provide an is_empty() function. Otherwise, it wouldn't be fair to expect users to know when it is safe to pop an element. (They would have to keep track of the stack size themselves, which means that your data structure isn't doing its job.) Also consider adding a peek() function.

I find that empty() is an odd name for a constructor. Something like new_stack() would be clearer.

The stack, being a data structure, acts as a "library". To remain generic and reusable, library code should avoid having side effects. In particular,

  • Calling abort() is antisocial. If you detect an error, then you should return an error code. As an alternative, an assertion might be acceptable. Another crappier alternative would be to not check at all, and just declare that popping an empty stack has undefined behaviour (i.e., it probably crashes). Calling abort() is odd in that you are expending effort to detect the error, but deliberately taking an action that violates expectations of how a library should behave.
  • Don't print error messages. If you must print something, print to stderr to avoid contaminating the output.

In this case, I think that returning an error code would make the interface too much of a pain to use. Using an assertion would be the way to go, in my opinion.

share|improve this answer
    
I appreciate it. In my pop function - do I need to free the memory of the initial Stack? Or does it get deallocated after there is no longer a reference to it? –  dysruption Feb 27 at 1:18
    
Nothing in C is automatic. Every pointer returned by malloc() must eventually be free()d. Otherwise, it's a memory leak. So yes, you have a memory leak in pop(). –  200_success Feb 27 at 2:36
    
How does this look? –  dysruption Feb 27 at 4:43
    
Better! I suggest that you pose it as a second question on Code Review. Mention that it is a follow-up to this question. –  200_success Feb 27 at 7:14
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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