Skip to content

Instantly share code, notes, and snippets.

@JohanneA
Last active April 26, 2018 10:01
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save JohanneA/2d653e1d2ae45595534bf6d406dfbe6e to your computer and use it in GitHub Desktop.
Save JohanneA/2d653e1d2ae45595534bf6d406dfbe6e to your computer and use it in GitHub Desktop.
A dynamic stack data structure made in C
#include <stdlib.h>
#include <stdio.h>
#define DEFAULT_SIZE 16
int no_of_words = 0; //Number of elements in array
int array_size = DEFAULT_SIZE;
int *stack; //Stack pointer
void init_stack() {
stack = malloc(sizeof(uint32_t) * DEFAULT_SIZE);
}
void destroy_stack() {
free(stack)
}
//Allocate a new chunk of memory with half the size.
//Copy the old stack to the new memory and free up
//the old stack.
void shrink_capacity() {
array_size /= 2;
int *new_stack = malloc(sizeof(uint32_t) * array_size);
int i;
for (i = 0; i < no_of_words; i++) {
new_stack[i] = stack[i];
}
free(stack);
stack = new_stack;
}
void double_capacity() {
array_size *= 2;
stack = realloc(stack, sizeof(uint32_t) * array_size);
}
/*************************************************************
* Stack operations
*************************************************************/
//Check if the number of elements is less than half the array size
//and shrink the capacity if true.
//Remove and return the element on top of the stack.
int pop() {
if (no_of_words < array_size / 2 && no_of_words > DEFAULT_SIZE) {
shrink_capacity();
}
int removed_word = stack[no_of_words - 1];
no_of_words -= 1;
return removed_word;
}
//Check if malloc and realloc returned a pointer.
//The capacity is doubled if the number of elements
//equals the array size.
//Add an element to the stack.
void push(int word){
if(stack == NULL) {
printf("Something went wrong, failed to allocate memory\n");
exit(1);
}
if(no_of_words == array_size) {
double_capacity();
}
stack[no_of_words] = word;
no_of_words += 1;
}
//Returns the top element
int top() {
return (int) stack[no_of_words - 1];
}
int size() {
return no_of_words;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment