Queues are an essential data structure in computer science used to manage collections of elements in a specific order. Queues follow the First-In-First-Out (FIFO) principle, where the first element that was added to the queue is the first one to be removed.
Queues are used in a variety of applications, such as process scheduling, network packet queuing, printer queuing, and call center queuing. Understanding and implementing queues is a fundamental skill for computer science engineering students.
This article provides a beginner’s guide to help them understand and implement queues using arrays and linked lists. We will also discuss the basic operations of a queue and the applications of queues in various fields.
What is a Queue?
A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. It is a collection of elements in which the elements are added at one end called the rear, and removed from the other end called the front.
Think of a queue as a line of people waiting for a service where the first person who joined the queue is the first one to receive the service, and the last person who joined the queue is the last one to receive the service.
Basic Operations on a Queue
The basic operations that can be performed on a queue are:
Enqueue: It adds an element to the end of the queue. The new element becomes the rear of the queue.
Dequeue: It removes an element from the front of the queue. The element that is removed is the one that has been in the queue the longest.
Peek: It returns the element at the front of the queue without removing it. This operation is used to view the element that is next to be removed.
isEmpty: It checks whether the queue is empty or not. If the queue is empty, it returns true; otherwise, it returns false.
isFull: It checks whether the queue is full or not. If the queue is full, it returns true; otherwise, it returns false.
Queue operations with example
Suppose we have a queue of integers with five elements: 1, 2, 3, 4, and 5. The front of the queue is 1, and the rear of the queue is 5.
Enqueue operation: Suppose we want to add an element 6 to the queue. We will call the enqueue operation with the element 6 as a parameter. The queue will now become 1, 2, 3, 4, 5, 6, where 6 is the rear of the queue.
Dequeue operation: Suppose we want to remove an element from the queue. We will call the dequeue operation, and the front element 1 will be removed from the queue. The queue will now become 2, 3, 4, 5, 6, where 2 is the new front of the queue.
Peek operation: Suppose we want to see the element at the front of the queue without removing it. We will call the peek operation, and the value returned will be 2.
isEmpty operation: Suppose we want to check whether the queue is empty or not. We will call the isEmpty operation, and since the queue is not empty, it will return false.
isFull operation: Suppose we want to check whether the queue is full or not. Since the queue has no maximum capacity defined, it will never be full, and the isFull operation will always return false.
These are the basic operations that can be performed on a queue. These operations help in implementing a queue and provide a way to manage and manipulate the elements of a queue.
Implementing a Queue
There are two ways to implement a queue: using an array and using a linked list.
Queue implementation using an array
In the array implementation, we maintain a front pointer and a rear pointer. The front pointer points to the first element in the queue, and the rear pointer points to the last element in the queue.
Initially, both pointers point to -1, indicating that the queue is empty. When we enqueue an element, we increment the rear pointer and add the element to the rear position.
When we dequeue an element, we increment the front pointer and remove the element from the front position. The following is the implementation of a queue using an array:
#define MAX_SIZE 10
int queue[MAX_SIZE];
int front = -1;
int rear = -1;
void enqueue(int element) {
if(rear == MAX_SIZE-1) {
printf("Queue Overflown");
} else {
rear++;
queue[rear] = element;
if(front == -1) {
front = 0;
}
}
}
int dequeue() {
int element;
if(front == -1 || front > rear) {
printf("Queue Underflown");
return -1;
} else {
element = queue[front];
front++;
return element;
}
}
int peek() {
if(front == -1 || front > rear) {
printf("Queue Underflown");
return -1;
} else {
return queue[front];
}
}
int isEmpty() {
if(front == -1 || front > rear) {
return 1;
} else {
return 0;
}
}
int isFull() {
if(rear == MAX_SIZE-1) {
return 1;
} else {
return 0;
}
}
Queue implementation using a linked list
In the linked list implementation, we maintain a front pointer and a rear pointer. The front pointer points to the first element in the queue, and the rear pointer points to the last element in the queue.
When we enqueue an element, we create a new node and add it to the rear of the linked list. When we dequeue an element, we remove the first node in the linked list and update the front pointer to point to the next node.
The following is the implementation of a queue using a linked list:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node* front = NULL;
struct Node* rear = NULL;
void enqueue(int element) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = element;
newNode->next = NULL;
if(front == NULL && rear == NULL) {
front = rear = newNode;
return;
}
rear->next = newNode;
rear = newNode;
}
int dequeue() {
int element;
struct Node* temp;
if(front == NULL) {
printf("Queue Underflown");
return -1;
}
temp = front;
front = front->next;
element = temp->data;
free(temp);
return element;
}
int peek() {
if(front == NULL) {
printf("Queue Underflown");
return -1;
} else {
return front->data;
}
}
int isEmpty() {
if(front == NULL) {
return 1;
} else {
return 0;
}
}
int isFull() {
return 0;
}
Applications of Queue
Queues have numerous applications in computer science, ranging from operating systems to network protocols. Some of the most common applications of queues are:
Job scheduling: Queues are commonly used in operating systems to manage and schedule processes. Processes are placed in a queue and the operating system schedules them based on their priority and other criteria.
Print spooling: When multiple users send print jobs to a printer, a queue is used to manage the order in which the print jobs are processed. The printer processes each job in the order in which it was added to the queue.
Task processing: In many applications, tasks are added to a queue and processed sequentially. For example, in a web application, user requests may be added to a queue and processed by a worker process one at a time.
Breadth-first search: In graph theory, breadth-first search is an algorithm that traverses a graph by exploring all the vertices at a given distance from the starting vertex before moving on to vertices at a greater distance. A queue is used to maintain the order in which vertices are explored.
Simulations: Queues are commonly used in simulations to model real-world scenarios. For example, a queue may be used to simulate customers waiting in line at a store, or cars waiting at a traffic signal.
Network protocols: Queues are used in network protocols to manage packets of data that are sent over a network. Packets are placed in a queue and transmitted in the order in which they were received.
These are just a few examples of the many applications of queues in computer science.
Conclusion
Queues are a fundamental data structure that can be used in a wide variety of contexts, and understanding how to implement and use them effectively is an important skill for any computer science student.
In this article, we provided a beginner’s guide to understanding and implementing queues using arrays and linked lists.
We also discussed the basic operations of a queue and the applications of queues in various fields.