C Programming data structures Queue and Circular Queue Step by step Implementation and Top 10 Questions and Answers
 .NET School AI Teacher - SELECT ANY TEXT TO EXPLANATION.    Last Update: April 01, 2025      18 mins read      Difficulty-Level: beginner

C Programming: Data Structures - Queue and Circular Queue

Queue is a fundamental data structure that follows the First-In-First-Out (FIFO) principle. This means that the element added first to the queue will be the first to be removed. Think of a line of people waiting for service at a ticket counter. Here, the first person in the line is the first one to get served and leave the queue.

Queue Structure

A queue can be implemented using either an array or a linked list. Let's explore both implementations:

1. Queue Using Arrays:

A queue can be implemented using a one-dimensional array. Two main pointers are used to manage the queue:

  • Front: Points to the front (beginning) of the queue, where the next element to be dequeued is located.
  • Rear: Points to the end (last) of the queue, where the next element will be enqueued.

Operations:

  • Enqueue: Adds an element to the rear of the queue.
  • Dequeue: Removes an element from the front of the queue.
  • Peek/Front: Returns the value at the front of the queue without removing it.
  • IsEmpty: Checks if the queue is empty.
  • IsFull: Checks if the queue is full.

Implementation:

#include <stdio.h>
#include <stdlib.h>
#define MAX 5

typedef struct {
    int items[MAX];
    int front;
    int rear;
} Queue;

void initQueue(Queue* q) {
    q->front = -1;
    q->rear = -1;
}

int isFull(Queue* q) {
    return q->rear == MAX - 1;
}

int isEmpty(Queue* q) {
    return q->front == -1;
}

void enqueue(Queue* q, int value) {
    if (isFull(q)) {
        printf("Queue is full.\n");
        return;
    }
    if (isEmpty(q)) {
        q->front = 0;
    }
    q->items[++q->rear] = value;
}

int dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty.\n");
        return -1;
    }
    int item = q->items[q->front];
    if (q->front == q->rear) {
        q->front = q->rear = -1;
    } else {
        q->front++;
    }
    return item;
}

int peek(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty.\n");
        return -1;
    }
    return q->items[q->front];
}

int main() {
    Queue q;
    initQueue(&q);
    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    printf("Dequeued element: %d\n", dequeue(&q));
    printf("Front element: %d\n", peek(&q));
    return 0;
}

2. Queue Using Linked Lists:

In the array implementation of queue, insertion and deletion operations require the front pointer to be updated, and the queue can become full even if there are vacant slots in the array due to the linear traversal from the front. To overcome this, a linked list implementation can be used, where the queue forms a simple singly linked list.

Operations:

  • Enqueue: Adds a node to the rear end of the queue.
  • Dequeue: Removes a node from the front end of the queue.
  • Peek/Front: Returns the value at the front of the queue without removing it.
  • IsEmpty: Checks if the queue is empty.

Implementation:

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

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct {
    Node* front;
    Node* rear;
} Queue;

Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

void initQueue(Queue* q) {
    q->front = q->rear = NULL;
}

int isEmpty(Queue* q) {
    return q->front == NULL;
}

void enqueue(Queue* q, int value) {
    Node* newNode = createNode(value);
    if (isEmpty(q)) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

int dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty.\n");
        return -1;
    }
    Node* temp = q->front;
    int item = temp->data;
    q->front = q->front->next;
    if (q->front == NULL) {
        q->rear = NULL;
    }
    free(temp);
    return item;
}

int peek(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty.\n");
        return -1;
    }
    return q->front->data;
}

int main() {
    Queue q;
    initQueue(&q);
    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    printf("Dequeued element: %d\n", dequeue(&q));
    printf("Front element: %d\n", peek(&q));
    return 0;
}

Circular Queue

A Circular Queue is a variation of the queue where the last element of the queue is connected to the first element, forming a circle. This data structure overcomes the limitation of wasted space caused by linear arrangement in standard queue implementation (using array).

Structure:

  • Like a linear queue, a circular queue also uses two pointers: front and rear.
  • The front pointer points to the first element of the queue (the element that was enqueued first and is to be dequeued first), and the rear pointer points to the last element of the queue.

Operations:

  • Enqueue: Adds an element to the rear of the queue.
  • Dequeue: Removes an element from the front of the queue.
  • Peek/Front: Returns the value at the front of the queue without removing it.
  • IsEmpty: Checks if the queue is empty.
  • IsFull: Checks if the queue is full.

Implementation:

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

#define MAX 5

typedef struct {
    int items[MAX];
    int front;
    int rear;
} CircularQueue;

void initQueue(CircularQueue* q) {
    q->front = -1;
    q->rear = -1;
}

int isFull(CircularQueue* q) {
    return (q->front == 0 && q->rear == MAX - 1) || (q->rear == (q->front - 1) % (MAX - 1));
}

int isEmpty(CircularQueue* q) {
    return q->front == -1;
}

void enqueue(CircularQueue* q, int value) {
    if (isFull(q)) {
        printf("Queue is full.\n");
        return;
    }
    if (q->front == -1) {
        q->front = 0;
    }
    q->rear = (q->rear + 1) % MAX;
    q->items[q->rear] = value;
}

int dequeue(CircularQueue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty.\n");
        return -1;
    }
    int item = q->items[q->front];
    if (q->front == q->rear) {
        q->front = q->rear = -1;
    } else {
        q->front = (q->front + 1) % MAX;
    }
    return item;
}

int peek(CircularQueue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty.\n");
        return -1;
    }
    return q->items[q->front];
}

int main() {
    CircularQueue q;
    initQueue(&q);
    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);
    printf("Dequeued element: %d\n", dequeue(&q));
    printf("Front element: %d\n", peek(&q));
    enqueue(&q, 40);
    enqueue(&q, 50);
    printf("Dequeued element: %d\n", dequeue(&q));
    printf("Dequeued element: %d\n", dequeue(&q));
    printf("Front element: %d\n", peek(&q));
    return 0;
}

Advantages of Circular Queue:

  • More efficient use of space compared to a linear queue.
  • Simpler implementation for insertion and deletion at both ends.

Disadvantages:

  • More complex than a linear queue due to the circular nature.
  • The size of the queue is fixed and cannot be changed dynamically unless implemented using dynamic data structures like linked lists.

Conclusion

Understanding queues and circular queues in C programming is essential for managing data in a FIFO manner. Both linear and circular queues have their use cases, with circular queues being more efficient in terms of space utilization. Implementations using arrays and linked lists provide flexibility depending on the requirements. Mastering these structures not only enhances your programming skills but also aids in solving complex algorithmic problems involving data management in a queue-like fashion.




C Programming Data Structures: Queue and Circular Queue - A Beginner's Guide

Introduction

In computer programming, a queue is an abstract data type (ADT) that models the behavior of a line in everyday life, where items are added at one end (rear) and removed from the other (front). The operations follow the First-In-First-Out (FIFO) principle. A circular queue is a special form of a queue in which the last element points back to the first element, making it appear as circular. This structure helps in optimizing memory usage by preventing wastage due to front movement, as seen in traditional queues.

In this guide, we will explore how to implement both queues and circular queues in C with step-by-step examples. We'll also discuss how to set up your development environment, compile your application, and trace the flow of data in the queues.

Setting Up the Development Environment

Before diving into coding, ensure you have the following installed on your system:

  1. C Compiler:

    • GCC (GNU Compiler Collection): Available for most Linux distributions. You can install it via a package manager (e.g., sudo apt-get install gcc on Ubuntu).
    • MinGW (Minimalist GNU for Windows): For Windows users, MinGW allows you to compile and run C code.
    • Xcode Command Line Tools: For macOS users, install the tools through Terminal with xcode-select --install.

  2. Code Editor or IDE:

    • Visual Studio Code:
      • Download and install from the official website: https://code.visualstudio.com/
      • Install C/C++ extension by Microsoft.
    • CLion (JetBrains): A powerful IDE specifically for C/C++.
    • Eclipse CDT: A free IDE widely used for various programming languages, including C.
    • Simple text editors like VSCode, Sublime Text suffice if you’re comfortable with them.

  3. Command Line Interface (CLI):

    • Familiarity with terminals or Command Prompt is essential for compiling and running your code.

Example 1: Implementing a Queue in C

Let’s start with a simple implementation of a linear queue using arrays. Our example queue will support basic operations such as enqueue (adding an item), dequeue (removing an item), checking if it’s full, and checking if it’s empty.

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

#define MAX 5         // Maximum number of elements in the queue

typedef struct {
    int items[MAX];  // Array to store queue elements
    int front;       // Front index of the queue
    int rear;        // Rear index of the queue
} Queue;

// Function prototypes
void createQueue(Queue *q);
int isFull(Queue *q);
int isEmpty(Queue *q);
void enqueue(Queue *q, int value);
int dequeue(Queue *q);
void printQueue(Queue *q);

