Created
August 26, 2018 20:31
-
-
Save parkj90/4fb6f1cf96e2865c8f082354feb878de to your computer and use it in GitHub Desktop.
queue with dynamic array
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
//array.c | |
#include <stdio.h> | |
#include <stdlib.h> | |
#include <string.h> | |
#include "array.h" | |
array_t *array_new(void) { | |
array_t *array = malloc(sizeof(array_t)); | |
if (array == NULL) { | |
return NULL; | |
} | |
array->size = 0; | |
array->data = NULL; | |
return array; | |
} | |
int array_get(array_t *array, unsigned int index, int *value) { | |
if (index >= array->size) { | |
return -1; | |
} | |
*value = array->data[index]; | |
return 0; | |
} | |
int array_set(array_t *array, unsigned int index, int value) { | |
if (index >= array->size) { | |
return -1; | |
} | |
array->data[index] = value; | |
return 0; | |
} | |
int array_delete(array_t *array, unsigned int index) { | |
if (index >= array->size) { | |
return -1; | |
} | |
int last = array->data[array->size - 1]; | |
int *temp = realloc(array->data, (array->size - 1) * sizeof(int)); | |
if (array->size != 1 && temp == NULL) { | |
return -2; | |
} | |
array->data = temp; | |
array->size--; | |
if ((array->size - index ) > 1) { | |
memmove(array->data + index, array->data + index + 1, (array->size - index - 1) * sizeof(int)); | |
} | |
if (index < array->size) { | |
array->data[array->size - 1] = last; | |
} | |
return 0; | |
} | |
int array_append(array_t *array, int value) { | |
int *temp = realloc(array->data, (array->size + 1) * sizeof(int)); | |
if (temp == NULL) { | |
return -2; | |
} | |
array->data = temp; | |
array->data[array->size] = value; | |
array->size++; | |
return 0; | |
} | |
unsigned int array_length(array_t *array) { | |
return array->size; | |
} | |
void array_free(array_t *array) { | |
free(array->data); | |
free(array); | |
} | |
//dump to stdout for debugging | |
void array_dump(array_t *array) { | |
for (int i = 0; i < array->size; i++) { | |
printf("%d ", array->data[i]); | |
} | |
printf("\n"); | |
} |
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
//array.h | |
#include <stdbool.h> | |
typedef struct { | |
unsigned int size; | |
int *data; | |
} array_t; | |
array_t *array_new(void); | |
int array_get(array_t *array, unsigned int index, int *value); | |
int array_set(array_t *array, unsigned int index, int value); | |
int array_delete(array_t *array, unsigned int index); | |
int array_append(array_t *array, int value); | |
unsigned int array_length(array_t *array); | |
void array_free(array_t *array); | |
//dump to stdout for debugging | |
void array_dump(array_t *array); | |
/* methods returning int should return: | |
0 on success | |
-1 on out of bounds | |
-2 on out of memory | |
*/ | |
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
//main.c | |
#include <stdio.h> | |
#include <assert.h> | |
#include "queue.h" | |
int main(void) { | |
int value; | |
queue_t *my_queue = queue_new(); | |
if (my_queue == NULL) { | |
printf("failed to allocate queue"); | |
} | |
//test push | |
assert(queue_push(my_queue, 3) == 0); | |
assert(queue_push(my_queue, 5) == 0); | |
assert(queue_push(my_queue, 8) == 0); | |
assert(queue_push(my_queue, 10) == 0); | |
//test size | |
assert(queue_size(my_queue) == 4); | |
//test empty | |
assert(queue_empty(my_queue)); | |
//test pop | |
assert(queue_pop(my_queue, &value) == 0); | |
assert(value == 3); | |
assert(queue_size(my_queue) == 3); | |
assert(queue_empty(my_queue)); | |
assert(queue_pop(my_queue, &value) == 0); | |
assert(value == 5); | |
assert(queue_size(my_queue) == 2); | |
assert(queue_pop(my_queue, &value) == 0); | |
assert(value == 8); | |
assert(queue_size(my_queue) == 1); | |
assert(queue_pop(my_queue, &value) == 0); | |
assert(value == 10); | |
assert(queue_size(my_queue) == 0); | |
assert(!queue_empty(my_queue)); | |
queue_free(my_queue); | |
} |
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
//queue.c | |
#include <stdlib.h> | |
#include "queue.h" | |
queue_t *queue_new(void) { | |
queue_t *queue = malloc(sizeof(queue_t)); | |
if (queue == NULL) { | |
return NULL; | |
} | |
queue->array = array_new(); | |
if (queue->array == NULL) { | |
free(queue); | |
return NULL; | |
} | |
return queue; | |
} | |
int queue_push(queue_t *queue, int value) { | |
if (queue == NULL) { | |
return -1; | |
} | |
array_append(queue->array, value); | |
return 0; | |
} | |
int queue_pop(queue_t *queue, int *value) { | |
if (queue == NULL || value == NULL) { | |
return -1; | |
} | |
if (array_get(queue->array, 0, value)) { | |
return -1; | |
} | |
if (array_delete(queue->array, 0)) { | |
return -1; | |
} | |
return 0; | |
} | |
unsigned int queue_size(queue_t *queue) { | |
if (queue == NULL) { | |
return -1; | |
} | |
return array_length(queue->array); | |
} | |
bool queue_empty(queue_t *queue) { | |
if (array_length(queue->array)) { | |
return true; | |
} | |
return false; | |
} | |
void queue_free(queue_t *queue) { | |
if (queue == NULL) { | |
return; | |
} | |
array_free(queue->array); | |
free(queue); | |
return; | |
} |
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
//queue.h | |
#include <stdbool.h> | |
#include "array.h" | |
typedef struct { | |
array_t *array; | |
} queue_t; | |
queue_t *queue_new(void); | |
int queue_push(queue_t *queue, int value); | |
int queue_pop(queue_t *queue, int *value); | |
unsigned int queue_size(queue_t *queue); | |
bool queue_empty(queue_t *queue); | |
void queue_free(queue_t *queue); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment