Building a Stack in C From Scratch (and Learning to Love Pointers)

A stack is one of those data structures that sounds boring until you actually build one. It is just a list where you add and remove things from the same end, like a stack of plates. You put a plate on top, and when you need one, you take it off the top. The last plate you put down is the first one you pick up. That behavior has a name: LIFO, which stands for Last In, First Out.

In this post I am going to walk through a complete stack implementation in C, line by line, decision by decision. I will not skip anything. If you are newer to C, this is a great structure to cut your teeth on because it forces you to deal with pointers, dynamic memory, and cleanup, which are the three things that make C both powerful and a little scary.

Here is the full program first, and then we will pull it apart piece by piece.

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

typedef struct Node
{
    int val;
    struct Node *next;
} Node;

typedef struct
{
    Node *node;
} Stack;

int DeleteStack(Stack *stack);

void AutoDeleteStack(Stack **stack_ptr)
{
    if (stack_ptr && *stack_ptr)
    {
        DeleteStack(*stack_ptr);
    }
}

#define AUTO_STACK __attribute__((cleanup(AutoDeleteStack))) Stack *

int PushStack(Stack *stack, int value)
{
    Node *nextNode = (Node *)malloc(sizeof(Node));
    if (nextNode == NULL)
    {
        printf("Memory allocation failed\n");
        return 1;
    }
    nextNode->val = value;
    nextNode->next = stack->node;
    stack->node = nextNode;
    return 0;
}

int PopStack(Stack *stack, int *val)
{
    if (stack->node == NULL)
    {
        printf("Stack is empty\n");
        return 1;
    }
    Node *temp = stack->node;
    if (val != NULL)
        *val = temp->val;
    stack->node = stack->node->next;
    free(temp);
    return 0;
}

int PeekStack(Stack *stack, int *val)
{
    if (stack->node == NULL)
    {
        printf("Stack is empty\n");
        return 1;
    }
    *val = stack->node->val;
    return 0;
}

int SizeStack(Stack *stack)
{
    int size = 0;
    Node *current = stack->node;
    while (current != NULL)
    {
        size++;
        current = current->next;
    }
    return size;
}

bool EmptyStack(Stack *stack)
{
    return stack->node == NULL;
}

Stack *CreateStack(int arr[], size_t length)
{
    Stack *stack = (Stack *)malloc(sizeof(Stack));
    if (stack == NULL)
    {
        printf("Memory allocation failed\n");
        return NULL;
    }
    stack->node = NULL;

    for (size_t i = 0; i < length; i++)
    {
        if (PushStack(stack, arr[i]) != 0)
        {
            DeleteStack(stack);
            return NULL;
        }
    }

    return stack;
}

int DeleteStack(Stack *stack)
{
    while (stack->node != NULL)
    {
        PopStack(stack, NULL);
    }
    free(stack);
    return 0;
}

int main()
{
    int arr[] = {1, 2, 3, 4, 5};
    size_t length = sizeof(arr) / sizeof(arr[0]);
    AUTO_STACK stack = CreateStack(arr, length);

    int val;
    int err = PeekStack(stack, &val);
    if (err != 0)
    {
        printf("Error peeking stack\n");
        return 1;
    }
    printf("Top of stack: %d\n", val);
    printf("Size of stack: %d\n", SizeStack(stack));

    err = PushStack(stack, 69);
    if (err != 0)
    {
        printf("Error pushing to stack\n");
        return 1;
    }
    int size = SizeStack(stack);
    printf("Size of stack after pushing 69: %d\n", size);

    while (!EmptyStack(stack))
    {
        PopStack(stack, &val);
        printf("Popping: %d\n", val);
    }

    printf("Stack is now empty.\n");

    return 0;
}

That is the whole thing. Now let us go through it.

Choosing how to store the data

The first big decision with any stack is how you store the items underneath. There are two common choices: a growable array, or a linked list. This implementation uses a linked list, so let us talk about why that is a reasonable pick.