int main() {
    Queue q;
    createQueue(&q);

    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);
    enqueue(&q, 4);
    enqueue(&q, 5);

    printf("Queue after initial enqueues: ");
    printQueue(&q);

    if(isFull(&q)) {
        printf("Queue is full!\n");
    }

    printf("Dequeued item: %d\n", dequeue(&q));
    printf("Queue after dequeuing an item: ");
    printQueue(&q);

    enqueue(&q, 6);
    printf("Queue after another enqueue: ");
    printQueue(&q);
    
    return 0;
}

void createQueue(Queue *q) {
    q->front = -1;
    q->rear = -1;
}
 
int isFull(Queue *q) {
    if(q->rear == MAX - 1)
        return 1;
    else
        return 0;
}
 
int isEmpty(Queue *q) {
    if(q->front == -1)
        return 1;
    else
        return 0;
}
 
void enqueue(Queue *q, int value) {
    if(isFull(q)) {
        printf("Queue is full!\n");
        return;
    }
    
    if(q->front == -1) {   // If queue is initially empty
        q->front = 0;
    }

    q->rear++;
    q->items[q->rear] = value;
}

int dequeue(Queue *q) {
    int item;

    if(isEmpty(q)) {
        printf("Queue is empty!\n");
        return -1;
    } else {
        item = q->items[q->front];
        q->front++;
        
        if(q->front > q->rear) {    // If queue becomes empty after removing an element
            q->front = q->rear = -1;
        }
        
        return item;
    }
}
 
void printQueue(Queue *q) {
    int i;

    if(isEmpty(q)) {
        printf("Queue is empty!\n");
        return;
    } else {
        printf("Queue elements:\n");
        for(i = q->front; i <= q->rear ; i++) {
            printf("%d ", q->items[i]);
        }
        printf("\n");
    }
}
Explanation:
  • createQueue: Initializes the queue by setting its front and rear to -1.
  • isFull: Checks if the queue is full by verifying if rear has reached MAX-1.
  • isEmpty: Checks if the queue is empty by seeing if front is -1.
  • enqueue: Adds an element to the rear of the queue. Adjusts front to 0 if it's the first insertion.
  • dequeue: Removes an element from the front of the queue, shifting the front to the next element. Resets front and rear to -1 if the queue becomes empty.
  • printQueue: Prints all the elements currently stored in the queue.
Steps to Compile and Run:
  1. Save the above code to queue.c.
  2. Open your command line interface (CLI).
  3. Navigate to the directory containing queue.c.
  4. Compile the code with GCC using the command: 
    gcc queue.c -o queue
  5. Run the compiled program: 
    ./queue
  6. Output: 
    Queue after initial enqueues: Queue elements:
1 2 3 4 5 
Queue is full!
Dequeued item: 1
Queue after dequeuing an item: Queue elements:
2 3 4 5 
Queue after another enqueue: Queue elements:
2 3 4 5 6

Example 2: Implementing a Circular Queue in C

Circular queues solve the issue of front movement wastage by rearranging the storage space effectively. This type of queue wraps around the end of the array and connects back with the beginning.

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

#define MAX 5         // Maximum number of elements in the queue

typedef struct {
    int items[MAX];  // Array to store queue elements
    int front;       // Front index of the queue
    int rear;        // Rear index of the queue
} CircularQueue;

// Function prototypes
void cqCreate(CircularQueue *cq);
int cqIsFull(CircularQueue *cq);
int cqIsEmpty(CircularQueue *cq);
void cqEnqueue(CircularQueue *cq, int value);
int cqDequeue(CircularQueue *cq);
void cqPrint(CircularQueue *cq);

int main() {
    CircularQueue cq;
    cqCreate(&cq);

    cqEnqueue(&cq, 1);
    cqEnqueue(&cq, 2);
    cqEnqueue(&cq, 3);
    cqEnqueue(&cq, 4);
    cqEnqueue(&cq, 5);

    printf("Circular Queue after initial enqueues: ");
    cqPrint(&cq);

    if(cqIsFull(&cq)) {
        printf("Circular Queue is full!\n");
    }

    printf("Dequeued item: %d\n", cqDequeue(&cq));
    printf("Circular Queue after dequeuing an item: ");
    cqPrint(&cq);

    cqEnqueue(&cq, 6);
    printf("Circular Queue after another enqueue: ");
    cqPrint(&cq);
    
    cqEnqueue(&cq, 7);
    printf("Circular Queue after yet another enqueue: ");
    cqPrint(&cq);
    
    return 0;
}

