A queue is a linear data structure in computer science that represents an ordered collection of elements
or items. In a queue, elements are added at one end, known as the “rear” or “back” of the queue, and
removed from the other end, known as the “front” or “head” of the queue. This arrangement follows
the principle of “first-in, first-out” (FIFO), meaning that the first element inserted into the queue is the
first one to be removed. Queues are commonly used for tasks such as managing tasks in a printer queue,
handling requests in a web server, or processing messages in a messaging system.
Imagine you’re standing in line at a bank or a bus stop. You’re part of an ordered collection of individuals
waiting for service or transportation. This line you’re in is a real-life example of what computer scientists
call a “queue.”
Primitive Operation on Queue
- Enqueue: This operation involves adding an element to the rear or back of the queue. When you join a queue, you’re essentially enqueueing yourself at the end of the line. In a programming context, when you enqueue an element, it becomes the newest element in the queue, waiting to be processed.
- Dequeue: Dequeueing is the opposite of enqueuing. It involves removing and returning the element at the front or head of the queue. Think of it like the next person in line stepping forward to be served. In programming, dequeuing removes the oldest element from the queue, making the next oldest element now the front of the queue.
- Peek (or Front): Sometimes, you might want to see who’s at the front of the queue without actually removing them. This is where the peek operation comes in. It returns the element at the front of the queue but doesn’t remove it. It’s like taking a quick glance at the person at the front of the line without asking them to step aside.
- IsEmpty: This operation is used to check if the queue is empty. If there are no elements in the queue, it means nobody is waiting in line, and the IsEmpty operation would return true. Otherwise, it returns false, indicating that there are elements in the queue.
- IsFull: Some queue implementations might include an IsFull operation to check if the queue has reached its maximum capacity. If the queue is full and you try to enqueue another element, it might result in an overflow condition. However, not all queue implementations have a fixed capacity, so this operation may not always be needed.
These primitive operations form the backbone of queue functionality, allowing for the orderly addition
and removal of elements according to the FIFO principle. They’re essential for implementing queues in
both real-world scenarios and computer programs.
Queue as an ADT
A Queue, as an Abstract Data Type (ADT), represents a collection of elements where items are added to
the rear and removed from the front, following the FIFO (First-In-First-Out) principle. It encapsulates
operations such as Enqueue (adding), Dequeue (removing), Peek (viewing without removing), IsEmpty
(checking if empty), and Size (counting elements). This abstraction allows for a consistent interface
across various implementations, providing flexibility and modularity in software design. Developers can
choose different underlying data structures, like arrays or linked lists while adhering to the expected
behavior defined by the Queue ADT.
Implementation of Queue using Array
- Array Representation: The elements of the queue are stored in an array, denoted as items, with a fixed maximum size defined by MAXQUEUE.
- Front and Rear Pointers: Two variables, front, and rear, are used to keep track of the positions within the array. front indicates the position of the first element in the queue, while rear indicates the last element’s position.
- Enqueue Operation: To add an element x to the queue, the enqueue(q, x) operation is implemented as q.items[++q.rear] = x. This means that x is placed at the position indicated by the rear, and then the rear is incremented to point to the next available position in the array.
- Dequeue Operation: To remove an element from the queue and return it, the dequeue(q) operation is implemented as x = q.items[q.front++]. This means that the element at the position indicated by the front is assigned to x, and then the front is incremented to point to the next element in the queue.
- Initialization: Initially, when the queue is empty, the rear is set to -1 to indicate no elements are present, and the front is set to 0.
- Empty and Full Conditions: The queue is considered empty when the rear is less than the front (q.rear <q.front). Conversely, the queue is considered full when the rear reaches the maximum capacity of the array (q.rear == MAXQUEUE – 1).
- Number of Elements: The number of elements in the queue at any given time is calculated as q.rear – q.front + 1, which represents the difference between the positions of rear and front, plus one to account for inclusive counting.
This implementation efficiently manages the queue using a fixed-size array and maintains the FIFO
principle with the help of front and rear pointers.
Linear Queue:
A linear queue is a type of queue data structure that follows the FIFO (First-In-First-Out) principle, where
elements are inserted at the rear end and removed from the front end. It has a linear arrangement,
meaning elements are stored in a sequential manner. Linear queues are commonly implemented using
arrays or linked lists. In a linear queue, elements are added (enqueued) at one end and removed
(dequeued) from the other end, maintaining the order in which they were inserted. This structure is
similar to a line of people waiting for service, where the first person to join the line is the first to be
served. Linear queues find applications in various computing scenarios, including task scheduling, job
processing, and data buffering.
Here’s an implementation of a linear queue in C:
#include <stdio.h>
#include <stdlib.h>
#define MAXQUEUE 100
struct Queue {
int items[MAXQUEUE];
int front, rear;
};
// Function to create a new empty queue
struct Queue* createQueue() {
struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
q->front = -1;
q->rear = -1;
return q;
}
// Function to check if the queue is empty
int isEmpty(struct Queue* q) {
return (q->rear == -1);
}
// Function to check if the queue is full
int isFull(struct Queue* q) {
return (q->rear == MAXQUEUE - 1);
}
// Function to add an element to the queue (enqueue)
void enqueue(struct Queue* q, int x) {
if (isFull(q)) {
printf("Queue is full. Overflow!\n");
return;
}
if (isEmpty(q))
q->front = 0;
q->rear++;
q->items[q->rear] = x;
printf("%d enqueued to queue\n", x);
}
// Function to remove an element from the queue (dequeue)
int dequeue(struct Queue* q) {
if (isEmpty(q)) {
printf("Queue is empty. Underflow!\n");
return -1;
}
int item = q->items[q->front];
if (q->front == q->rear) {
q->front = -1;
q->rear = -1;
}
else
q->front++;
printf("%d dequeued from queue\n", item);
return item;
}
// Function to peek the front element of the queue
int peek(struct Queue* q) {
if (isEmpty(q)) {
printf("Queue is empty.\n");
return -1;
}
return q->items[q->front];
}
int main() {
struct Queue* q = createQueue();
enqueue(q, 10);
enqueue(q, 20);
enqueue(q, 30);
printf("Front element: %d\n", peek(q));
dequeue(q);
printf("Front element after dequeue: %d\n", peek(q));
return 0;
}Circular Queue:
A circular queue, also known as a ring buffer, is a variation of the queue data structure in which the last
element is connected back to the first element to form a circle. This circular arrangement allows for
efficient usage of memory and enables elements to wrap around the end of the queue. In a circular
queue, elements are inserted at the rear end and removed from the front end, following the FIFO (First-
In-First-Out) principle. When the queue becomes full, new elements overwrite the oldest elements,
effectively reusing space. Circular queues are commonly implemented using arrays or linked lists and find applications in scenarios where a fixed-size, continuous buffer is required, such as data transmission, input/output handling, and memory management in embedded systems.
Here’s an implementation of a circular queue in C:
#include <stdio.h>
#include <stdlib.h>
#define MAXQUEUE 100
struct CircularQueue {
int items[MAXQUEUE];
int front, rear;
};
// Function to create a new empty circular queue
struct CircularQueue* createCircularQueue() {
struct CircularQueue* q = (struct CircularQueue*)malloc(sizeof(struct CircularQueue));
q->front = -1;
q->rear = -1;
return q;
}
// Function to check if the circular queue is empty
int isEmpty(struct CircularQueue* q) {
return (q->front == -1);
}
// Function to check if the circular queue is full
int isFull(struct CircularQueue* q) {
return ((q->rear + 1) % MAXQUEUE == q->front);
}
// Function to add an element to the circular queue (enqueue)
void enqueue(struct CircularQueue* q, int x) {
if (isFull(q)) {
printf("Queue is full. Overflow!\n");
return;
}
if (isEmpty(q))
q->front = 0;
q->rear = (q->rear + 1) % MAXQUEUE;
q->items[q->rear] = x;
printf("%d enqueued to queue\n", x);
}
// Function to remove an element from the circular queue (dequeue)
int dequeue(struct CircularQueue* q) {
if (isEmpty(q)) {
printf("Queue is empty. Underflow!\n");
return -1;
}
int item = q->items[q->front];
if (q->front == q->rear) {
q->front = -1;
q->rear = -1;
}
else
q->front = (q->front + 1) % MAXQUEUE;
printf("%d dequeued from queue\n", item);
return item;
}
// Function to peek the front element of the circular queue
int peek(struct CircularQueue* q) {
if (isEmpty(q)) {
printf("Queue is empty.\n");
return -1;
}
return q->items[q->front];
}
int main() {
struct CircularQueue* q = createCircularQueue();
enqueue(q, 10);
enqueue(q, 20);
enqueue(q, 30);
printf("Front element: %d\n", peek(q));
dequeue(q);
printf("Front element after dequeue: %d\n", peek(q));
return 0;
}Priority Queue:
A priority queue is a type of queue data structure where each element has an associated priority value.
Unlike a standard queue, where elements are processed in a first-in-first-out (FIFO) manner, in a priority
queue, elements are dequeued based on their priority. Elements with higher priority values are dequeued before elements with lower priority values. Priority queues are commonly implemented using heaps, where elements are stored in a way that ensures that the highest priority element can be efficiently accessed and removed. Priority queues find applications in various scenarios where tasks or events need to be processed based on their relative importance or urgency.
Here’s an implementation of a priority queue in C:
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// Structure to represent an element in the priority queue
struct PriorityQueueElement {
int data;
int priority;
};
// Structure to represent the priority queue
struct PriorityQueue {
struct PriorityQueueElement elements[MAX_SIZE];
int size;
};
// Function to create a new empty priority queue
struct PriorityQueue* createPriorityQueue() {
struct PriorityQueue* pq = (struct PriorityQueue*)malloc(sizeof(struct PriorityQueue));
pq->size = 0;
return pq;
}
// Function to swap two priority queue elements
void swap(struct PriorityQueueElement* a, struct PriorityQueueElement* b) {
struct PriorityQueueElement temp = *a;
*a = *b;
*b = temp;
}
// Function to maintain the min-heap property after inserting an element
void heapifyUp(struct PriorityQueue* pq, int index) {
int parent = (index - 1) / 2;
while (index > 0 && pq->elements[parent].priority > pq->elements[index].priority) {
swap(&pq->elements[parent], &pq->elements[index]);
index = parent;
parent = (index - 1) / 2;
}
}
// Function to maintain the min-heap property after removing an element
void heapifyDown(struct PriorityQueue* pq, int index) {
int leftChild = 2 * index + 1;
int rightChild = 2 * index + 2;
int smallest = index;
if (leftChild < pq->size && pq->elements[leftChild].priority < pq->elements[smallest].priority)
smallest = leftChild;
if (rightChild < pq->size && pq->elements[rightChild].priority < pq->elements[smallest].priority)
smallest = rightChild;
if (smallest != index) {
swap(&pq->elements[index], &pq->elements[smallest]);
heapifyDown(pq, smallest);
}
}
// Function to remove and return the element with the highest priority from the priority queue
struct PriorityQueueElement dequeue(struct PriorityQueue* pq) {
if (pq->size <= 0) {
printf("Queue is empty. Underflow!\n");
struct PriorityQueueElement emptyElement = { -1, -1 };
return emptyElement;
}
struct PriorityQueueElement minElement = pq->elements[0];
pq->elements[0] = pq->elements[pq->size - 1];
pq->size--;
heapifyDown(pq, 0);
return minElement;
}
// Function to check if the priority queue is empty
int isEmpty(struct PriorityQueue* pq) {
return (pq->size == 0);
}
int main() {
struct PriorityQueue* pq = createPriorityQueue();
enqueue(pq, 10, 3);
enqueue(pq, 20, 2);
enqueue(pq, 30, 1);
enqueue(pq, 40, 4);
while (!isEmpty(pq)) {
struct PriorityQueueElement element = dequeue(pq);
printf("Dequeued element: %d with priority: %d\n", element.data, element.priority);
}
return 0;
}Application of Queue:
- Operating Systems: Managing process scheduling and I/O buffers.
- Networking: Packet routing and message queues.
- Data Structures: Breadth-First Search (BFS) and binary tree traversal.
- Simulation: Event simulation and customer service modeling.
- Hardware Design: CPU pipeline management.
- Web Servers: Handling incoming HTTP requests.