Queues are an essential data structure in computer programming that follow the First-In-First-Out (FIFO) rule. Similar to a queue outside a cinema hall, where the first person entering the queue is the first person to get a ticket, a queue in programming operates in a similar fashion. The item that goes into the queue first is the item that comes out first.

In this article, we will explore the concept of queues in data structures, focusing on their basic operations, implementation in various programming languages like C, and their applications in real-world scenarios. We will also provide code examples and illustrations to help you better understand the concept.

Understanding Queues

A queue is a linear data structure that allows the insertion of elements at one end and the removal of elements from the other end. The end where elements are inserted is called the rear, and the end from which elements are removed is called the front. This FIFO behavior makes queues suitable for scenarios where the order of insertion and removal of elements needs to be maintained.

Basic Operations of a Queue

A queue supports several basic operations, including:

Enqueue

The enqueue operation adds an element to the end of the queue. It involves checking if the queue is full, incrementing the rear pointer, and adding the new element to the position pointed to by the rear.

Dequeue

The dequeue operation removes an element from the front of the queue. It involves checking if the queue is empty, returning the value pointed by the front, incrementing the front pointer, and resetting the values of front and rear if the last element is removed.

IsEmpty

The isEmpty operation checks if the queue is empty by verifying if the front pointer is -1.

IsFull

The isFull operation checks if the queue is full by checking if the rear pointer has reached the maximum size.

Peek

The peek operation allows you to get the value of the front of the queue without removing it. It involves accessing the data element where the front pointer is pointing.

 

Queue Implementations with Array in C

Now let’s look at how queues can be implemented in the C programming language using arrays.

 

#include <stdio.h>
#define MAX_SIZE 5

int queue[MAX_SIZE];
int front = -1;
int rear = -1;

int isFull() {
  if (rear == MAX_SIZE - 1) {
    return 1;
  }
  return 0;
}

int isEmpty() {
  if (front == -1) {
    return 1;
  }
  return 0;
}

void enqueue(int item) {
  if (isFull()) {
    printf("Queue is full.\n");
  } else {
    if (front == -1) {
      front = 0;
    }
    rear++;
    queue[rear] = item;
    printf("Enqueued: %d\n", item);
  }
}

int dequeue() {
  int item;
  if (isEmpty()) {
    printf("Queue is empty.\n");
    return -1;
  } else {
    item = queue[front];
    if (front == rear) {
      front = -1;
      rear = -1;
    } else {
      front++;
    }
    printf("Dequeued: %d\n", item);
    return item;
  }
}

void display() {
  int i;
  if (isEmpty()) {
    printf("Queue is empty.\n");
  } else {
    printf("Queue: ");
    for (i = front; i <= rear; i++) {
      printf("%d ", queue[i]);
    }
    printf("\n");
  }
}

int main() {
  enqueue(1);
  enqueue(2);
  enqueue(3);
  enqueue(4);
  enqueue(5);

  display();

  dequeue();

  printf("After removing an element\n");
  display();

  return 0;
}

 

Queue Implementations with Linked List in C

Now let’s look at how queues can be implemented in the C programming language using a linked list.

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

// Define the Node structure
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Define the Queue structure
typedef struct Queue {
    Node* front;
    Node* rear;
} Queue;

// Create a new node
Node* newNode(int data) {
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->data = data;
    temp->next = NULL;
    return temp;
}

// Initialize a new queue
Queue* createQueue() {
    Queue* q = (Queue*)malloc(sizeof(Queue));
    q->front = q->rear = NULL;
    return q;
}

// Enqueue an item to the queue
void enqueue(Queue* q, int data) {
    Node* temp = newNode(data);

    if (q->rear == NULL) {
        q->front = q->rear = temp;
        return;
    }

    q->rear->next = temp;
    q->rear = temp;
}

// Dequeue an item from the queue
int dequeue(Queue* q) {
    if (q->front == NULL) {
        printf("Queue is empty!\n");
        return -1; // Indicating the queue is empty
    }

    Node* temp = q->front;
    int data = temp->data;

    q->front = q->front->next;

    if (q->front == NULL) {
        q->rear = NULL;
    }

    free(temp);
    return data;
}

// Get the front item of the queue without dequeueing
int front(Queue* q) {
    if (q->front == NULL) {
        printf("Queue is empty!\n");
        return -1; 
    }
    return q->front->data;
}

// Check if the queue is empty
int isEmpty(Queue* q) {
    return q->front == NULL;
}

int main() {
    Queue* q = createQueue();

    enqueue(q, 10);
    enqueue(q, 20);
    enqueue(q, 30);

    printf("Front element: %d\n", front(q));
    printf("Dequeued element: %d\n", dequeue(q));
    printf("Front element after dequeue: %d\n", front(q));

    return 0;
}

Advantages and Limitations of Queue:

Advantages:

• Direct access to the topmost element with O(1) complexity.
• Memory allocation is straightforward, ensuring efficient access.

Limitations:

• The size of the stack is fixed. If the stack exceeds its capacity, we’ll encounter a “Stack Overflow”.
• Similarly, if you try to pop an element from an empty stack, it will result in a “Stack Underflow”.

 

Applications of Queues

Queues find applications in various real-world scenarios where the order of processing or access needs to be maintained. Some common applications of queues include:

Operating Systems – Process Scheduling

In operating systems, queues are used to implement process scheduling algorithms like round-robin scheduling. Processes are added to a queue and executed in the order they were added, ensuring fair allocation of CPU time.

Printer Spooling

Printers utilize queues to maintain the order of print jobs. When multiple print jobs are sent to a printer, they are added to a queue and processed one by one, ensuring that each print job is handled in the order it was received.

Messaging Applications

Messaging applications like WhatsApp or Facebook Messenger use queues to maintain the order of messages. When a user sends a message, it is added to the recipient’s message queue and delivered in the order it was sent, ensuring message integrity.

Call Center Phone Systems

Call center phone systems utilize queues to manage incoming calls. Calls are added to a queue and answered by available agents in the order they were received, ensuring a fair distribution of calls among agents.

Time And Space Complexity

Conclusion

Queues are an important data structure in programming, following the First-In-First-Out (FIFO) rule. They allow for the orderly insertion and removal of elements, making them useful in scenarios where the order of processing or access needs to be maintained. Implementations of queues can be found in various programming languages, including C, Java, and Python. Understanding queues and their applications can greatly enhance your programming skills and help you design efficient and organized systems.

Remember to consider the specific requirements of your programming language and the problem you are trying to solve when implementing queues. With the knowledge of queue operations and their implementations, you can tackle a wide range of programming challenges efficiently and effectively.