Queues

By Notes Vandar

3.1 Definition

A queue is a linear data structure that follows the First In, First Out (FIFO) principle, meaning that the first element added to the queue will be the first one to be removed. Queues are used in various applications, such as scheduling processes, managing requests in servers, and handling asynchronous data transfers.

Types of Queues

  1. Simple Queue: A basic queue structure that allows operations only at the front and rear.
  2. Circular Queue: A queue where the last position is connected back to the first position, making efficient use of space.
  3. Priority Queue: Each element has a priority, and the element with the highest priority is served before others.
  4. Double-Ended Queue (Deque): Allows insertion and deletion of elements from both ends.

3.2 Queue as an ADT

Key Characteristics of Queue ADT

  1. FIFO Principle: The queue operates on a First In, First Out basis, meaning the first element added to the queue will be the first one to be removed.
  2. Operations: The queue ADT provides a standard set of operations that can be performed on it. These operations include:
    • Enqueue: Insert an element at the rear of the queue.
    • Dequeue: Remove an element from the front of the queue.
    • Peek/Front: Access the front element without removing it.
    • IsEmpty: Check if the queue is empty.
    • IsFull: Check if the queue is full (if implemented with a fixed size).
  3. Dynamic Behavior: Depending on its implementation (using arrays, linked lists, or other structures), a queue can grow and shrink dynamically.

Queue ADT Operations

Here’s a description of the key operations associated with the queue ADT:

  1. Enqueue Operation:
    • Input: An element to be added to the queue.
    • Output: None.
    • Description: Adds the element to the rear of the queue. If the queue is full, it indicates an overflow condition.
  2. Dequeue Operation:
    • Input: None.
    • Output: The element removed from the front of the queue.
    • Description: Removes and returns the element at the front of the queue. If the queue is empty, it indicates an underflow condition.
  3. Peek/Front Operation:
    • Input: None.
    • Output: The element at the front of the queue.
    • Description: Returns the front element without removing it from the queue. If the queue is empty, it typically returns a null or an error value.
  4. IsEmpty Operation:
    • Input: None.
    • Output: Boolean (true/false).
    • Description: Checks whether the queue has any elements. Returns true if empty, false otherwise.
  5. IsFull Operation:
    • Input: None.
    • Output: Boolean (true/false).
    • Description: Checks if the queue has reached its maximum capacity (in case of a fixed-size queue). Returns true if full, false otherwise.

Pseudocode for Queue ADT

Here’s a simple pseudocode representation of the Queue ADT:

ADT Queue
// Properties
front: integer
rear: integer
items: array of size MAX

// Operations
FUNCTION initQueue()
front <- -1
rear <- -1

FUNCTION isEmpty()
RETURN front == -1

FUNCTION isFull()
RETURN (rear + 1) % MAX == front

FUNCTION enqueue(value)
IF isFull() THEN
PRINT “Queue Overflow”
ELSE
IF isEmpty() THEN
front <- 0
ENDIF
rear <- (rear + 1) % MAX
items[rear] <- value
ENDIF

FUNCTION dequeue()
IF isEmpty() THEN
PRINT “Queue Underflow”
RETURN NULL
ELSE
value <- items[front]
IF front == rear THEN
front <- -1
rear <- -1
ELSE
front <- (front + 1) % MAX
ENDIF
RETURN value
ENDIF

FUNCTION peek()
IF isEmpty() THEN
RETURN NULL
ELSE
RETURN items[front]
ENDIF
END ADT

Implementation Considerations

  • Fixed-size Queue: Can be implemented using an array with a defined maximum size. Care must be taken to handle overflow and underflow conditions.
  • Dynamic Queue: Can be implemented using linked lists, allowing the queue to grow and shrink dynamically as elements are added or removed.

