Skip to content

Instantly share code, notes, and snippets.

@parkj90
Created August 26, 2018 20:31
Show Gist options
  • Save parkj90/4fb6f1cf96e2865c8f082354feb878de to your computer and use it in GitHub Desktop.
Save parkj90/4fb6f1cf96e2865c8f082354feb878de to your computer and use it in GitHub Desktop.
queue with dynamic array
//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");
}
//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
*/
//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);
}
//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;
}
//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