Stack implementation in C programming Language

Question

I have tried to implement a Stack and associated functions in C, in order to understand the data structure better. Just wanted to know what do you think about my code overall.

Furthermore, I am using 0 as a value to set "empty section of the stack", and I know this is ambiguous - any suggestion on how to improve that aspect or anything else in the code?

/*Data Structure: Stack*/
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct stack{
 //Data_Strucure: Stack of intgers
 int *stack;
 int size_of_stack;
 int elem_in_stack;
};
struct stack creat_stack(unsigned int);
int push(struct stack *, int);
int pop(struct stack *);
int empty(struct stack *);
int peek(struct stack *);
void print_the_stack(struct stack);
int main(int argc, char *argv[]){
 int elem, ret;
 struct stack new_stack = creat_stack(5);
 for(int i = 0, elem = 5; i < new_stack.size_of_stack; i++)
 if(push(&new_stack, elem--) == 1)
 fprintf(stderr, "Unable to allocate more elements into the stack.");
 print_the_stack(new_stack);
 ret = pop(&new_stack);
 printf("[POP] -> %d\n", ret);
 elem = 10;
 if(push(&new_stack, elem) == 1)
 fprintf(stderr, "Unable to allocate '%d' into the stack. No more space avaible.\n", elem);
 print_the_stack(new_stack);
 if((ret = peek(&new_stack)) == 1)
 fprintf(stderr, "Stack is empty");
 printf("[PEEK] -> %d\n", ret);
 printf("[EMPTYING]...\n");
 empty(&new_stack);
 print_the_stack(new_stack);
}
struct stack creat_stack(unsigned int size){
 struct stack tmp;
 if((tmp.stack = malloc(sizeof(int) * size)) == NULL){
 fprintf(stderr, "Unable to allocate memory for the Stack.\n");
 exit(1);
 }
 tmp.size_of_stack = size;
 tmp.elem_in_stack = 0;
 for(int i = 0; i < tmp.size_of_stack; i++)
 tmp.stack[i] = 0;
 return tmp;
}
int push(struct stack *stack, int nw_elem){
 int pos = stack->size_of_stack - stack->elem_in_stack;
 
 if(stack->elem_in_stack == stack->size_of_stack)
 return 1;
 stack->stack[pos - 1] = nw_elem;
 stack->elem_in_stack++;
}
int pop(struct stack *stack){
 int ret;
 if(stack->elem_in_stack > 0){
 int pos = stack->size_of_stack - stack->elem_in_stack;
 ret = stack->stack[pos];
 stack->elem_in_stack--;
 stack->stack[pos] = 0;
 return ret;
 }
 fprintf(stderr, "Stack is empty\n");
 exit(1);
}
int empty(struct stack *stack){
 for(int i = 0; i < stack->size_of_stack; i++)
 stack->stack[i] = 0;
 stack->size_of_stack = 0;
 stack->elem_in_stack = 0;
}
int peek(struct stack *stack){
 int ret;
 if(stack->elem_in_stack > 0){
 int pos = stack->size_of_stack - stack->elem_in_stack;
 return stack->stack[pos];
 }
 else
 return 1;
}
void print_the_stack(struct stack stack){
 printf("[CURRENT STACK STATE] -> { ");
 for(int i = 0; i < stack.size_of_stack; i++)
 printf("%d ", stack.stack[i]);
 printf("}\n");
}

Plus, let me know if the code runs on your machine. On other implementation try, that was the major problem.

Thanks in advance for any useful help

• coderodde: If you are satisfied with my answer, you could accept it. That will give you 2 karma points.
• KmerPadreDiPdor: I am satisfied with your answer, though not fully. The function stack_contract_after_pop() is a little bit unclear. Suppose you have 4 elements into storage_array; when stack_pop() is called, the number of elements is decremented and the function is called. Following the if: 3 * 4 = 12 -> 12 <= 4 fails then, no allocation will take place, where instead 1 block of memory should have been trimmed. Suppose the other case where you have a storage of 10 and 3 elements: 8<=10 TRUE -> 10 > 8 TRUE -> then realloc set storege to 2. Maybe is me, but, could you please explain how it works please?
• coderodde: The idea is: (1) the capacity is reduced 4-fold if that is enough to store all the elements; (2) however, new capacity cannot be smaller than ’MINIMUM_STORAGE_ARRAY_CAPACITY = 4’.

Answer 1

Advice 1

time.h is not used. Remove it. Same for string.h.

Advice 2

struct stack {
 //Data_Strucure: Stack of intgers
 int* stack;
 int size_of_stack;
 int elem_in_stack;
};

Just declare (and rename the fields) as

typedef struct stack {
 int* storage_array;
 size_t size;
 size_t capacity;
} stack;

That way, you don't have to write always struct stack* st; stack* st will do nicely.

Since pop, push, etc., belong to the stack, I suggest you add the stack_ prefix to all the relevant stack operations: stack_pop, stack_push, etc. This is in order to avoid possible name clashes in projects where a programmer wants to use, say, priority queue functions that have similar names.

Advice 3

I suggest you arrange your stack as a header file with all the function declarations, and an implementation file including the header file and providing the function definitions.

Advice 4

You can easily extend your design to resize the storage array in order to allow (virtually) any number of int elements in your stack: on push, if the storage array is already filled, extend the storage array capacity by a factor \$q > 1\$. That way, the running time complexity of push will remain amortized \$\Theta(1)\$ regardless the fact that on full storage array you have to run the operation in \$\Theta(N)\$.

Alternative implementation

All in all, I had this in mind:

cstack.h

#ifndef COM_YOURCOMPANY_UTIL_STACK_H
#define COM_YOURCOMPANY_UTIL_STACK_H
typedef struct stack {
 int* storage_array;
 size_t size;
 size_t capacity;
} stack;
stack* stack_creat();
void stack_push(stack*, int);
int stack_pop(stack*);
int stack_empty(stack*);
int stack_peek(stack*);
void stack_print(stack*);
#endif

cstack.c

#include "cstack.h"
#include <stdlib.h>
static const MINIMUM_STORAGE_ARRAY_CAPACITY = 4;
stack* stack_creat() {
 stack* s = (stack*)malloc(sizeof(*s));
 if ((s->storage_array =
 calloc(MINIMUM_STORAGE_ARRAY_CAPACITY,
 sizeof(int))) == NULL) {
 perror("Unable to allocate memory for the Stack.\n");
 exit(EXIT_FAILURE);
 }
 s->size = 0;
 s->capacity = MINIMUM_STORAGE_ARRAY_CAPACITY;
 return s;
}
static void stack_ensure_capacity_before_push(stack* s) {
 if (s->size == s->capacity) {
 s->storage_array =
 realloc(s->storage_array,
 sizeof(int) * (s->capacity *= 2));
 }
}
static void stack_contract_after_pop(stack* s) {
 if (s->size * 4 <= s->capacity
 && s->capacity > 2 * MINIMUM_STORAGE_ARRAY_CAPACITY) {
 s->storage_array = realloc(s->storage_array, s->capacity /= 4);
 }
}
void stack_push(stack* s, int element) {
 stack_ensure_capacity_before_push(s);
 s->storage_array[s->size++] = element;
}
int stack_pop(stack* s) {
 int ret;
 if (s->size == 0) {
 perror("Popping from empty stack.");
 exit(EXIT_FAILURE);
 }
 ret = s->storage_array[--s->size];
 stack_contract_after_pop(s);
 return ret;
}
int stack_empty(stack* s) {
 s->size = 0;
 stack_contract_after_pop(s);
}
int stack_peek(stack* s) {
 if (s->size == 0) {
 perror("Peeking from empty stack.");
 exit(EXIT_FAILURE);
 }
 return s->storage_array[s->size - 1];
}
void stack_print(stack* s) {
 printf("[CURRENT STACK STATE] -> { ");
 for (int i = 0; i < s->size; i++)
 printf("%d ", s->storage_array[i]);
 printf("}\n");
}

main.c

#include "cstack.h"
#include <stdio.h>
#include <stdlib.h>
int main(int argc, char* argv[]) {
 int elem, ret;
 stack* s = stack_creat();
 for (int i = 0, elem = 5; i < 5; i++)
 stack_push(s, elem--);
 stack_print(s);
 ret = stack_pop(s);
 printf("[POP] -> %d\n", ret);
 elem = 10;
 stack_push(s, elem);
 stack_print(s);
 printf("[PEEK] -> %d\n", stack_peek(s));
 printf("[EMPTYING]...\n");
 stack_empty(s);
 stack_print(s);
}

Hope that helps.

• KmerPadreDiPdor: It helped a lot! Thanks! The Advace 4 is a little bit cryptic to my mind but I think that I will find a way to deal with it. Thanks again, was very helpful.
• coderodde: @KmerPadreDiPdor In order to parse the Advice 4, google up "running time analysis". Don’t worry, it"s not rocket science.

Answer 2

Instead of manually zeroing the stack's cells in creat_stack, you can allocate them using calloc instead of malloc to have them cleared from the start

On that note, I'm not convinced you need to keep the unused cells set to 0. If they aren't in use, their content doesn't matter, right? Initializing them at the start might be useful, but resetting them back to 0 when you pop a value doesn't seem like it actually helps with anything in particular

I don't think having creat_stack and pop terminate the program when they fail is the right thing to do. Telling the caller that they failed (by returning an invalid stack for creat_stack or by returning a failure value for pop) - the caller might be able to do something else instead, or if not, they might at least have some cleaning up which they expect to do without having the program just suddenly stop

push seems to be missing a return statement for the case where the stack isn't full. Different compilers compiling different programs for different systems may make all kinds of assumptions about what that might mean, and at least some of them will assume things that you don't want them to. You'll want to fix that

peek is ambiguous - it doesn't distinguish an empty stack from a stack where the topmost value is 1 - that's probably not ideal
One relatively common approach to getting around that (though not the only one, nor necessarily the best one) could be the use of an output parameter - passing an additional int * parameter, and having the function write the result to that pointer, using the return value only to indicating whether the call succeeded or not