Applications of Queue ADT

  • Task Scheduling: Used in operating systems for process scheduling, where processes are queued and executed in order.
  • Print Spooling: Managing print jobs sent to a printer.
  • Breadth-First Search (BFS): In graph algorithms, a queue is used to explore nodes level by level.
  • Buffering: Used in IO buffers where data is processed in the order it arrives.

 

3.3 Primitive operations in queue: Enqueue and Dequeue

Primitive Operations in Queue: Enqueue and Dequeue

In the context of a queue as an Abstract Data Type (ADT), two fundamental operations are Enqueue and Dequeue. These operations are critical for managing the flow of data within the queue and adhere to the First In, First Out (FIFO) principle.

1. Enqueue Operation

Definition: The Enqueue operation adds an element to the rear (end) of the queue.

Characteristics:

  • It modifies the queue by adding a new element.
  • If the queue is already full (in the case of a fixed-size implementation), the operation indicates an overflow condition.
  • It may adjust the rear pointer or index to reflect the new position of the last element.

Pseudocode:

FUNCTION Enqueue(queue, value)
IF IsFull(queue) THEN
PRINT “Queue Overflow”
RETURN
ENDIF

IF IsEmpty(queue) THEN
queue.front <- 0 // Set front to 0 if the queue was empty
ENDIF

queue.rear <- (queue.rear + 1) % MAX // Circular increment of rear
queue.items[queue.rear] <- value // Insert the value at rear
PRINT value, “enqueued to queue”
END FUNCTION

Example:

Queue: [ ]
Enqueue 10
Queue: [10]

Enqueue 20
Queue: [10, 20]

Enqueue 30
Queue: [10, 20, 30]

2. Dequeue Operation

Definition: The Dequeue operation removes an element from the front of the queue.

Characteristics:

  • It modifies the queue by removing an existing element.
  • If the queue is empty, the operation indicates an underflow condition.
  • It may adjust the front pointer or index to reflect the new position of the first element.

Pseudocode:

FUNCTION Dequeue(queue)
IF IsEmpty(queue) THEN
PRINT “Queue Underflow”
RETURN NULL
ENDIF

value <- queue.items[queue.front] // Retrieve the front element
IF queue.front == queue.rear THEN
// The queue will become empty after this operation
queue.front <- -1
queue.rear <- -1
ELSE
queue.front <- (queue.front + 1) % MAX // Circular increment of front
ENDIF

PRINT value, “dequeued from queue”
RETURN value
END FUNCTION

Example:

Queue: [10, 20, 30]
Dequeue
Output: 10
Queue: [20, 30]

Dequeue
Output: 20
Queue: [30]

Implementation in C

Here’s a simple implementation of the Enqueue and Dequeue operations in C using a queue represented by an array.

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

#define MAX 5

typedef struct {
int items[MAX];
int front;
int rear;
} Queue;

// Function to initialize the queue
void initQueue(Queue* q) {
q->front = -1;
q->rear = -1;
}

// Function to check if the queue is empty
int isEmpty(Queue* q) {
return q->front == -1;
}

// Function to check if the queue is full
int isFull(Queue* q) {
return (q->rear + 1) % MAX == q->front;
}

// Function to enqueue an element
void enqueue(Queue* q, int value) {
if (isFull(q)) {
printf(“Queue Overflow! Cannot enqueue %d\n”, value);
return;
}
if (isEmpty(q)) {
q->front = 0; // Set front to 0 if the queue was empty
}
q->rear = (q->rear + 1) % MAX; // Circular increment of rear
q->items[q->rear] = value; // Insert the value at rear
printf(“%d enqueued to queue.\n”, value);
}

// Function to dequeue an element
int dequeue(Queue* q) {
if (isEmpty(q)) {
printf(“Queue Underflow! Cannot dequeue\n”);
return -1; // Return an error value
}
int dequeuedValue = q->items[q->front]; // Retrieve the front element
if (q->front == q->rear) { // The queue will become empty
q->front = -1;
q->rear = -1;
} else {
q->front = (q->front + 1) % MAX; // Circular increment of front
}
printf(“%d dequeued from queue.\n”, dequeuedValue);
return dequeuedValue;
}

