If you want to reverse the order of a list, trace back memory jumps or implement undoing commands you may want to use a stack. A stack is part of the STL in C++ as std::stack<T>, where T stands for the type you want the collection to be of.
In C there is no stack class in standard implementation so we have to rely on our own programming skills. The goal of this article is to implement a stack container class in modern C.
If you need an overview of different containers and their advantages and disadvantages you can find them in my article here.
In this Article...
How a Stack works
A stack is a container that works according to the Last In First Out (FIFO) principle. You push the new data on top of the stack and always get elements from the top. In contrast to other containers (e.g. Linked List or Vector) you cannot access any elements with a stack, but only the last one you inserted.
For our elements we will have a sort of dynamic array that we resize everytime that an element is added or removed.
One could also reserve some memory in advance and only increase if the stack gets bigger. This is up to the developer implementing the stack class and as always weighs in the space vs. speed discussion.
Stack with 0 Elements
When there are no elements in the stack we only have the size element in the struct that really occupies memory and tells us that the stack is empty.
Stack with 1 Element
With one element on the stack we can access this element by calling top(…) and size will return a 1.
Stack with 3 Elements
With three elements on the stack we now can access only the last one we insterted. In order to pop(…) the 1 from the stack we first would have to remove the 3 and then the 2. The size is 3 as expected.
Stack Based Memory Allocation
One use case for a stack container may be the stack based memory allocation. A certain amount of memory is reserved as so called stack memory. Following is a very simple description:
Every time you need memory (i.e. for a variable declaration), a stack pointer is moved by the length of the reserved memory (i.e. 4 Bytes) and the memory is now used by this variable. This means that you can only free memory in the reverse order you reserved it.
Also be aware of a Stack Overflow which occurs if you reserve more memory than was originally allocated by the stack.
Goals of the Stack Implementation in C
We will implement a Stack Class in C that is capable of the following features:
- Initializing a Stack (and clean up!)
- Adding Elements to the Stack
- Accessing Elements from Stack
- Removing Elements from the Stack
- Swapping complete Stacks
We will only implement a Stack for the Integer (int) type. The C language is missing the <template> stuff that C++ provides so you have to make an implementation for every type that you need. (You maybe could use void-Pointers but that is a rabbit whole of it’s own…)
A Note on Double Ended Queues
A dequeue (double ended queue) is a combination of a queue (read more about queues here) and a stack. It can be accessed from both sides and therefore does not guarantee FIFO or LIFO element access.
We will not cover this special type of queue in this article but together with the information from the queue article you may want to implement a dequeue for yourself.
Stack Initialization in C
We will need three files for our implementation:
- stack.h – here we define the Interface for our Stack
- stack.c – the actual Stack implementation
- main.c – here we write a little program to test our Stack
The stack_t struct contains the elements we want to store and a size which tells us how many elements are currently stored within the stack.
The header file serves as Interface for our Stack “Class”. The struct is declared anonymusly because the members will be private.
#pragma once
typedef struct stack_t stack_t;
stack_t* stack_new();
void stack_ctr(stack_t* obj);
void stack_dtr(stack_t* obj);The struct contains the elements that were described above. The new(), ctr() and dtr() functions imitate the behaviour of a class which I described more deeply in the article about classes in C. In the destructor we make sure to separatly free the elements if they are allocated to any heap memory.
#include "stack.h"
#include <stdlib.h>
typedef struct stack_t {
int* elements;
int size;
} stack_t;
stack_t* stack_new()
{
return (stack_t*) malloc(sizeof(stack_t));
}
void stack_ctr(stack_t* obj)
{
obj->elements = calloc(0, sizeof(int));
obj->size = 0;
}
void stack_dtr(stack_t* obj)
{
if(NULL != obj) {
if(NULL != obj->elements) {
free(obj->elements);
}
free(obj);
}
}The first test program does nothing besides creating and destroying a stack object. Its only purpose is to test the functions we just implemented.
#include "stack.h"
int main(int argc, char** argv)
{
stack_t* my_stack = stack_new();
stack_ctr(my_stack);
stack_dtr(my_stack);
return 0;
}Adding an Element to a Stack in C
There is only one way to add an element to the stack via its push(…) function. However, in C++ there also is a function called emplace(…) which also adds an element to the end of the list but also creates the object for it in place. Since we don’t have Objects in the C++ sense we don’t really need another function.
The interface for these functions is simple, it only takes the object and the element that we want to add.
...
void stack_push(stack_t* obj, int element);
void stack_emplace(stack_t* obj, int element);
...The emplace(…) function just forwards to push(…). There we make space for the new element in the elements array via realloc(..). Then put the element at the end of the list, which in our case represents the top of the stack.
...
void stack_push(stack_t* obj, int element)
{
if(NULL == obj) {
return;
}
obj->size++;
obj->elements = (int*)realloc(obj->elements, obj->size);
obj->elements[obj->size-1] = element;
}
void stack_emplace(stack_t* obj, int element)
{
stack_push(obj, element);
}
...We now add two numbers to our stack in the test program. There is still no output yet, but this will change in the next paragraph.
#include "stack.h"
int main(int argc, char** argv)
{
stack_t* my_stack = stack_new();
stack_ctr(my_stack);
stack_push(my_stack, 1);
stack_emplace(my_stack, 2);
stack_dtr(my_stack);
return 0;
}Getting Information about the Stack
In the C++ STL implementation there are two capacity functions for a stack to get some information about its content. The first checks if a stack is empty, the second returns the size of the stack. In C there is originally no bool data type. We could use int, but I will include stdbool as it makes the intent of the function clearer.
#pragma once
#include <stdbool.h>
...
bool stack_empty(stack_t* obj);
int stack_size(stack_t* obj);
...The implementation is really simple because we only have to check if there size equals zero in the empty(…) function and return the current size in the size(…) function.
...
bool stack_empty(stack_t* obj)
{
return (0 == obj->size);
}
int stack_size(stack_t* obj)
{
return obj->size;
}
...Now we are able to get some information about our stack. We add some messages to our test program and therefore will get some output in the console. For this to happen we have to include stdio.h.
#include "stack.h"
#include <stdio.h>
int main(int argc, char** argv)
{
stack_t* my_stack = stack_new();
stack_ctr(my_stack);
if(stack_empty(my_stack)) {
printf("Stack is empty at startup!\n");
}
printf("Stack Size: %d\n", stack_size(my_stack));
stack_push(my_stack, 1);
stack_emplace(my_stack, 2);
if(!stack_empty(my_stack)) {
printf("Stack List is filled!\n");
}
printf("Stack Size: %d\n", stack_size(my_stack));
stack_dtr(my_stack);
return 0;
}The output shows us wheter the stack is empty or not and how many elements are currently stored.
Stack is empty at startup!
Stack Size: 0
Stack List is filled!
Stack Size: 2Accessing Stack Elements in C
As already described, there is no way to access any element directly within the stack. This would completely contradict the sense of the data type. Instead you can only “see” the top element of the stack.
The top(…) element is the last element you put onto the stack and the only one you can acess. This preserves the Last In First Out (LIFO) principle. Our declaration of the interface is simple:
...
int stack_top(stack_t* obj);
...In the definition we guard against NULL and also return zero if there are no elements on the stack. If there are elements we simply return the last one that was put onto the stack.
...
int stack_top(stack_t* obj)
{
if(NULL == obj || obj->size == 0) {
return 0;
}
return obj->elements[obj->size-1];
}
...We now add a query for the top element to our test program. In order to keep the output clean we remove the calls to empty(..) and the corresponding output.
...
int main(int argc, char** argv)
{
stack_t* my_stack = stack_new();
stack_ctr(my_stack);
printf("Stack Size: %d\n", stack_size(my_stack));
stack_push(my_stack, 1);
stack_emplace(my_stack, 2);
printf("Stack Size: %d\n", stack_size(my_stack));
printf("Top Element of the Stack is: %d\n", stack_top(my_stack));
stack_dtr(my_stack);
return 0;
}So now we see the size of the stack and the current top element in our console.
Stack Size: 0
Stack Size: 2
Top Element of the Stack is: 2Removing Stack Elements in C
We learned in the last paragraph that we can only “see” the top element of the stack. Therefore we are only able to remove this element. If we put the numbers 1, 2 and 3 onto the stack we first have to remove 3 and then 2 to get back to the 1.
The function that removes the top element from the stack is called pop(…). Its declaration in the interface looks like this:
...
void stack_pop(stack_t* obj);
...Another straight forward implementation follows. The ever present guard clause protects us against bad input. Then we decrement the size of the stack and reallocate the memory for our elements so that the allocated memory is shrunk.
...
void stack_pop(stack_t* obj)
{
if(NULL == obj || obj->size == 0) {
return;
}
obj->size--;
obj->elements = (int*) realloc(obj->elements, obj->size);
}
...We modify our last test program a little bit by adding the pop(..) call and then checking the stack size and the top element again. For the sake of clarity we also removed the first call to size.
...
int main(int argc, char** argv)
{
stack_t* my_stack = stack_new();
stack_ctr(my_stack);
stack_push(my_stack, 1);
stack_emplace(my_stack, 2);
printf("Stack Size: %d\n", stack_size(my_stack));
printf("Top Element of the Stack is: %d\n", stack_top(my_stack));
stack_pop(my_stack);
printf("Stack Size: %d\n", stack_size(my_stack));
printf("Top Element of the Stack is: %d\n", stack_top(my_stack));
stack_dtr(my_stack);
return 0;
}
...The output shows us that the stack has indeed been shrunk and now the 1 is our top element.
Stack Size: 2
Top Element of the Stack is: 2
Stack Size: 1
Top Element of the Stack is: 1Swapping Stacks in C
There is one more feature of the stack to cover: Swapping. The swap(…) function exchanges the complete contents of one stack with those from another stack. It is a standard feature in the STL containe classes.
The swap function takes the source stack and target stack which should be swapped. The parameters are changed directly and no return value is given.
...
void stack_swap(stack_t** source, stack_t** target);
...Nothing special here, just a guard clause and then the swap algorithm with a temporary stack.
...
void stack_swap(stack_t** source, stack_t** target)
{
if(NULL == source || NULL == target) {
return;
}
stack_t* temp = *source;
*source = *target;
*target = temp;
}
...To show the functionality of swap we write a new test program that creates to stacks, swaps them and shows the sizes and top elements so we can check if the function worked as intended.
...
int main(int argc, char** argv)
{
stack_t* int_values = stack_new();
stack_ctr(int_values);
stack_t* tni_values = stack_new();
stack_ctr(tni_values);
stack_push(int_values, 1);
stack_push(int_values, 2);
stack_push(tni_values, 5);
stack_push(tni_values, 4);
stack_push(tni_values, 3);
stack_swap(&int_values, &tni_values);
printf("Int Values Size: %d\n", stack_size(int_values));
printf("Top Int Element: %d\n", stack_top(int_values));
printf("Tni Values Size : %d\n", stack_size(tni_values));
printf("Top Tni Element: %d\n", stack_top(tni_values));
stack_dtr(int_values);
stack_dtr(tni_values);
return 0;
}The output shows cleary that the contents of the stacks have changed.
Int Values Size: 3
Top Int Element: 3
Tni Values Size : 2
Top Tni Element: 2Summary & Further Ideas
Now we have completly implemented a Stack Class in C. Feel free to use it in your projects.
You may want to optimize it if you need it, you could for instance try the suggested implementaion with pre-reserved memory in order to optimize for speed. Another thing you can do is implementing a double ended queue.
If you need FIFO (First In First Out) instead of the LIFO stack, you may want to take a look at the Queue Class in C.
