Queues:

A queue is a data structure or a collection of items where elements are added at one end (called the rear or tail) and removed from the other end (called the front or head). It 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.

Application:

1. Task Scheduling (CPU Scheduling)

• Operating systems use queues to manage processes. When multiple tasks are waiting for the CPU, a scheduling algorithm uses a queue to determine which task gets the CPU time next. For example, in Round-Robin Scheduling, tasks are placed in a queue and are processed one by one.


2. Print Queue

• When multiple print jobs are sent to a printer, they are stored in a queue and printed in the order they were received. This ensures that print jobs are handled fairly and sequentially.


3. Call Centers (Customer Service)

• In customer service systems, calls are placed in a queue and are attended to in the order they arrive. This helps ensure that no customer is skipped, and the first one to call gets served first.


4. Breadth-First Search (BFS) in Graphs

• In BFS, nodes of a graph are explored level by level, and the nodes to be visited next are stored in a queue. This algorithm is widely used in various applications like f inding the shortest path in unweighted graphs, social network analysis, and web crawling.


5. Data Buffers

• Queues are used in buffers, especially in I/O (Input/Output) operations. For example, a queue is used in the keyboard buffer to store key presses until they are processed by the computer.


6. Networking (Packet Handling)

• In routers and switches, queues manage incoming and outgoing network packets. These packets are queued up and processed in the order they arrive, ensuring fair and efficient delivery.


7. Asynchronous Task Management

• In many programming frameworks, background tasks like sending emails, processing payments, or generating reports are placed in a queue for asynchronous execution. Systems like message queues (e.g., RabbitMQ, Kafka) handle distributed tasks and communication between different services.


8. Simulation Systems

• In simulations of real-world systems (like traffic management, airport runways, or supermarket checkouts), queues are used to model the behavior of entities waiting for resources, helping to understand delays, bottlenecks, and efficiency.


9. Operating Systems (I/O Queuing)

• Operating systems use queues to manage the input/output (I/O) requests for devices like hard drives. The requests are queued up and processed sequentially, or based on priority, depending on the system.


10. CPU Instruction Pipelines

• In modern CPUs, instructions are queued in a pipeline, where they are executed one by one in the order they were received, ensuring smooth and efficient processing of tasks.


11. Shared Resources Management

• In distributed systems, queues are used to manage access to shared resources. For instance, multiple processes may need to access a database, and a queue ensures that the requests are processed in order.


12. Multithreading

• In multithreaded applications, a queue is often used to manage tasks between producer and consumer threads, where one thread produces data and another consumes it. This model ensures proper synchronization between threads.


13. Real-time Systems

• In real-time systems (e.g., emergency systems, robotics), queues help ensure that tasks are processed in the correct order and within the required time frame, prioritizing tasks as needed.


These applications demonstrate the versatility and importance of queues in solving real world problems where managing sequential tasks is essential.

Array Representation:

A queue can be implemented using an array by maintaining two pointers: one for the front (where elements are removed) and one for the rear (where elements are added). This approach ensures that the First In, First Out (FIFO) principle is followed.


Key Operations


1. Enqueue (Insertion): Add an element at the rear of the queue.


2. Dequeue (Deletion): Remove an element from the front of the queue.


3. Peek (Front): View the front element without removing it.


4. isEmpty: Check if the queue is empty.


5. isFull: Check if the queue is full (in case of a fixed size).


Basic Structure


// Define the size of the queue

#define MAX 5

// Initialize an empty queue

int queue[MAX];

int front = -1;

int rear = -1;


Queue Operations Using an Array


1. Enqueue Operation To add an element at the rear:

• If the queue is empty, set both front and rear to 0.

• If the queue is not full, increment the rear and add the element.

• If the queue is full, report an overflow condition.


void enqueue(int value) {

if (rear == MAX - 1) {

printf("Queue Overflow\n");

return;

}

if (front == -1) {

front = 0; // Initialize front if queue was empty

}

rear++;

queue[rear] = value;

printf("%d added to queue\n", value);

}


2. Dequeue Operation


To remove an element from the front:

• If the queue is empty, report an underflow condition.

• If there's only one element, reset both front and rear to -1 (queue becomes empty).

• Otherwise, increment the front pointer to remove the element.


int dequeue() {

if (front == -1) {

printf("Queue Underflow\n");

return -1;

}

int value = queue[front];

if (front == rear) {

// If only one element was in the queue

front = rear = -1;

} else {

front++;

}

printf("%d removed from queue\n", value);

return value;

}


3. Peek Operation


To view the front element without removing it:

int peek() {

if (front == -1) {

printf("Queue is Empty\n");

return -1;

}

return queue[front];

}


4. isEmpty Operation


To check if the queue is empty:

int isEmpty() {

return (front == -1);

}


5. isFull Operation


To check if the queue is full:

int isFull() {

return (rear == MAX - 1);

}


Example Scenario


Consider enqueuing the elements 10, 20, 30, and dequeuing them in sequence:


enqueue(10); // Queue: [10]

enqueue(20); // Queue: [10, 20]

enqueue(30); // Queue: [10, 20, 30]


dequeue(); // Removes 10, Queue: [20, 30]

dequeue(); // Removes 20, Queue: [30]


peek(); // Returns 30 without removing


Limitations


1. Fixed Size: The size of the queue is limited by the size of the array (MAX). Once it is full, no more elements can be enqueued.


2. Wastage of Space: After multiple dequeues, even if there is space left in the array, the queue might still be considered full if elements are added only at the end. This issue can be resolved by using a circular queue.

Linked representation

A queue can also be implemented using a linked list, which allows for dynamic memory allocation, meaning that the queue can grow or shrink as needed without a fixed size limitation. In this implementation, each element (node) in the queue contains data and a reference (or pointer) to the next node in the queue.


Structure of a Node


Each node in the linked list contains:


1. Data: The value stored in the node.

2. Next: A pointer to the next node in the queue.


Queue Using Linked List


In a linked list implementation of a queue, we maintain two pointers:


• Front: Points to the first node in the queue (where elements are dequeued).

• Rear: Points to the last node in the queue (where elements are enqueued).


Key Operations


1. Enqueue (Insertion): Add a new node at the rear of the queue.

2. Dequeue (Deletion): Remove a node from the front of the queue.

3. Peek (Front): View the front element without removing it.

4. isEmpty: Check if the queue is empty.


Structure Definitions


#include

#include


// Define the structure for a node

struct Node {

int data;

struct Node* next;

};

// Define the structure for a queue

struct Queue {

struct Node *front, *rear;

};


// Function to create a new node

struct Node* newNode(int value) {

struct Node* temp = (struct Node*)malloc(sizeof(struct Node));

temp->data = value;

temp->next = NULL;

return temp;

}


// Function to create an empty queue

struct Queue* createQueue() {

struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));

q->front = q->rear = NULL;

return q;

}


Queue Operations


1. Enqueue Operation


To add an element at the rear:


• Create a new node.

• If the queue is empty, both front and rear point to the new node.

• If not, link the new node to the current rear and update the rear pointer.


void enqueue(struct Queue* q, int value) {

struct Node* temp = newNode(value);

if (q->rear == NULL) {

q->front = q->rear = temp; // Queue was empty

printf("%d added to queue\n", value);

return;

}

q->rear->next = temp;

q->rear = temp;

printf("%d added to queue\n", value);

}


2. Dequeue Operation


To remove an element from the front:


• If the queue is empty, print underflow.

• If only one element is in the queue, update both front and rear to NULL.

• Otherwise, move the front pointer to the next node and free the previous node.


3. Peek Operation


To view the front element without removing it:

int peek(struct Queue* q) {

if (q->front == NULL) {

printf("Queue is Empty\n");

return -1;

}


return q->front->data;

}


4. isEmpty Operation


To check if the queue is empty:

int isEmpty(struct Queue* q) {

return (q->front == NULL);

}


Advantages of Linked List Queue


• Dynamic Size: No fixed limit on the number of elements, as nodes are dynamically allocated.

• Efficient Memory Usage: Memory is allocated only when necessary, unlike array implementations where unused space can be wasted.

• No Wastage: There’s no need to shift elements (like in array implementations).


Disadvantages


• Extra Memory: Each node requires extra memory for the pointer (next reference).

• Slower Access: Linked list traversal can be slower compared to arrays due to non contiguous memory allocation.


This implementation provides an efficient way to handle queues when the size is not known beforehand or when the queue needs to dynamically grow or shrink.

Types of Queues:

In data structures, a queue is a linear structure that follows the First In, First Out (FIFO) principle, meaning the first element added to the queue is the first one to be removed.


1. Simple Queue (Linear Queue)


• Structure: The basic form of a queue where insertion occurs at the rear (end) and removal occurs from the front.


• Operations:


o Enqueue: Adds an element to the rear of the queue.

o Dequeue: Removes an element from the front of the queue.


• Limitation: When elements are dequeued, the front of the queue moves forward, and over time, the available space may not be reused, leading to inefficient memory usage.


Example:


Queue: [10, 20, 30, 40]

Front -> 10

Rear -> 40


2. Circular Queue


• Structure: In a circular queue, the last position is connected back to the first position, forming a circle. This helps in overcoming the limitations of a linear queue by reusing the space when elements are dequeued.


• Operations:


o Enqueue: Adds an element to the rear, and when the rear reaches the end, it wraps around to the front if space is available.

o Dequeue: Removes an element from the front, and the front moves forward in a circular manner.


• Advantage: Efficient use of space, as the queue can wrap around when it becomes full.


Example:


Circular Queue: [30, 40, _, _, 10, 20]

Front -> 10

ear -> 40


3. Priority Queue


• Structure: In a priority queue, each element has a priority level associated with it. Elements are dequeued based on their priority rather than their position in the queue. If two elements have the same priority, they are dequeued based on their order of arrival.


• Operations:


o Enqueue: Adds an element along with its priority.

o Dequeue: Removes the element with the highest priority (or lowest depending on the convention).


• Applications: Used in scenarios where certain tasks need to be executed before others, such as in scheduling algorithms or network packet management.


Example:


Priority Queue: [(5, Task A), (2, Task B), (3, Task C)]

equeued -> Task B (priority 2)


4. Double-Ended Queue (Deque)


• Structure: A double-ended queue allows insertion and deletion of elements from both ends: the front and the rear.


• Types:


o Input-Restricted Deque: Insertion is allowed at only one end, but deletion is allowed at both ends.

o Output-Restricted Deque: Deletion is allowed at only one end, but insertion is allowed at both ends.


• Operations:

o Enqueue Front: Adds an element to the front.

o Enqueue Rear: Adds an element to the rear.

o Dequeue Front: Removes an element from the front.

o Dequeue Rear: Removes an element from the rear.


• Applications: Useful in applications like the "sliding window" problem or for implementing both stacks and queues using the same data structure.


Example:


Deque: [Front] 10 <-> 20 <-> 30 <-> 40 [Rear]


5. Circular Deque


• Structure: A variation of the deque where the ends (front and rear) are connected in a circular manner. This allows both efficient use of space and the ability to insert and delete from both ends.

• Operations: Same as Deque but with circular behaviour.


Example:


Circular Deque: [30, 40, _, _, 10, 20]

Front -> 10

Rear -> 40


6. Double-Ended Priority Queue (DEPQ)


• Structure: A special type of priority queue where elements can be inserted or removed from both ends based on priority. It allows access to both the highest and lowest priorities. •


Operations:

o Insert: Add an element with priority.

o Remove Highest Priority: Removes the element with the highest priority.

o Remove Lowest Priority: Removes the element with the lowest priority.


Example:


DEPQ: [(1, Task A), (5, Task B), (3, Task C)]

Highest -> Task B (priority 5)

Lowest -> Task A (priority 1)


7. Concurrent Queue (Thread-Safe Queue)


• Structure: A queue designed for concurrent access in multi-threaded environments. This type of queue ensures that multiple threads can enqueue and dequeue items safely without causing race conditions or corrupting the data structure.

• Operations: Supports thread-safe versions of enqueue and dequeue, often using locks or atomic operations.

• Applications: Used in parallel processing, multithreading, and producer-consumer problems.


Example:


Used in concurrent programming libraries like Java's concurrentLinkedQueue or Python's queue.Queue.


Conclusion


Each type of queue serves different purposes based on the application requirements, such as efficient memory use, priority-based processing, or thread-safe operations. Understanding the strengths and limitations of each helps in selecting the appropriate queue for a given problem.

Priority Queue in detail:

A Priority Queue is a specialized type of queue in which each element is associated with a priority, and elements are dequeued based on their priority rather than the order in which they were enqueued. It is commonly used in algorithms like Dijkstra's Shortest Path and Huffman Coding and in various real-time systems like operating system scheduling, task management, and simulations.


In a priority queue, higher-priority elements are dequeued before lower-priority elements. In case two elements have the same priority, they are processed according to their order of arrival (FIFO within priorities).


Types of Priority Queues


1. Max-Priority Queue: The element with the highest priority is dequeued first.

2. Min-Priority Queue: The element with the lowest priority is dequeued first.


Priority Queue Operations


Here are the main operations supported by a priority queue:


1. Insert (Enqueue): Insert an element with a priority into the queue.

2. Delete (Dequeue): Remove the element with the highest (or lowest) priority.

3. Peek: Return the element with the highest (or lowest) priority without removing it.

4. Change Priority: Modify the priority of a given element.


Priority Queue Implementations

A priority queue can be implemented using various data structures, each with different performance characteristics.


1. Using Arrays


• Insert: Add the element at the end of the array. The time complexity is O(1)O(1)O(1).

• Delete (Dequeue): To find the element with the highest/lowest priority, scan the array and remove that element. The time complexity is O(n)O(n)O(n), where nnn is the number of elements.


• Advantages: Simple and straightforward.

• Disadvantages: Inefficient for large data sets due to linear-time deletion.


2. Using Linked Lists


• Unsorted Linked List:

o Insert: Add the element at the front or the rear (constant-time operation, O(1)O(1)O(1)).

o Delete: Search the entire list to find and remove the element with the highest/lowest priority (linear-time operation, O(n)O(n)O(n)).


• Sorted Linked List: o Insert: Traverse the list to insert the element at the correct position (linear t ime operation, O(n)O(n)O(n)).

o Delete: Remove the element at the front (constant-time operation, O(1)O(1)O(1)).


• Advantages: Efficient deletion with sorted lists.

• Disadvantages: Insertion becomes inefficient for large lists when sorted.


3. Using Heaps (Binary Heap)


The most efficient way to implement a priority queue is with a binary heap, which is a complete binary tree that satisfies the heap property:


• Max-Heap: Every parent node has a value greater than or equal to its children.

• Min-Heap: Every parent node has a value less than or equal to its children.

• Insert: Add the element at the end of the heap and "bubble up" (heapify-up) to maintain the heap property. The time complexity is O(log⁡n)O(\log n)O(logn).

• Delete (Dequeue): Remove the root (highest or lowest priority), replace it with the last element, and "bubble down" (heapify-down) to maintain the heap property. The t ime complexity is O(log⁡n)O(\log n)O(logn).

• Peek: Return the root element (highest or lowest priority) in O(1)O(1)O(1).


• Advantages: Very efficient insertion and deletion.

• Disadvantages: Requires more complex algorithms for heap maintenance.


4. Using Balanced Binary Search Trees (BST)


• Insert: Insert an element into the tree maintaining the order based on priority (time complexity O(log⁡n)O(\log n)O(logn)).

• Delete: Remove the node with the highest/lowest priority (time complexity O(log⁡n)O(\log n)O(logn)).


• Advantages: More flexibility with tree structures like AVL trees or Red-Black trees for maintaining balanced order.

• Disadvantages: More overhead in managing balanced trees compared to heaps.


Applications of Priority Queue


1. Operating System Scheduling: Process scheduling based on priorities.

2. Graph Algorithms: Used in algorithms like Dijkstra’s shortest path, Prim’s minimum spanning tree.

3. Event Simulation: Managing events based on the time they are supposed to occur.

4. Job Scheduling in Print Spoolers: Jobs are executed in priority order.

5. Data Compression (Huffman Coding): Used to build Huffman Trees.

Introduction to Data Structure

Array

Overview

Operations

Array representation

Array the Abstract Data Type

Linked list

Types of linked list

Searching in array and linked list

Searching in an Array

Searching in a Linked List

Linear data structure

Linked representation of linear list

Array representation of linear list

Objects and structure in linear DS

Linear list representation in array and vector

Multiple list in a single array

Multiple list in single array

Matrices

Types of matrices

Special matrices

Stack

Stack application

Array representation

Linked representation

Queue

Queue application

Array representation

Linked representation

Types of queue

Priority queue

Sorting

Internal sorting

External sorting

Graph

Representation of graph

Graph implementation

Graph transversal

Application of graph transversal

Min. cost spanning trees

Shortest path pro

All pair shortest paths

Indexing

Indexed binary research trees

Indexed sequential access method

m- way search trees

B trees of order m

Height of a b- tree

Searching a b tree

Inserting into a b- tree

Deletion from a b- tree

Node structure

Hashing function

Collision resolution

Rehashing

Extensible hashing

Trees

Binary and other trees

Binary trees

Properties of binary trees

Representation of binary trees

Common binary trees operations

Binary trees transversal

ADT for binary trees

Class of linked binary trees

Binary search trees

ADT in binary search trees

Operations and implementation

Balanced search trees

Avl trees

Previous

Next