Last active
April 26, 2018 10:01
-
-
Save JohanneA/2d653e1d2ae45595534bf6d406dfbe6e to your computer and use it in GitHub Desktop.
A dynamic stack data structure made in C
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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