Skip to content

Instantly share code, notes, and snippets.

@lukem512
Created January 24, 2020 14:35
Show Gist options
  • Save lukem512/278012aaa6e7f45828f511f7b79d6363 to your computer and use it in GitHub Desktop.
Save lukem512/278012aaa6e7f45828f511f7b79d6363 to your computer and use it in GitHub Desktop.
Queue (Circular Buffer) ADS
// Luke Mitchell & Max Peglar-Willis, 2020
// <hi@lukemitchell.co>
#include <stdlib.h>
#include <stdbool.h>
#include "queue.h"
// Initialise a new queue of the
// specified size
queue_t* init_queue(size_t size) {
queue_t* q = malloc(sizeof(queue_t));
if (q == NULL) {
return NULL;
}
q->head = 0;
q->tail = 0;
q->size = size;
q->buf = malloc(size * sizeof(size_t));
if (q->buf == NULL) {
return NULL;
}
return q;
}
// Add a new value to the queue
// Returns TRUE on success, FALSE
// when the queue is full.
int enqueue(queue_t* q, size_t val) {
// If the pointers meet, the queue is full.
if (q->head == q->tail - 1) {
return false;
}
// If the head pointer is at the end of the buffer
// and the tail pointer at the beginning,
// the queue is also full.
if (q->head == q->size) {
if (q->tail == 0) {
return false;
}
}
q->buf[q->head] = val;
// If the head pointer is at the end of the
// buffer, loop around to the start.
if (q->head == q->size) {
q->head = 0;
} else {
q->head += 1;
}
return true;
}
// Remove the oldest value in the queue
// and return it.
size_t dequeue(queue_t* q) {
size_t oldTail = q->tail;
// If the tail pointer is at
// the end of the buffer,
// loop around to the start.
if (q->tail == q->size) {
q->tail = 0;
} else {
q->tail += 1;
}
return q->buf[oldTail];
}
// Return the oldest value in the queue.
// This is the next value that will be
// removed when dequeue is called.
size_t peek(queue_t* q) {
return q->buf[q->tail];
}
// Luke Mitchell & Max Peglar-Willis, 2020
// <hi@lukemitchell.co>
#ifndef QUEUE_H
#define QUEUE_H
// Define a queue data structure.
// This is a First In First Out (FIFO)
// structure.
typedef struct {
size_t* buf;
size_t head;
size_t tail;
size_t size;
} queue_t;
// Initialise a new queue of the
// specified size
extern queue_t* init_queue(size_t size);
// Add a new value to the queue
// Returns TRUE on success, FALSE
// when the queue is full.
extern int enqueue(queue_t* q, size_t val);
// Remove the oldest value in the queue
// and return it.
extern size_t dequeue(queue_t* q);
// Return the oldest value in the queue.
// This is the next value that will be
// removed when dequeue is called.
extern size_t peek(queue_t* q);
#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment