Queue Implementation for Unsigned Integers

A short implementation of a queue for unsigned integers with several benefits:

  • the queue expands automatically as elements are enqueued and shrinks as elements are dequeued.
  • in case the total size of the queue is known before usage, then the uintQueueCreate function will pre-allocate all the queue elements which will make ulterior operations faster since they will not suffer from the slowdowns of realloc.
/*************************************************************************/
/*    Copyright (C) 2015 Wizardry and Steamworks - License: GNU GPLv3    */
/*************************************************************************/
/*                                                                       */
/*  uintQueue                                                            */
/*                                                                       */
/*  An implementation of a queue of unsigned integers.                   */
/*  Implemented functions:                                               */
/*      - create                                                         */
/*      - clear                                                          */
/*      - is empty                                                       */
/*      - count                                                          */
/*      - size                                                           */
/*      - enqueue                                                        */
/*      - dequeue                                                        */
/*      - print                                                          */
/*                                                                       */
/*************************************************************************/
 
#include <stdio.h>
#include <stdlib.h>
 
/* The unitQueue structure with front being the index of the front-mode
 * element and rear being the index of the last element in the queue
 */
typedef struct {
    int size;
    unsigned int *store;
    int front, rear;
} uintQueue;
 
/*
 * Creates a new uintQueue with a given length.
 */
uintQueue* uintQueueCreate(int size) {
    uintQueue *q = (uintQueue *)calloc(1, sizeof(uintQueue));
    if((q->store = (unsigned int*)calloc(size, sizeof(unsigned int *))) == NULL)
        return NULL;
    q->size = size;
    q->front = 0;
    q->rear = 0;
    return q;
}
 
/*
 * Clears an uintQueue and returns a pointer to a new empty queue.
 */
uintQueue* uintQueueClear(uintQueue *q) {
    if (q != NULL)
        free(q);
    return uintQueueCreate(1);
}
 
/*
 * Takes as parameter an uintQueue and returns 1 if the queue is empty
 * or 0 if the queue is not empty.
 */
int uintQueueIsEmpty(uintQueue *q) {
    return q->rear == q->front;
}
 
/*
 * Returns allocated queue size (not the number of elements).
 */
int uintQueueSize(uintQueue *q) {
    return q->size;
}
 
/*
 * Returns the number of elements in uintQueue.
 */
int uintQueueCount(uintQueue *q) {
    return q->rear - q->front;
}
 
/*
 * Enqueues an element to the uintQueue.
 */
void uintQueueEnqueue(uintQueue *q, int e) {
    if (q->rear > q->size - 1) 
        q->store = (unsigned int *)realloc(q->store, ++q->size * sizeof(unsigned int *));
    q->store[q->rear] = e;
    ++q->rear;
}
 
/*
 * Dequeues an element from the uintQueue or returns -1 in case the queue
 * is empty.
 */
int uintQueueDequeue(uintQueue *q) {
    int e;
    if (uintQueueIsEmpty(q))
        return -1;
    e = q->store[q->front++];
    return e;
}
 
/*
 * Prints out the elements of the uintQueue.
 */
void uintQueuePrint(uintQueue *q) {
    int i;
    if (uintQueueIsEmpty(q)) {
        printf("Queue is empty.\n");
        return;
    }
    printf("Elements in the queue: ");
    i = q->front;
    do {
        printf("%d ", q->store[i]);
    } while (++i < q->rear);
    printf("\n");
}
 
int main(void) {
    uintQueue *q = uintQueueCreate(3);
    printf("queue length: %d\n", uintQueueCount(q));
    uintQueueEnqueue(q, 1);
    uintQueueEnqueue(q, 8);
    uintQueuePrint(q);
    printf("queue length: %d\n", uintQueueCount(q));
    printf("Dequeue: %d\n", uintQueueDequeue(q));
    printf("Dequeue: %d\n", uintQueueDequeue(q));
    uintQueuePrint(q);
}

fuss/c/data_structures/queues/unsigned_integers.txt ยท Last modified: 2017/02/22 18:30 (external edit)

Access website using Tor Access website using i2p


For the copyright, license, warranty and privacy terms for the usage of this website please see the license, privacy and plagiarism pages.