// Main function to demonstrate Enqueue and Dequeue
int main() {
Queue q;
initQueue(&q);

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

return 0;
}

3.4 Linear Queue, Circular Queue, Priority Queue.

Queues are essential data structures that organize data in a specific order, typically following the First In, First Out (FIFO) principle. Different types of queues serve various applications and performance requirements. Here are three common types: Linear Queue, Circular Queue, and Priority Queue.

1. Linear Queue

Definition: A Linear Queue is a straightforward implementation of a queue, where elements are arranged in a linear order. In a linear queue, the first element added is the first one to be removed (FIFO).

Characteristics:

  • Structure: Implemented using an array or linked list.
  • Fixed Size: If implemented using an array, the size of the queue is fixed.
  • Overflow Condition: Occurs when attempting to add an element to a full queue.
  • Underflow Condition: Occurs when attempting to remove an element from an empty queue.

Operations:

  • Enqueue: Adds an element to the rear of the queue.
  • Dequeue: Removes an element from the front of the queue.

Example:

Queue: [1, 2, 3, 4]
Dequeue → Removes 1
Queue: [2, 3, 4]
Enqueue 5 → Adds 5
Queue: [2, 3, 4, 5]

C Implementation:

#define MAX 5
int queue[MAX];
int front = -1;
int rear = -1;

void enqueue(int value) {
if (rear == MAX – 1) {
printf(“Queue Overflow\n”);
return;
}
if (front == -1) {
front = 0; // First element
}
queue[++rear] = value;
}

int dequeue() {
if (front == -1) {
printf(“Queue Underflow\n”);
return -1;
}
int value = queue[front++];
if (front > rear) {
front = rear = -1; // Reset queue
}
return value;
}

2. Circular Queue

Definition: A Circular Queue is an advanced version of a linear queue that efficiently utilizes the available space by connecting the last position back to the first position, thus forming a circle.

Characteristics:

  • Circular Structure: The last position points to the first position.
  • No Wasted Space: Allows for efficient use of space, especially after multiple enqueue and dequeue operations.
  • Wrap Around: The rear and front can wrap around to the beginning of the array when reaching the end.

Operations:

  • Enqueue: Adds an element to the rear. The rear pointer wraps around if it reaches the end of the array.
  • Dequeue: Removes an element from the front. The front pointer wraps around if it reaches the end of the array.

Example:

Queue: [(priority 2, ‘A’), (priority 1, ‘B’), (priority 3, ‘C’)]
Remove → Removes ‘C’ (highest priority)
Queue: [(priority 2, ‘A’), (priority 1, ‘B’)]

C Implementation:

#define MAX 5
int queue[MAX];
int front = -1;
int rear = -1;

void enqueue(int value) {
if ((rear + 1) % MAX == front) {
printf(“Queue Overflow\n”);
return;
}
if (front == -1) {
front = 0; // First element
}
rear = (rear + 1) % MAX; // Circular increment
queue[rear] = value;
}

int dequeue() {
if (front == -1) {
printf(“Queue Underflow\n”);
return -1;
}
int value = queue[front];
if (front == rear) {
front = rear = -1; // Reset queue
} else {
front = (front + 1) % MAX; // Circular increment
}
return value;
}

3. Priority Queue

Definition: A Priority Queue is a specialized queue where each element has a priority associated with it. Elements are dequeued based on their priority rather than their order in the queue. The element with the highest priority is processed first.

Characteristics:

  • Priority Levels: Elements can have different levels of importance. Higher priority elements are dequeued before lower priority ones.
  • Dynamic Size: Usually implemented using a dynamic data structure, such as a heap, for efficient access and modification.
  • Not FIFO: Unlike standard queues, priority queues do not follow the FIFO principle; they follow priority levels.

