I'm completely new to C and I'm trying to implement a queue data structure. I don't know much about using pointers and storing data, so I'm having difficulty starting. The queue works as a fixed size circular buffer.
I only need a single queue_t. The queue_t or struct queue contains a long * that holds the data stored in the queue. It is also important that there are no memory/data leaks in my code.
I was just wondering if I could receive some help on how exactly to start, especially with the queue_new function, but also the other functions like enqueue as well? I'm sure I will need to use functions such as malloc. Here is the code I'm starting out with:
/*
* Queue implementation.
*
*/
#include <assert.h>
#include <stdlib.h>
#include "queue.h"
/** The main data structure for the queue. */
struct queue{
unsigned int back; /* The next free position in the queue
* (i.e. the end or tail of the line) */
unsigned int front; /* Current 'head' of the queue
* (i.e. the front or head of the line) */
unsigned int size; /* How many total elements we currently have enqueued. */
unsigned int capacity; /* Maximum number of items the queue can hold */
long *data; /* The data our queue holds */
};
/**
* Construct a new empty queue.
*
* Returns a pointer to a newly created queue.
* Return NULL on error
*/
queue_t *queue_new(unsigned int capacity) {
/* needs finishing */
queue_t *q = NULL;
return q;
}
/**
* Check if the given queue is empty
*
* Returns a non-0 value if the queue is empty, 0 otherwise.
*/
int queue_empty(queue_t *q) {
assert(q != NULL);
/* needs finishing */
return 0;
}
/*
* Check if the given queue is full
*
* Returns a non-0 value if the queue is empty, 0 otherwise.
*/
int queue_full(queue_t *q) {
assert(q != NULL);
/* needs finishing */
return 0;
}
/**
* Enqueue a new item.
*
* Push a new item into our data structure.
*/
void queue_enqueue(queue_t *q, long item) {
assert(q != NULL);
assert(q->size < q->capacity);
/* needs finishing */
}
/**
* Queue size.
*
* Queries the current size of a queue (valid size must be >= 0).
*/
unsigned int queue_size(queue_t *q) {
assert(q != NULL);
/* needs finishing */
return 0;
}
/**
* Dequeue an item.
*
* Returns the item at the front of the queue and removes an item from the
* queue.
*
* Note: Removing from an empty queue is an undefined behavior (i.e., it could
* crash the program)
*/
long queue_dequeue(queue_t *q) {
assert(q != NULL);
assert(q->size > 0);
/* needs finishing */
return -1;
}
/**
* Delete queue.
*
* Remove the queue and all of its elements from memory.
*
* Note: This should be called before the proram terminates.
*/
void queue_delete(queue_t* q) {
assert(q != NULL);
/* needs finishing */
}
The code references a queue.h file which acts as an interface, which I will provide here:
#ifndef _QUEUE_H
#define _QUEUE_H
/** Our queue type (fields are hidden in the implementation file). */
typedef struct queue queue_t;
/**
* Construct a new empty queue.
*
* Returns a pointer to a newly created queue.
* Return NULL on error
*/
queue_t *queue_new(unsigned int capacity);
/**
* Check if the given queue is empty
*
* Returns a non-0 value if the queue is empty, 0 otherwise.
*/
int queue_empty(queue_t *q);
/**
* Check if the given queue is full.
*
* Returns a non-0 value if the queue is empty, 0 otherwise.
*/
int queue_full(queue_t *q);
/**
* Enqueue a new item.
*
* Push a new item into our data structure.
*/
void queue_enqueue(queue_t *q, long item);
/**
* Dequeue an item.
*
* Returns the item at the front of the queue and removes an item from the
* queue.
*
* Note: Removing from an empty queue is an undefined behavior (i.e., it could
* crash the program)
*/
long queue_dequeue(queue_t *q);
/**
* Queue size.
*
* Queries the current size of a queue (valid size must be >= 0).
*/
unsigned int queue_size(queue_t *q);
/**
* Delete queue.
*
* Remove the queue and all of its elements from memory.
*
* Note: This should be called before the program terminates.
*/
void queue_delete(queue_t *q);
#endif /* ifndef _QUEUE_H */
