Circular Linked List Queue Implementation with Tail Pointer Only

A circular linked list with a head node and single tail pointer (no head pointer) can represent a queue. The head node's next pointer points to itself when empty.

#include <stdio.h>
#include <stdlib.h>

#define SUCCESS 0
#define FAILURE -1

typedef int ElementType;

typedef struct Node {
    ElementType value;
    struct Node* link;
} Node, *QueuePtr;

QueuePtr initializeQueue() {
    QueuePtr tail = (QueuePtr)malloc(sizeof(Node));
    if (!tail) exit(FAILURE);
    tail->link = tail;
    return tail;
}

int enqueueElement(QueuePtr tail, ElementType item) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) return FAILURE;
    
    newNode->value = item;
    newNode->link = tail->link;
    tail->link = newNode;
    tail = newNode;
    return SUCCESS;
}

int dequeueElement(QueuePtr tail, ElementType* output) {
    if (tail->link == tail) return FAILURE;
    
    Node* firstNode = tail->link->link;
    *output = firstNode->value;
    
    if (firstNode == tail) {
        tail->link = tail;
    } else {
        tail->link->link = firstNode->link;
    }
    
    free(firstNode);
    return SUCCESS;
}

int main() {
    QueuePtr tail = initializeQueue();
    ElementType result;
    
    enqueueElement(tail, 10);
    enqueueElement(tail, 20);
    enqueueElement(tail, 30);
    
    dequeueElement(tail, &result);
    printf("%d\n", result);
    dequeueElement(tail, &result);
    printf("%d\n", result);
    dequeueElement(tail, &result);
    printf("%d\n", result);
    
    free(tail);
    return 0;
}

Aray-Based Circualr Queue with Tag Flag

A circular queue implementation using an array with a tag indicator to distignuish between empty and full states when front equals rear.

#include <stdio.h>
#include <stdlib.h>

#define MAX_CAPACITY 100

typedef int QueueElement;

typedef struct {
    QueueElement elements[MAX_CAPACITY];
    int head;
    int tail;
    int statusFlag;
} CircularQueue;

void setupQueue(CircularQueue* q) {
    q->head = 0;
    q->tail = 0;
    q->statusFlag = 0;
}

int insertElement(CircularQueue* q, QueueElement item) {
    if (q->head == q->tail && q->statusFlag == 1) {
        printf("Queue capacity exceeded\n");
        return -1;
    }
    
    q->elements[q->tail] = item;
    q->tail = (q->tail + 1) % MAX_CAPACITY;
    q->statusFlag = 1;
    return 0;
}

int removeElement(CircularQueue* q, QueueElement* output) {
    if (q->head == q->tail && q->statusFlag == 0) {
        printf("Queue is empty\n");
        return -1;
    }
    
    *output = q->elements[q->head];
    q->head = (q->head + 1) % MAX_CAPACITY;
    q->statusFlag = 0;
    return 0;
}

int main() {
    CircularQueue q;
    setupQueue(&q);
    QueueElement result;
    
    insertElement(&q, 10);
    insertElement(&q, 20);
    insertElement(&q, 30);
    
    removeElement(&q, &result);
    printf("%d\n", result);
    removeElement(&q, &result);
    printf("%d\n", result);
    removeElement(&q, &result);
    printf("%d\n", result);
    
    return 0;
}