With an array, you get everything sitting next to each other in memory, which is fast and cache friendly. The downside is that when the array fills up, you have to allocate a bigger one and copy everything over. With a linked list, each item lives in its own little box in memory, and each box knows where the next box is. Adding an item never requires copying anything. You just make a new box and point it at the old top. The trade off is that the boxes are scattered around memory, so a linked list is usually a little slower to walk through, and every item costs you an extra pointer of memory.

For a learning project, and honestly for a lot of real programs, the linked list version is a clean choice because pushing and popping are always fast and you never have to think about resizing.

The Node struct

typedef struct Node
{
    int val;
    struct Node *next;
} Node;

This is the box I keep talking about. Each Node holds two things: the actual value we care about (val, an integer), and a pointer to the next node in the chain (next).

Notice the slightly awkward struct Node *next inside the struct. You have to write struct Node there, spelled out in full, rather than just Node. That is because at the moment the compiler is reading that line, the typedef that gives us the short name Node has not finished yet. The struct is still being defined. So we reach for the full name struct Node, which is available because we named the struct on the first line (struct Node). This is called a self referential struct, and it is the backbone of every linked structure in C.

The Stack struct

typedef struct
{
    Node *node;
} Stack;

This one is tiny. The Stack is just a wrapper that holds a single pointer to the top node of the chain. That is it. When the stack is empty, this pointer is NULL. When you push something, this pointer moves to point at the new top.

You might ask why we bother wrapping a single pointer in a struct at all. Why not just pass around a Node * directly? Two reasons. First, it reads better: a function that takes a Stack * clearly works on a stack, while a function taking a Node * is vague. Second, it gives us room to grow. If later we want to store the size, or a maximum capacity, or some other bookkeeping, we just add a field to Stack and none of the function signatures have to change. This is a small design habit that pays off later.

Also notice this struct is anonymous. There is no name between struct and the opening brace, because unlike Node, the Stack never needs to refer to itself.

A quick word on the return code style

Before we hit the functions, look at the pattern that shows up over and over: most functions return an int, where 0 means success and a non zero value means something went wrong. The functions that produce a value do not return that value directly. Instead they take a pointer, and they write the result into wherever that pointer points.

This is a very common C convention, and it exists because C functions can only return one thing. If PeekStack returned the top value directly as an int, then what would it return when the stack is empty? It could return 0, but then you could never tell the difference between "the stack is empty" and "the top of the stack is genuinely the number 0". By splitting the two jobs apart, the return code tells you whether it worked, and the out parameter carries the value, we sidestep that ambiguity completely. You will see this style all over real C code, so it is worth getting comfortable with it.

PushStack: adding to the top

int PushStack(Stack *stack, int value)
{
    Node *nextNode = (Node *)malloc(sizeof(Node));
    if (nextNode == NULL)
    {
        printf("Memory allocation failed\n");
        return 1;
    }
    nextNode->val = value;
    nextNode->next = stack->node;
    stack->node = nextNode;
    return 0;
}

Pushing is where the linked list magic happens, and it is only three real lines of work.

First we ask the operating system for memory to hold a brand new node, using malloc(sizeof(Node)). The sizeof(Node) part means "however many bytes one Node takes up", so we never have to hardcode a number. malloc hands back a pointer to that fresh chunk of memory.

Then comes a check that a lot of beginners skip: if (nextNode == NULL). malloc can fail. If the machine is out of memory, it returns NULL instead of a valid pointer. If we did not check, and we went ahead and wrote to that NULL pointer, the program would crash. So we check, print a message, and bail out with a return code of 1 to signal failure. Checking every allocation is one of those habits that separates code that works on your machine from code that works everywhere.

Now the three lines that actually do the work:

• nextNode->val = value; stores the value in the new node.
• nextNode->next = stack->node; points the new node at whatever used to be the top. If the stack was empty, stack->node was NULL, so the new node points at NULL, which is exactly right because it will be the only node.
• stack->node = nextNode; moves the stack's top pointer to the new node.

The order matters here. We hook the new node onto the old top before we move the top pointer. If we did it the other way around, we would lose track of the old chain entirely. Draw it on paper once and it clicks: new node points down at the old top, then the stack's handle slides up to the new node.

Because we never touch any other node, pushing is always fast no matter how big the stack gets. In Big O terms that is O(1), constant time.

PopStack: removing from the top

int PopStack(Stack *stack, int *val)
{
    if (stack->node == NULL)
    {
        printf("Stack is empty\n");
        return 1;
    }
    Node *temp = stack->node;
    if (val != NULL)
        *val = temp->val;
    stack->node = stack->node->next;
    free(temp);
    return 0;
}

Popping is the reverse of pushing, plus a bit of care around memory.

First we guard against popping an empty stack. If stack->node is NULL, there is nothing to remove, so we print a message and return 1.

Then we grab a temporary pointer, temp, to the current top node. We need this because we are about to move the stack's top pointer away, and if we did not save the old top somewhere, we would have no way to free its memory. That is a classic way to leak memory: unhook a node and forget to release it.

Next, if (val != NULL) *val = temp->val;. This is a small but important design choice. The caller can pass a pointer if they want the popped value handed back to them, or they can pass NULL if they just want the item gone and do not care about its value. The check means passing NULL is completely safe: we only write the value out if there is somewhere to write it to. This flexibility matters in a moment when we look at DeleteStack.

Then stack->node = stack->node->next; moves the top pointer down to the second node, effectively cutting the old top out of the chain. Finally free(temp) returns the old top's memory to the system. Every malloc needs a matching free, and this is where a pushed node eventually gets released.

Like push, pop only ever touches the top node, so it is also O(1).

PeekStack: looking without removing

int PeekStack(Stack *stack, int *val)
{
    if (stack->node == NULL)
    {
        printf("Stack is empty\n");
        return 1;
    }
    *val = stack->node->val;
    return 0;
}

Sometimes you want to know what is on top without taking it off. That is peek. It is almost identical to pop, but without the removal and the freeing. It checks for an empty stack, then copies the top value into the caller's val pointer, and returns 0.

One thing to notice: unlike PopStack, this one does not check whether val is NULL before writing to it. That is a reasonable choice, because peeking without wanting the value back would be pointless. There is no reason to call peek and pass NULL, so the function assumes you gave it a real pointer.

SizeStack: counting the items

int SizeStack(Stack *stack)
{
    int size = 0;
    Node *current = stack->node;
    while (current != NULL)
    {
        size++;
        current = current->next;
    }
    return size;
}

This walks the chain from top to bottom, counting as it goes. We start a counter at zero and a current pointer at the top node. As long as current is not NULL, we add one to the count and follow the next pointer to the following node. When current finally becomes NULL, we have walked off the end of the chain and the count is complete.

This is worth pausing on, because it is the standard way you traverse any linked list in C. The current = current->next line is the engine of the whole loop: it hops from one node to the next until it runs out of nodes.

One honest trade off here: counting this way is O(n), meaning the time it takes grows with the number of items, because we visit every single node. If you needed size to be instant, you would store a counter inside the Stack struct and bump it up in push and down in pop. For a small learning stack, walking the chain is perfectly fine and keeps the struct simple. This is exactly the kind of thing that wrapper Stack struct would make easy to add later.

EmptyStack: a tiny but useful helper

bool EmptyStack(Stack *stack)
{
    return stack->node == NULL;
}

This returns true if the stack has nothing in it, and false otherwise. The whole test is just "is the top pointer NULL".

You might think this is too small to deserve its own function. Why not just write stack->node == NULL wherever you need it? The answer is readability and intent. When someone reads while (!EmptyStack(stack)) in the main loop, they instantly understand it means "keep going while the stack has items". Compare that to while (stack->node != NULL), which makes the reader stop and decode what the condition means. It also keeps the internals of the stack hidden. If we ever changed how emptiness is represented, every caller keeps working because they go through this one function. This is a small example of encapsulation, and it uses the bool type from stdbool.h, which is why that header is included at the top.

CreateStack: building a stack from an array

Stack *CreateStack(int arr[], size_t length)
{
    Stack *stack = (Stack *)malloc(sizeof(Stack));
    if (stack == NULL)
    {
        printf("Memory allocation failed\n");
        return NULL;
    }
    stack->node = NULL;

    for (size_t i = 0; i < length; i++)
    {
        if (PushStack(stack, arr[i]) != 0)
        {
            DeleteStack(stack);
            return NULL;
        }
    }

    return stack;
}

This is a convenience function that takes a plain C array and turns it into a full stack in one call.

We start by allocating the Stack struct itself with malloc, and of course we check that allocation for failure, same as before. If it fails, we return NULL so the caller knows there is no stack. Right after allocating, we set stack->node = NULL. This is critical. Fresh memory from malloc contains garbage, not zeros. If we did not set the top pointer to NULL, the stack would start out thinking it had a node at some random address, and the first operation would crash or misbehave. Always initialize your pointers.

Then we loop through the array and push each element. Notice the loop counter is declared as size_t i, not int i. This matches the type of length, which is also size_t. size_t is the unsigned type C uses for sizes and counts. If we mixed an int counter with a size_t length, the compiler would warn about comparing a signed and an unsigned value, and for very large arrays it could even behave incorrectly. Matching the types keeps everything clean and warning free.

There is a nice bit of error handling inside the loop. If any PushStack fails, which would only happen if memory ran out partway through, we do not just return NULL and walk away. We first call DeleteStack(stack) to clean up everything we built so far, and then return NULL. Without that cleanup, a failure halfway through would leave a partly built stack floating in memory with no way to reach it, which is a memory leak. Handling the partial failure properly is the kind of detail that is easy to skip and annoying to debug later.

One small thing worth knowing: because we push the array in order, the last element of the array ends up on top of the stack. Push 1, 2, 3, 4, 5 and the top will be 5. That is just how a stack works, but it can surprise you the first time.

DeleteStack: tearing it all down

int DeleteStack(Stack *stack)
{
    while (stack->node != NULL)
    {
        PopStack(stack, NULL);
    }
    free(stack);
    return 0;
}

Everything you malloc you must eventually free, and this function is where the whole stack gets cleaned up. It works in two stages.

First, it pops every node off until the stack is empty. Here is where that earlier design choice pays off: we call PopStack(stack, NULL). We pass NULL for the value pointer because during teardown we genuinely do not care about the values, we just want the nodes gone. Because PopStack checks for NULL before writing, this is completely safe. Each pop frees one node's memory.

Once the loop finishes and all nodes are freed, we free(stack) to release the Stack struct itself. Remember there were two kinds of allocations: the individual nodes, and the wrapper struct. Both have to be freed, and in the right order. If we freed the struct first, we would lose the pointer to the nodes and leak all of them. So nodes first, struct last.

You may have noticed DeleteStack is declared once near the top of the file, before it is defined, in a line called a forward declaration (int DeleteStack(Stack *stack);). That is there because CreateStack and AutoDeleteStack both call DeleteStack before the compiler has actually seen its full definition further down. The forward declaration is a promise to the compiler: "this function exists, here is its shape, trust me, the body is coming later." Without it, the compiler would complain that it does not know what DeleteStack is.

The automatic cleanup trick

This is the fanciest part of the whole program, and it is optional sugar rather than core stack logic, but it is genuinely useful so let us unpack it.

void AutoDeleteStack(Stack **stack_ptr)
{
    if (stack_ptr && *stack_ptr)
    {
        DeleteStack(*stack_ptr);
    }
}

#define AUTO_STACK __attribute__((cleanup(AutoDeleteStack))) Stack *

The problem this solves is a familiar one in C: it is easy to forget to call DeleteStack before your variable goes out of scope, and then you leak memory. Wouldn't it be nice if cleanup happened automatically when the variable disappears, the way destructors work in C++? It turns out that with the GCC and Clang compilers you can get exactly that, using a feature called the cleanup attribute.

When you tag a variable with __attribute__((cleanup(SomeFunction))), the compiler promises to call SomeFunction automatically the moment that variable goes out of scope, and it hands that function the address of the variable. That is why AutoDeleteStack takes a Stack **, a pointer to a pointer. The variable itself is a Stack *, so the address of it is a Stack **.

Inside AutoDeleteStack, we check that both the outer pointer and the actual stack are not NULL (if (stack_ptr && *stack_ptr)) before calling DeleteStack. This guards against cleaning up a stack that was never successfully created, for instance if CreateStack had returned NULL.

The #define AUTO_STACK line is just a shortcut so we do not have to type that long attribute every time. After the macro, writing AUTO_STACK stack = ... expands to __attribute__((cleanup(AutoDeleteStack))) Stack *stack = .... Clean and readable.

I want to be honest about one thing: this cleanup attribute is not standard C. It is a GCC and Clang extension. It will not compile on Microsoft's MSVC compiler. So if you care about your code working on every compiler out there, you would skip this and just call DeleteStack by hand. But if you know you are on GCC or Clang, it is a lovely way to make memory leaks much harder to cause by accident. It is a great trick to have in your back pocket.

Tying it together in main

int main()
{
    int arr[] = {1, 2, 3, 4, 5};
    size_t length = sizeof(arr) / sizeof(arr[0]);
    AUTO_STACK stack = CreateStack(arr, length);
    ...
}

The main function ties everything together and doubles as a little test drive.

We start with a plain array of five integers. The line size_t length = sizeof(arr) / sizeof(arr[0]); is the standard C idiom for figuring out how many elements an array has. sizeof(arr) is the total size of the whole array in bytes, and sizeof(arr[0]) is the size of one element. Divide the total by the size of one, and you get the count. This only works on real arrays, not on pointers, but here arr is a genuine array so it is perfect. It also means if you add or remove elements from the array, the count updates itself with no editing required.

Then AUTO_STACK stack = CreateStack(arr, length); builds the stack and, thanks to the macro, arranges for it to be automatically cleaned up when main ends. We never have to remember to call DeleteStack ourselves. That is the whole payoff of the cleanup trick.

The rest of main exercises the stack. It peeks at the top, checking the return code and bailing out if peeking failed. It prints the size. It pushes a new value, 69, again checking for failure, and prints the new size to show the stack grew. Then it drains the stack with while (!EmptyStack(stack)), popping and printing each value until nothing is left.

That drain loop is worth appreciating. Because it is driven by EmptyStack rather than a hardcoded count, it correctly handles the fact that we pushed an extra element earlier. An older version of this code might have looped exactly five times, which would have been wrong after the push. Letting the stack itself tell us when it is empty is more robust than counting by hand.

When you run it, the output looks like this:

Top of stack: 5
Size of stack: 5
Size of stack after pushing 69: 6
Popping: 69
Popping: 5
Popping: 4
Popping: 3
Popping: 2
Popping: 1
Stack is now empty.

Notice the order things come out: 69 first because it was pushed last, then 5, 4, 3, 2, 1. That is LIFO in action. Last in, first out.

What I would do next

This implementation is solid, correct, and leak free, which is a great place to be. If I wanted to keep improving it, here is where I would look.

The biggest thing is that every function assumes you hand it a valid, non NULL stack. If CreateStack ever failed and returned NULL, and you called PeekStack on that NULL right away, you would crash. In practice malloc almost never fails for a tiny struct, so you will likely never hit it, but a truly defensive version would either check for NULL right after creating the stack, or add a NULL guard at the top of each function.

The other thing I keep going back and forth on is the printf calls buried inside the stack functions. Printing "Stack is empty" from inside PopStack is friendly for a learning program, but if this were a reusable library, a printed message would be an odd thing to force on every user. A library version would just return the error code and let whoever is calling decide whether and how to report it. For a personal project though, the printouts make it easy to see what is going on, so they earn their keep here.

Neither of these is a bug. They are the difference between "works great for me" and "works great as a library other people depend on", and knowing which one you are building is half the battle.

Wrapping up

A stack is a small data structure, but building one in C touches almost everything that makes the language what it is: structs, pointers, dynamic memory, matching every allocation with a free, self referential types, forward declarations, and even a compiler extension for automatic cleanup. If you understand every line above, you understand a real slice of practical C.

The best way to make it stick is to break it. Delete the stack->node = NULL line in CreateStack and watch it misbehave. Remove the NULL check in PopStack and see what happens during deletion. Draw the push operation on paper with arrows. Data structures stop being scary the moment you build one with your own hands, and a stack is the perfect place to start.