Implementing stacks in C, using arrays

Question

I am trying to implement a Stack in C using arrays just for the sake of learning.

I am making some decisions in how this is implemented (suggestions are welcome), basically I proposed a struct for the stack containing the array and an index 't' of the top element. Then I have a function to create the stack which allocates the memory depending on the size defined by the user, this is how it looks so far:

UPDATE: I have used some of your suggestions and this is how version 2.0 looks like until now. I also created an online document with version 1.0 for anybody interested (here)

stack.h

// Interface for a stack data structure using arrays

typedef struct Stack{
    int t;          // Index of the top element in st
    int maxSize;    // Max size, allows to be resized when full
    int* st;        // Changed from int[] to int*
}Stack;

void initStack(Stack* s, int length);   // Declare the initial length
void push(Stack* s, int elem);
int pop(Stack* s);
int top(Stack* s);
int size_s(Stack* s);
int isEmpty(Stack* s);
void print(Stack* s);                   // Visualize the stack

stack.c

#include <stdio.h>
#include "stack.h"
#include <malloc.h>


void initStack(Stack* s, int length){
    s->st = malloc(sizeof(int)*length);
    s->maxSize = length;    // Initial size (this could also have a default number since it would be able to grow)
    s->t = -1;              // Initialize the size (index) to -1 to indicate an empty stack
}

void push(Stack* s, int elem){
    int* tmp;
    int i;
    if(size_s(s) == s->maxSize){  // Resize to double the size if full...
        // WOULD IT BE POSSIBLE TO REPLACE ALL OF THIS USING REALLOC() ?
        s->maxSize = s->maxSize * 2;
        tmp = malloc(sizeof(int)*s->maxSize);
        for(i = 0; i < size_s(s); i++){
            tmp[i] = s->st[i];
        }
        free(s->st);
        s->st = tmp;
    }

    int t = s->t + 1;
    s->t = t;
    s->st[t] = elem;
}

int top(Stack* s){
    if(isEmpty(s)) return -1;   // Empty stack
    return s->st[s->t];
}

int pop(Stack* s){
    int element;
    if(isEmpty(s)) return -1;    // Empty stack
    element = s->st[s->t];

    //////////////////////////////////////
    s->st[s->t] = 0;            // Empty the previous location, what other value could I use?
                                // Would it make sense to use free() ? I would need to malloc() again right?
    //////////////////////////////////////

    s->t = s->t - 1;
    return element;
}

int size_s(Stack* s){
    return (s->t) + 1;
}

int isEmpty(Stack* s){
    if(s->t == -1){
        return 1;   // True
    }else{
        return 0;   // False
    }
}

void print(Stack* s){
    int len = size_s(s);
    printf("Length: %d\n",len);
    int i;
    for(i = 0; i < len; i++){
        printf("%d ",s->st[i]);
    }
}

I haven't tested all the functions yet but that is a basic structure on how I would implement them.

OBS: The push operation is still not safe because I'm not checking whether or not the stack is full.

The test code I am running is

main.c

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

int main()
{
    Stack* s = malloc(sizeof(Stack));
    int i = 0;
    initStack(s,10);    // Declare an initial size

    for(i = 0; i < 12; i++){
        push(s,i);
        printf("Size of stack: %d, MaxSize: %d\n",size_s(s),s->maxSize);
    }
    printf("Top element: %d\n",top(s));
    print(s);
    puts("");
    popped = pop(s);
    printf("Popped: %d\n",popped);
    print(s);
    puts("");
    return 0;
}

OUTPUT

Size of stack: 1, MaxSize: 10
Size of stack: 2, MaxSize: 10
Size of stack: 3, MaxSize: 10
Size of stack: 4, MaxSize: 10
Size of stack: 5, MaxSize: 10
Size of stack: 6, MaxSize: 10
Size of stack: 7, MaxSize: 10
Size of stack: 8, MaxSize: 10
Size of stack: 9, MaxSize: 10
Size of stack: 10, MaxSize: 10
Size of stack: 11, MaxSize: 20
Size of stack: 12, MaxSize: 20
Top element: 11
Length: 12
0 1 2 3 4 5 6 7 8 9 10 11
Popped: 11
Length: 11
0 1 2 3 4 5 6 7 8 9 10

There is a bug in the program, I am only testing 3 functions:

• newStack
• push
• print

The program has no compilation or explicit runtime error, it will only crash and I can't figure out why. I am not entirely sure about the newStack() method because I am allocating memory in an odd way that I found about (here) so that the typedef of the Stack struct has an array of an unknown size.

In some other tests I did sometimes I get some garbage values in some of the cells of the array.

Thanks, I'll keep posting all the fixes and updates to this implementation.

I would also love to hear your suggestions on the implementation i.e. header file etc.

Answer 1

Stack* s = (Stack*)malloc(sizeof(Stack)+length); 

Should be:

Stack* s = malloc(sizeof(Stack)+length*sizeof(int)); 

Also, you should save length in the struct to use for overflow checking.

Answer 2

Don't forget to free your memory. Also, you probably should consider keeping the size, rather than the index of the top, and instead use a function to get the top. Then your size is 0 if there are no elements. Finally your data member should be an int * rather than a int[] because a pointer better implies a realizable array.

The function newStack could be better by instead calling it initStack and passing it a Stack *, just like the rest of the functions.

void initStack(Stack* s, int length){
    s.size = 0;
     s.maxSize = length;
    s.data = malloc(sizeof(int)*length);
    return s;
}