Queue Implementation for Strings

A short implementation of a queue for strings 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 stringQueueCreate function will pre-allocate all the queue elements which will make ulterior operations faster since they will not suffer from the slowdowns of realloc.

Code

/*************************************************************************/
/*    Copyright (C) 2015 Wizardry and Steamworks - License: GNU GPLv3    */
/*************************************************************************/
/*                                                                       */
/*  stringQueue                                                          */
/*                                                                       */
/*  An implementation of a queue of strings.                             */
/*  Implemented functions:                                               */
/*      - create                                                         */
/*      - clear                                                          */
/*      - is empty                                                       */
/*      - size                                                           */
/*      - count                                                          */
/*      - enqueue                                                        */
/*      - dequeue                                                        */
/*      - print                                                          */
/*                                                                       */
/*************************************************************************/
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
/* The stringQueue 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;
    char **store;
    int front, rear;
} stringQueue;
 
// Zero or one arguments for stringQueueCreate_Internal.
#define stringQueueCreate_0() stringQueueCreate_Internal(1)
#define stringQueueCreate_1(x) stringQueueCreate_Internal(x)
#define _FUNC_OVERRIDE(_1, FUNC) FUNC
#define stringQueueCreate(...) _FUNC_OVERRIDE(stringQueueCreate_1(__VA_ARGS__), stringQueueCreate_0())
#define stringQueueIsEmpty(q) (q->rear == q->front)
#define stringQueueSize(q) q->size
#define stringQueueCount(q) q->rear - q->front
 
/*
 * Creates a new stringQueue with a given size.
 */
stringQueue* stringQueueCreate_Internal(int size) {
    stringQueue *q = (stringQueue*)calloc(1, sizeof(stringQueue));
    if ((q->store = (char**)calloc(size, sizeof(char **))) == NULL)
        return NULL;
    q->size = size;
    q->front = 0;
    q->rear = 0;
    return q;
}
 
/*
 * Clears a stringQueue and returns a pointer to a new empty queue.
 */
stringQueue* stringQueueClear(stringQueue *q) {
    if (q != NULL)
        free(q);
    return stringQueueCreate(1);
}
 
/*
 * Enqueues an element to the stringQueue.
 */
void stringQueueEnqueue(stringQueue *q, char *e) {
    if (q->rear > q->size - 1)
        q->store = (char**)realloc(q->store, ++q->size * sizeof(char *));
    q->store[q->rear] = (char*)calloc(strlen(e) + 1, sizeof(char *));
    strncpy(q->store[q->rear], e, strlen(e));
    ++q->rear;
}
 
/*
 * Dequeues an element from the stringQueue or returns NULL in case the
 * queue is empty.
 */
char *stringQueueDequeue(stringQueue *q) {
    char *e;
    if (stringQueueIsEmpty(q))
        return NULL;
    e = (char *)calloc(strlen(q->store[q->front]), sizeof(char *));
    strncpy(e, q->store[q->front], strlen(q->store[q->front]));
    ++q->front;
    return e;
}
 
/*
 * Prints out the elements of the stringQueue.
 */
void stringQueuePrint(stringQueue *q) {
    int i;
    if (stringQueueIsEmpty(q)) {
        printf("Queue is empty.\n");
        return;
    }
    printf("Elements in the queue: ");
    i = q->front;
    do {
        printf("%s ", q->store[i]);
    } while (++i < q->rear);
    printf("\n");
}
 
int main(void) {
    stringQueue *q = stringQueueCreate();
    printf("queue size: %d\n", stringQueueSize(q));
    stringQueueEnqueue(q, "Good");
    stringQueueEnqueue(q, "Day");
    stringQueueEnqueue(q, "!");
    stringQueuePrint(q);
    printf("queue size: %d\n", stringQueueSize(q));
    printf("number of elements in the queue: %d\n", stringQueueCount(q));
    printf("Dequeue: %s\n", stringQueueDequeue(q));
    printf("Dequeue: %s\n", stringQueueDequeue(q));
    stringQueuePrint(q);
    printf("Dequeue: %s\n", stringQueueDequeue(q));
    stringQueuePrint(q);
}

fuss/c/data_structures/queues/strings.txt ยท Last modified: 2017/04/27 08:35 by office

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.