Simple Stacks! A Gentle Approach

Welcome to my Simple Stacks tutorial! By all means, this is not the best nor greatest implementation but I'm sure you'll learn something new if you're just starting out. I also acknowledge I could have done a lot cooler looking stuff in C++ but that's just boring.

First off, we start with the header file:

#ifndef SIMPLESTACK_H_INCLUDED
#define SIMPLESTACK_H_INCLUDED

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

/*
    It's probably a good idea to have some definite limit on the size of your data structures. For one,
    it'll be a lot harder to manage if you're careless.

    I imagine you could render this constant useless by setting it to -1 if you wanted to remove the limit.
*/
#define MAX_STACK_SIZE 50

/*
    I also like to have a constant defined to turn debugging messages on and off quickly and easily.
*/
#define STACK_DEBUG_MODE 1

/*
    Below is the basic structure of the stack.
    In this example, I'm using characters,
    just by random choice. However, you could use any
    data type really.

    Basically, it holds 2 pieces of data:
        - An array
        - The size of the stack, as 'unsigned short'.
*/
typedef unsigned short ushort;

typedef struct
{
    char* data;
    ushort size;
} SimpleStack;

/*
    You can find explainations and discussion
    about these procedures below.
*/
SimpleStack CreateStack(void);

void FreeStack(SimpleStack*);

ushort StackPush(SimpleStack*, char);

char StackPop(SimpleStack*);

char StackTop(SimpleStack*);

void ReportError(const char*);

#endif // SIMPLESTACK_H_INCLUDED

To make life easier, we will make a simple procedure that creates a new stack object for us when we need to use one. It saves the hassle of having to mess with malloc() and what not every time you need to use a stack.

SimpleStack CreateStack(void)
{
    SimpleStack newStack;

    newStack.data = (char*) malloc(sizeof(char));
    if (newStack.data == NULL)
    {
        ReportError("There's not enough memory to create a new stack!");
    }

    newStack.size = 1;

    return newStack;
}

I use pointers here but don't worry, they're not as scary as some people make them out to be, haha.

What makes pointers so useful is that not only can they be used as super-powerful references but they can also be used to dynamically allocate memory on the heap. This isn't really a pointers tutorial but I'm sure there are some decent ones around here on these forums.

This is the only procedure that passes by value. From now on, we will be passing by pointer. Although it's not that much of an issue with small data structures, performance issues can arise when they are large in size so it's best to get into the habit of passing by reference or pointer with objects, especially those that have the potential to take up a lot of memory, as soon as you can.

If you're new to C, you may not have seen malloc() before. malloc() is a powerful tool at every C programmer's disposal. You may be used to and possibly even been frustrated by the fact you have to predetermine every array you declare. Well, malloc() is the answer to that problem and allows you to, when coupled with pointers, to create dynamic arrays at run time. However, if you do ever need to use it, be aware that it expects you to give the size of the block you're allocating in bytes and not as the actual array length as I've witnessed before. You have to multiply the size of the data type you wish to allocate by the number of elements you need.

Oh and one more thing, don't use malloc() in C++, it has a much nicer alternative and a hell of a lot less confusing to new blood.

Since we're using the malloc() procedure, it's probably a wise idea to have some sort of method to help us safely remove unused stacks and free up the memory we allocated.

Infact, I can't stress to you enough how important it is. No one likes memory leaks and they especially don't like people who don't make an effort to stop them from happening. Although, I'm not saying you're one of them!

void FreeStack(SimpleStack* stackObj)
{
    free(stackObj->data);
    stackObj = NULL;
}

Also, take notice that we're now passing by pointer. Again, if you're new, the star next to the type name could have easily been missed.

Anyway, it just wouldn't be a stack implementation without the famous Push and Pop procedures.

Pushing data on to the stack is pretty straight forward but if you're new to C, you might not have come across realloc() yet. Good thing I'm here to explain it to you, eh?

As malloc() allows you allocate a block of memory dynamically, realloc() allows you to change the size of the block dynamically. It really comes in use when memory usage is restricted, though it's not something you can always rely on.

Obviously, this 'pushes' a new item on to the top of the stack, returning 1 on success or 0 on failure.

Here I reallocate the newly sized memory block to a temporary object. That way, if it failed, there's no risk of your original stack object being lost, which I imagine would be a total pain in the arse.

ushort StackPush(SimpleStack* stackObj, char item)
{
    if (stackObj->size == MAX_STACK_SIZE)
    {
        ReportError("Error: Maximum stack size has been exceeded");
        return 0;
    }

    char* tempObj = (char*) realloc(stackObj->data, sizeof(char) * ++stackObj->size);
    if (tempObj == NULL)
    {
        ReportError("There's not enough memory to push a new item on the stack!");
        return 0;
    }

    tempObj[stackObj->size - 1] = item;

    stackObj->data = tempObj;

    free(tempObj);

    return 1;
}

Again, same scenario as the Push procedure, just the opposite way round:

char StackPop(SimpleStack* stackObj)
{
    char item = '\0';

    if (stackObj->size == 0)
    {
        ReportError("Error: There are no data elements on this stack!");
        return (char) NULL;
    }

    else
    {
        stackObj->size--;
        item = stackObj->data[stackObj->size];
        stackObj->data[stackObj->size + 1] = (char) NULL;

        char* tempObj = (char*) realloc(stackObj->data, sizeof(char) * stackObj->size);
        if (tempObj == NULL)
        {
            ReportError("Could not pop the item off the stack!");
            return (char) NULL;
        }
    }
   
    stackObj = tempObj;
    free(tempObj);

    return item;
}

And finally, a procedure to look at the top of the stack, which is probably the simplest stack procedure of them all:

char StackTop(SimpleStack* stackObj)
{
    if (stackObj->size == 0)
    {
        ReportError("Error: There are no data elements on this stack!");
        return (char) NULL;
    }

    return stackObj->data[stackObj->size - 1];
}

Also, if you're copying things down from here, you'll want this procedure too:

void ReportError(const char* message)
{
    if (STACK_DEBUG_MODE == 1) perror(message);
}

Anyway, that just about wraps it up. Although this was pretty easy going, it'll come in great use when I write my next tutorial on converting infix expressions to postfix form (Reverse Polish Notation) and then evaluating it.

Thanks for your time, I hope you enjoy! ^^

Also, I've attached the source file. It isn't commented because I explained all of it in this post.