Operations:

  • Insert: Adds an element to the queue with an associated priority.
  • Remove: Removes the element with the highest priority.

Example:

Queue: [(priority 2, ‘A’), (priority 1, ‘B’), (priority 3, ‘C’)]
Remove → Removes ‘C’ (highest priority)
Queue: [(priority 2, ‘A’), (priority 1, ‘B’)]

C Implementation:

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

typedef struct {
int priority;
char data;
} Node;

typedef struct {
Node* arr;
int size;
int capacity;
} PriorityQueue;

void insert(PriorityQueue* pq, char data, int priority) {
if (pq->size == pq->capacity) {
printf(“Queue Overflow\n”);
return;
}
pq->arr[pq->size].data = data;
pq->arr[pq->size].priority = priority;
pq->size++;

// Sort the array based on priority (higher priority first)
for (int i = pq->size – 1; i > 0; i–) {
if (pq->arr[i].priority > pq->arr[i – 1].priority) {
Node temp = pq->arr[i];
pq->arr[i] = pq->arr[i – 1];
pq->arr[i – 1] = temp;
} else {
break;
}
}
}

Node remove(PriorityQueue* pq) {
if (pq->size == 0) {
printf(“Queue Underflow\n”);
return (Node){-1, ‘\0’}; // Return an invalid node
}
return pq->arr[–pq->size]; // Remove the highest priority node
}

Write a program to implement linear and circular queue operations

Here’s a comprehensive implementation of both Linear Queue and Circular Queue operations in C. This program includes functions for enqueueing and dequeueing elements, along with basic menu-driven user interaction for testing these operations.

Linear Queue Implementation

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

#define MAX 5

typedef struct {
int items[MAX];
int front;
int rear;
} LinearQueue;

// Function to initialize the queue
void initLinearQueue(LinearQueue* q) {
q->front = -1;
q->rear = -1;
}

// Function to check if the linear queue is empty
int isLinearEmpty(LinearQueue* q) {
return q->front == -1;
}

// Function to check if the linear queue is full
int isLinearFull(LinearQueue* q) {
return q->rear == MAX – 1;
}

// Function to enqueue an element into the linear queue
void linearEnqueue(LinearQueue* q, int value) {
if (isLinearFull(q)) {
printf(“Linear Queue Overflow\n”);
return;
}
if (isLinearEmpty(q)) {
q->front = 0; // First element
}
q->items[++q->rear] = value; // Increment rear and add element
printf(“%d enqueued to Linear Queue\n”, value);
}

// Function to dequeue an element from the linear queue
int linearDequeue(LinearQueue* q) {
if (isLinearEmpty(q)) {
printf(“Linear Queue Underflow\n”);
return -1; // Return an error value
}
int value = q->items[q->front++];
if (q->front > q->rear) {
// Reset queue if it becomes empty
q->front = q->rear = -1;
}
printf(“%d dequeued from Linear Queue\n”, value);
return value;
}

// Function to display the linear queue
void displayLinearQueue(LinearQueue* q) {
if (isLinearEmpty(q)) {
printf(“Linear Queue is empty\n”);
return;
}
printf(“Linear Queue: “);
for (int i = q->front; i <= q->rear; i++) {
printf(“%d “, q->items[i]);
}
printf(“\n”);
}

 

Circular Queue Implementation

typedef struct {
int items[MAX];
int front;
int rear;
} CircularQueue;

// Function to initialize the circular queue
void initCircularQueue(CircularQueue* q) {
q->front = -1;
q->rear = -1;
}

// Function to check if the circular queue is empty
int isCircularEmpty(CircularQueue* q) {
return q->front == -1;
}

// Function to check if the circular queue is full
int isCircularFull(CircularQueue* q) {
return (q->rear + 1) % MAX == q->front;
}

// Function to enqueue an element into the circular queue
void circularEnqueue(CircularQueue* q, int value) {
if (isCircularFull(q)) {
printf(“Circular Queue Overflow\n”);
return;
}
if (isCircularEmpty(q)) {
q->front = 0; // First element
}
q->rear = (q->rear + 1) % MAX; // Circular increment
q->items[q->rear] = value; // Add element
printf(“%d enqueued to Circular Queue\n”, value);
}

// Function to dequeue an element from the circular queue
int circularDequeue(CircularQueue* q) {
if (isCircularEmpty(q)) {
printf(“Circular Queue Underflow\n”);
return -1; // Return an error value
}
int value = q->items[q->front];
if (q->front == q->rear) {
// Reset queue if it becomes empty
q->front = q->rear = -1;
} else {
q->front = (q->front + 1) % MAX; // Circular increment
}
printf(“%d dequeued from Circular Queue\n”, value);
return value;
}

// Function to display the circular queue
void displayCircularQueue(CircularQueue* q) {
if (isCircularEmpty(q)) {
printf(“Circular Queue is empty\n”);
return;
}
printf(“Circular Queue: “);
int i = q->front;
while (1) {
printf(“%d “, q->items[i]);
if (i == q->rear) {
break;
}
i = (i + 1) % MAX; // Circular increment
}
printf(“\n”);
}

Main Program to Test the Queues

int main() {
LinearQueue linearQueue;
CircularQueue circularQueue;
initLinearQueue(&linearQueue);
initCircularQueue(&circularQueue);

int choice, value;

while (1) {
printf(“\n1. Linear Queue Operations\n”);
printf(“2. Circular Queue Operations\n”);
printf(“3. Exit\n”);
printf(“Enter your choice: “);
scanf(“%d”, &choice);

switch (choice) {
case 1: // Linear Queue
printf(“\nLinear Queue Menu:\n”);
printf(“1. Enqueue\n”);
printf(“2. Dequeue\n”);
printf(“3. Display\n”);
printf(“Enter your choice: “);
scanf(“%d”, &choice);
if (choice == 1) {
printf(“Enter value to enqueue: “);
scanf(“%d”, &value);
linearEnqueue(&linearQueue, value);
} else if (choice == 2) {
linearDequeue(&linearQueue);
} else if (choice == 3) {
displayLinearQueue(&linearQueue);
}
break;

case 2: // Circular Queue
printf(“\nCircular Queue Menu:\n”);
printf(“1. Enqueue\n”);
printf(“2. Dequeue\n”);
printf(“3. Display\n”);
printf(“Enter your choice: “);
scanf(“%d”, &choice);
if (choice == 1) {
printf(“Enter value to enqueue: “);
scanf(“%d”, &value);
circularEnqueue(&circularQueue, value);
} else if (choice == 2) {
circularDequeue(&circularQueue);
} else if (choice == 3) {
displayCircularQueue(&circularQueue);
}
break;

case 3:
exit(0);

default:
printf(“Invalid choice. Please try again.\n”);
}
}

return 0;
}

Explanation of the Code

  1. Linear Queue Implementation:
    • Defined using a structure that holds the queue items, front, and rear indices.
    • Provides functions for initialization, checking empty/full conditions, enqueueing, dequeuing, and displaying the queue.
  2. Circular Queue Implementation:
    • Similar to the linear queue but includes logic to wrap around the array using modular arithmetic.
    • The same functions as the linear queue are implemented for circular operations.
  3. Main Function:
    • Contains a menu-driven interface to test both linear and circular queue operations.
    • Allows the user to enqueue, dequeue, and display the contents of the queues.

How to Compile and Run

  1. Copy the complete code into a .c file (e.g., queues.c).
  2. Open a terminal and navigate to the directory containing the file.
  3. Compile the program using:
    gcc queues.c -o queues
  4. Run the program with:
    . /queues

This implementation will allow you to interactively test both linear and circular queue operations.

 

Previous Chapter Next Chapter
Important Questions
Comments
Discussion
0 Comments
  Loading . . .