How can you implement a queue in C?

1 Array-based queue

One way to implement a queue in C is to use an array and two variables that keep track of the front and rear of the queue. The front variable points to the index of the first element in the queue, and the rear variable points to the index of the last element. To enqueue (add) an element, you need to increment the rear variable and store the element at that index. To dequeue (remove) an element, you need to return the element at the front index and increment the front variable. You also need to check if the queue is full or empty before performing these operations. Here is an example of an array-based queue in C:

#define MAX 10 // maximum size of the queue
int queue[MAX]; // array to store the queue elements
int front = -1; // front of the queue
int rear = -1; // rear of the queue
// function to check if the queue is full
int isFull() {
  return (rear == MAX - 1);
}
// function to check if the queue is empty
int isEmpty() {
  return (front == -1 || front > rear);
}
// function to enqueue an element
void enqueue(int x) {
  if (isFull()) {
    printf("Queue is full.\n");
  } else {
    if (front == -1) {
      front = 0; // initialize front if the queue was empty
    }
    rear++; // increment rear
    queue[rear] = x; // store the element at rear index
    printf("Enqueued %d.\n", x);
  }
}
// function to dequeue an element
int dequeue() {
  if (isEmpty()) {
    printf("Queue is empty.\n");
    return -1;
  } else {
    int x = queue[front]; // get the element at front index
    front++; // increment front
    printf("Dequeued %d.\n", x);
    return x;
  }
}        

2 Pointer-based queue

Another way to implement a queue in C is to use a linked list and two pointers that point to the head and tail of the list. The head pointer points to the first node in the list, and the tail pointer points to the last node. Each node contains a data value and a next pointer that points to the next node in the list. To enqueue an element, you need to create a new node with the element as the data value and append it to the end of the list. To dequeue an element, you need to return the data value of the head node and remove it from the list. You also need to update the head and tail pointers accordingly. Here is an example of a pointer-based queue in C:

// structure to represent a node
struct node {
  int data; // data value
  struct node *next; // next pointer
};
// pointers to the head and tail of the list
struct node *head = NULL;
struct node *tail = NULL;
// function to create a new node with a given data value
struct node *newNode(int x) {
  struct node *temp = (struct node *)malloc(sizeof(struct node)); // allocate memory
  temp->data = x; // assign data value
  temp->next = NULL; // initialize next pointer
  return temp; // return the node
}
// function to enqueue an element
void enqueue(int x) {
  struct node *temp = newNode(x); // create a new node
  if (head == NULL) {
    head = temp; // set head to the new node if the list was empty
  } else {
    tail->next = temp; // append the new node to the end of the list
  }
  tail = temp; // set tail to the new node
  printf("Enqueued %d.\n", x);
}
// function to dequeue an element
int dequeue() {
  if (head == NULL) {
    printf("Queue is empty.\n");
    return -1;
  } else {
    int x = head->data; // get the data value of the head node
    struct node *temp = head; // store the head node in a temporary variable
    head = head->next; // move the head pointer to the next node
    free(temp); // free the memory of the removed node
    if (head == NULL) {
      tail = NULL; // set tail to NULL if the list becomes empty
    }
    printf("Dequeued %d.\n", x);
    return x;
  }
}        

3 Here’s what else to consider

This is a space to share examples, stories, or insights that don’t fit into any of the previous sections. What else would you like to add?