void cqCreate(CircularQueue *cq) {
    cq->front = -1;
    cq->rear = -1;
}
 
int cqIsFull(CircularQueue *cq) {
    if((cq->rear + 1) % MAX == cq->front) {
        return 1;
    } else {
        return 0;
    }
}
 
int cqIsEmpty(CircularQueue *cq) {
    if(cq->front == -1) {
        return 1;
    } else {
        return 0;
    }
}
 
void cqEnqueue(CircularQueue *cq, int value) {
    if(cqIsFull(cq)) {
        printf("Circular Queue is full!\n");
        return;
    }
    if(cq->front == -1) {       // If queue is initially empty
        cq->front = 0;
        cq->rear = 0;
    } else {
        cq->rear = (cq->rear + 1) % MAX; // Rear circularly wraps around
    }
    cq->items[cq->rear] = value;
}

int cqDequeue(CircularQueue *cq) {
    int item;
    if(cqIsEmpty(cq)) {
        printf("Circular Queue is empty!\n");
        return -1;
    } else {
        item = cq->items[cq->front];
        if(cq->front == cq->rear) {  // Only one element is present
            cq->front = cq->rear = -1;
        } else {
            cq->front = (cq->front + 1) % MAX;
        }
        return item;
    }
}

void cqPrint(CircularQueue *cq) {
    int i;
    if(cqIsEmpty(cq)) {
        printf("Circular Queue is empty!\n");
        return;
    }
    printf("Circular Queue elements: \n");
    for(i = cq->front; i != (cq->rear+1)%MAX; i = (i + 1)%MAX) {
        printf("%d ", cq->items[i]);
    }
    printf("\n");
}
Explanation:
  • cqCreate: Initializes the circular queue.
  • cqIsFull: Checks if the queue is full considering the circular property.
  • cqIsEmpty: Checks if the queue is empty.
  • cqEnqueue: Inserts an item into the queue. When the rear reaches the end, it wraps around to the start.
  • cqDequeue: Removes an item from the front. Similarly, when the front reaches the end, it wraps around to the start.
  • cqPrint: Displays current elements in the queue.
Steps to Compile and Run:
  1. Save the above code to circular_queue.c.
  2. Open your command line interface (CLI).
  3. Navigate to the directory containing circular_queue.c.
  4. Compile the code with GCC: 
    gcc circular_queue.c -o circular_queue
  5. Run the compiled program: 
    ./circular_queue
  6. Output 
    Circular Queue after initial enqueues: Circular Queue elements: 
1 2 3 4 5 
Circular Queue is full!
Dequeued item: 1
Circular Queue after dequeuing an item: Circular Queue elements: 
2 3 4 5 
Circular Queue after another enqueue: Circular Queue elements: 
2 3 4 5 6 
Circular Queue after yet another enqueue: Circular Queue is full!

Tracing Data Flow

Understanding the flow of data within the queue helps in debugging and optimizing your code. Here’s how the data flows through our examples:

  • Linear Queue:

    • enqueue(&q, 1): Queue is empty initially (-1, -1); Front and rear updated to 0. Array: [1]
    • enqueue(&q, 2): Now, rear is increased to 1. Array: [1,2]
    • Similar actions occur until the queue is full.
    • dequeue(&q): Front moves to 1. Remaining array: [_,2,3,4,5]
    • More enqueue operations shift rear circularly back to the start.

  • Circular Queue:

    • Same enqueue and dequeue actions but the rear wraps around when it reaches the end.
    • cqEnqueue(&cq, 6): Rear shifts to (5+1)%5 = 0. Array: [6,2,3,4,5]
    • cqDequeue(&cq): Front moves to (1+1)%5 = 2. Array: [6,_,_,4,5]
    • cqEnqueue(&cq, 7): Rear shifts to (0+1)%5 = 1, now the queue appears full (3 == (2+1) % 5). But actually, the queue can take another element because the position at the front is empty. Array: [6,7,_,4,5]

Summary

In this beginners' guide, we covered the fundamental concepts of queues and circular queues in C programming. We started by understanding the nature of the FIFO principle followed by both these structures. We provided two detailed examples for both types of queues illustrating their behavior and usage.

Implementing and experimenting with these concepts will enhance your understanding of how data is managed efficiently in queues and give you a better grasp of memory management in C. Practice modifying these examples and testing them to explore their boundaries and potential uses in practical applications.

Happy coding!