Queues are data structures and algorithms used to store and process data in a particular order. This follows the FIFO (first in, first out) principle. That is, the first item entered is processed first. Queues are commonly used by applications such as operating systems, network protocols, and web servers to manage requests from multiple users or tasks. It also helps ensure system fairness by granting equal access to all users or tasks. Queue data structures can be implemented using various algorithms such as linked lists, arrays, and circular arrays.
Learn the concepts of DSA with the complete beginner-friendly video tutorial course Data Structures & Algorithms using Java
Representation of Queues
Complexity
Basic Operations of Queue
A queue is an object (an abstract data structure - ADT) that allows the following operations:
Enqueue : Add an element to the end of the queue
Dequeue : Remove an element from the front of the queue
IsEmpty : Check if the queue is empty
IsFull : Check if the queue is full
Peek : Get the value of the front of the queue without removing it
Types of Queue
Simple Queue or Linear Queue
Circular Queue
Priority Queue
Double Ended Queue (or Deque)
Linear Queue
A linear queue is a data structure used to store and manage data on a first-in, first-out (FIFO) basis. It is a sort of abstract data type consisting of an ordered collection of elements, with the addition of new elements and the removal of existing elements at one end, called the "front". A circular queue that allows both additions and deletions at both ends. Linear queues are useful for implementing batches and solving problems related to task or process scheduling. It can also be used to store data in sequence, making it ideal for applications such as job scheduling and task management systems.
Ways to implement the queue
Using Array –
Arrays can be used to represent queue data structures. In this representation, the queue is implemented using a fixed-size array, with two pointers (front and back) to track the first and last element of the queue respectively.
Initially, both front and back are set to -1 to indicate that the queue is empty. When an item is added to the queue, the rear pointer is incremented and the item is inserted at the index pointed to by the rear. If the queue is empty, the front and back are incremented and the first element is inserted at index 0. When an element is dequeued, the front pointer is incremented and the element at the index pointed to by the front is returned. Both front and back are set to -1 when the queue is empty.
Using Linked List –
Linked lists can also be used to represent queue data structures. In this representation, the queue is implemented using a singly linked list where each node stores an element of the queue and a pointer to the next node.
Two pointers, front and back, are used to track the first and last element of the queue respectively. Initially, both front and back are set to NULL to indicate that the queue is empty.
When an item is added to the queue, a new node is created and the item is stored in the node. If the queue is empty, both the front and back are set to point to the new node. Otherwise, the back pointer is updated to point to the new node.
As the element is dequeued, the front pointer is updated to point to the next node, and the element stored at the node pointed to by the original front pointer is returned. Both front and back are set to NULL when the queue is empty.
Implementation of Queue in C
// Queue implementation in C
#include <stdio.h>
#define SIZE 5
void enQueue(int);
void deQueue();
void display();
int items[SIZE], front = -1, rear = -1;
int main() {
//deQueue is not possible on empty queue
deQueue();
//enQueue 5 elements
enQueue(1);
enQueue(2);
enQueue(3);
enQueue(4);
enQueue(5);
// 6th element can't be added to because the queue is full
enQueue(6);
display();
//deQueue removes element entered first i.e. 1
deQueue();
//Now we have just 4 elements
display();
return 0;
}
void enQueue(int value) {
if (rear == SIZE - 1)
printf("\nQueue is Full!!");
else {
if (front == -1)
front = 0;
rear++;
items[rear] = value;
printf("\nInserted -> %d", value);
}
}
void deQueue() {
if (front == -1)
printf("\nQueue is Empty!!");
else {
printf("\nDeleted : %d", items[front]);
front++;
if (front > rear)
front = rear = -1;
}
}
// Function to print the queue
void display() {
if (rear == -1)
printf("\nQueue is Empty!!!");
else {
int i;
printf("\nQueue elements are:\n");
for (i = front; i <= rear; i++)
printf("%d ", items[i]);
}
printf("\n");
}
Circular Queue
A circular queue is a data structure used to store and retrieve data in computer programming. This is a linear data structure that stores elements cyclically. It works on the principle of FIFO (first in, first out). In other words, items added to the queue first are removed from the queue first.
Working of Circular Queue
A circular queue is a data structure that uses arrays to store elements in a circular fashion. Used to store and manage data in a queue-like manner, where the last element of the queue is wrapped to become the first element. This allows for efficient memory usage and efficient insert and deletes operations. A circular queue works by maintaining two-pointers. One point to the head of the queue and one point to the back of the queue. When an item is added to the queue it is inserted at the back pointer position, but when an item is removed from the queue it is removed from the front pointer position. This ensures that items are always added and removed on a first-in, first-out (FIFO) basis.
Operations on Circular Queue
Front: It is used to get the front element from the Queue.
Rear: It is used to get the rear element from the Queue.
enQueue(value): This function is used to insert the new value in the Queue. The new element is always inserted from the rear end.
deQueue(): This function deletes an element from the Queue. The deletion in a Queue always takes place from the front end.
Implementation of Circular Queue in C
// Circular Queue implementation in C
#include <stdio.h>
#define SIZE 5
int items[SIZE];
int front = -1, rear = -1;
// Check if the queue is full
int isFull() {
if ((front == rear + 1) || (front == 0 && rear == SIZE - 1)) return 1;
return 0;
}
// Check if the queue is empty
int isEmpty() {
if (front == -1) return 1;
return 0;
}
// Adding an element
void enQueue(int element) {
if (isFull())
printf("\n Queue is full!! \n");
else {
if (front == -1) front = 0;
rear = (rear + 1) % SIZE;
items[rear] = element;
printf("\n Inserted -> %d", element);
}
}
// Removing an element
int deQueue() {
int element;
if (isEmpty()) {
printf("\n Queue is empty !! \n");
return (-1);
} else {
element = items[front];
if (front == rear) {
front = -1;
rear = -1;
}
// Q has only one element, so we reset the
// queue after dequeing it. ?
else {
front = (front + 1) % SIZE;
}
printf("\n Deleted element -> %d \n", element);
return (element);
}
}
// Display the queue
void display() {
int i;
if (isEmpty())
printf(" \n Empty Queue\n");
else {
printf("\n Front -> %d ", front);
printf("\n Items -> ");
for (i = front; i != rear; i = (i + 1) % SIZE) {
printf("%d ", items[i]);
}
printf("%d ", items[i]);
printf("\n Rear -> %d \n", rear);
}
}
int main() {
// Fails because front = -1
deQueue();
enQueue(1);
enQueue(2);
enQueue(3);
enQueue(4);
enQueue(5);
// Fails to enqueue because front == 0 && rear == SIZE - 1
enQueue(6);
display();
deQueue();
display();
enQueue(7);
display();
// Fails to enqueue because front == rear + 1
enQueue(8);
return 0;
}
Also Read: Stack in Data Structure and Implementation