Binary Doodles

I was trying to choose a language that I could use to practice implementation of different data structures and wanted something object oriented that had a syntax that wouldn't distract me away from what I'm trying to learn.

Ruby/Python is too high level if you want to learn how to implement as a stack or a queue. Even a simple array can be directly used as a stack or a queue. C++ syntax, for some reason, annoys me, so that too was rejected.

But hey, there's C. It's doesn't technically qualify as an object oriented language, but I could write C code in such a way that it feels like it. Take, for instance, this bit of how you would use a Stack class in Ruby:

s = Stack.new
s.push(10) # s contains [10]
s.push(42) # s contains [10, 42]
puts s.pop # prints '42'

We could write C code that vaguely resembles the structure of the Ruby code (and still get to use pointers!)

Stack s = Stack_create();
Stack_push(s, 10);
Stack_push(s, 42);
printf("%d ", Stack_pop(s));

Now, let's walk through how we could implement a C structure that behaves like this. First of all we define a struct called STACK. To keep things simple we will limit this stack to integer values only and use a simple array to store the values.

#define MAXSIZE 10

typedef struct STACK {
  int items[MAXSIZE];
  int top;
} STACK;

typedef STACK* Stack;

We have also declared Stack as an alias for a pointer to STACK variables and gotten rid of the annoying asterisks everywhere in our function parameters.

The Stack_create() method should allocate memory for a new stack and return the pointer to it. Also, we'll write a Stack_destroy() method that will free up the allocated memory once we no longer need the stack. We'll also add a Stack_isFull() helper function that returns true if we have reached the limit of the array.

Stack Stack_create() {
  Stack s;
  s = (Stack) malloc(sizeof(STACK));
  s->top = 0;
  return(s);
}

void Stack_destroy(Stack s) { free(s); }

int  Stack_isFull (Stack s) { return(s->top >= MAXSIZE); }

Let's write the Stack_push() and Stack_pop() methods as well:

int Stack_push(Stack s, int item) {
  if(Stack_isFull(s)) return(0); // failed to add
  s->items[s->top] = item;
  return(++(s->top));
}

int Stack_pop(Stack s) {
  (s->top)--;
  return(s->items[s->top]);
}

void Stack_print(Stack s) {
    int i;
    printf("[ ");
    for (i=0; i < s->top; i++) printf("%d ",s->items[i]);
    printf("]\n");
}

Here we've also added a Stack_print helper method to print the content of the stack. We can now test these methods in main():

int main() {
  Stack s = Stack_create();
  Stack_print(s);
  Stack_push(s, 10);
  Stack_print(s);
  Stack_push(s, 42);
  Stack_print(s);
  printf("Pop -> %d \n", Stack_pop(s));
  printf("Pop -> %d \n", Stack_pop(s));

  return 0;
}

The output looks like:

$ ./a.out
[ ]
[ 10 ]
[ 10 42 ]
Pop -> 42
Pop -> 10 

In less than 40 lines of code, we have described a naive stack implementation. We don't get most of the features of real object oriented languages, but the code does feel easier to write this way. I'm not sure how well this approach translates for large projects, but for learning data structure concepts, this is working extremely well for me.

If you want to take a serious look at object orientation in C, this book on object oriented programming in ANSI C [PDF] is a great way to get started.

A gist containing the above code is available here.