Queue

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle, which means that the first element added to the queue is the first one to be removed. Queues are commonly used in computer science and programming for various applications, such as scheduling tasks, managing resources, and more.

1. Definition:
  • A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. This means that the element added first is the one to be removed first.
  • Queues are used to manage data in a way that ensures orderly processing. Elements are added to the rear (enqueue) and removed from the front (dequeue) of the queue.
2. Basic Queue Operations:
  • Enqueue (Insertion): Adding an element to the rear of the queue.
  • Dequeue (Deletion): Removing an element from the front of the queue.
  • Peek: Viewing the element at the front of the queue without removing it.
  • IsEmpty: Checking if the queue is empty.
  • IsFull: Checking if the queue is full (in the context of a fixed-size queue).
  • Size: Getting the current number of elements in the queue.
3. Use Cases:
Queues are used in various real-world scenarios, including:

Task scheduling in operating systems.
Print job management in printers.
Breadth-First Search (BFS) in graph algorithms.
Handling requests in web servers.
Managing resources in concurrent programming.

4. Types of Queues:
Priority Queue: Elements have associated priorities, and higher-priority elements are dequeued before lower-priority ones.
Circular Queue (or Ring Buffer): A queue implemented in a circular manner, where the front and rear wrap around to the beginning when they reach the end of the queue.

5. Time Complexity:
Enqueue: O(1)
Dequeue: O(1)
Peek: O(1)
IsEmpty: O(1)
Size: O(1)

6. Implementation Variations:
Queues can be implemented using arrays, linked lists, or other data structures depending on specific requirements.

In summary, a queue is a fundamental data structure that plays a crucial role in managing data in a first-come-first-served manner. It is used in various applications across computer science and programming and is characterized by its simple yet essential operations and FIFO behavior.

Algorithms for various queue operations

InitializeQueue():
    front = 0
     rear = -1

1. Enqueue (Insertion):

Algorithm Enqueue(queue, item):
Input: queue (an array-based queue), item (element to be inserted)
Output: None

1. If the queue is full (rear == max_size - 1), return an error (overflow).
2. Increment rear by 1.
3. Set queue[rear] to the item.

2. Dequeue (Deletion):

Algorithm Dequeue(queue):
Input: queue (an array-based queue)
Output: dequeuedItem (element removed from the front of the queue)

1. If the queue is empty (front > rear), return an error (underflow).
2. Retrieve the element at queue[front].
3. Increment front by 1.
4. Return the dequeuedItem.

3. Peek:

Algorithm Peek(queue): 
Input: queue (an array-based queue) 
Output: frontItem (element at the front of the queue) 
1. If the queue is empty (front > rear), return an error (empty queue). 
2. Retrieve the element at queue[front]. 
3. Return frontItem without removing it.

4. IsEmpty:

Algorithm IsEmpty(queue):
Input: queue (an array-based queue)
Output: isEmpty (boolean indicating whether the queue is empty)

1. If front > rear, set isEmpty to True (queue is empty).
2. Otherwise, set isEmpty to False (queue is not empty).

5. Size:

Algorithm Size(queue):
Input: queue (an array-based queue)
Output: size (number of elements in the queue)

1. Set size to (rear - front + 1) if the queue is not empty.
2. Set size to 0 if the queue is empty.

These algorithms describe the basic operations on a queue implemented using an array. Ensure that you handle underflow (dequeue from an empty queue) and overflow (enqueue when the queue is full) appropriately in your code, as described in the enqueue and dequeue algorithms.

Note; if  rear<front and front !=0, we can initialize the queue to make use of the space.





C program - Queue Implementation
/*******************************************************************************/
#include <stdio.h>
#include<stdlib.h>
#include <stdbool.h>
#define MAX 5
// initilazing queue
int queue[MAX];
int rear = - 1;
int front = 0;
// Function to check if the queue is empty
bool isEmpty() {
    return rear <front ;
}

// Function to check if the queue is full
bool isFull() {
    return rear == MAX - 1;
}

void insert() // enqueue
{
int item;
if (isFull())
  printf("Queue Overflow \n");
else
 {
 printf("\nInset the element in queue : ");
 scanf("%d", &item);
 rear = rear + 1;
 queue[rear] = item;
 }
} /*End of insert()*/
void delete() //dequeue
{
if (isEmpty() )
    {
    printf("\nQueue Underflow \n");
    return ;
    }
    else
    {
    printf("\nElement deleted from queue is : %d\n", queue[front]);
    front = front + 1;
}
} /*End of delete() */
void display()// print queue
{
int i;
    if (isEmpty() )
        printf("\nQueue is empty \n");
    else
    {
        printf("\nQueue is : ");
        for (i = front; i <= rear; i++)
            printf("%d ", queue[i]);
        printf("\n");
    }
}
// Function to peek at the front item
int peek() {
    if (isEmpty()) {
        printf("Queue is empty. Nothing to peek.\n");
        return -1; // Error value
    } else {
        return queue[front];
    }
}
// Function to get the size of the queue
int size() {
    if (isEmpty()) {
        return 0;
    } else {
        return rear - front + 1;
    }
}
int main()
{
int choice;
while (1)
{
printf("\n1.Insert element to queue \n");
printf("2.Delete element from queue \n");
printf("3.Display all elements of queue \n");
printf("4.Peek \n");
printf("5.Size of the queue\n");
printf("6.Quit \n");
printf("\nEnter your choice : ");
scanf("%d", &choice);
switch (choice)
{
case 1:
    insert();
    break;
case 2:
    delete();
    break;
case 3:
    display();
    break;
case 4:
    int x=peek();
    if(x!=-1) printf("\nfront element is=%d\n",x);
    break;
case 5:
    printf("\nsize of the queue is =%d\n",size());
    break;
case 6:
    exit(1);

default:

printf("\nWrong choice \n");

} /*End of switch*/

} /*End of while*/
return 0;
} /*End of main()*/


/**** a memory efficient implementation where elements are shifted left after deletion *********/
#include <stdio.h>
#include<stdlib.h>
#include <stdbool.h>
#define MAX 5
// initilazing queue
int queue[MAX];
int rear = - 1;
int front = 0;
// Function to check if the queue is empty
bool isEmpty() {
    return rear ==-1 ;
}

// Function to check if the queue is full
bool isFull() {
    return rear == MAX - 1;
}

void insert() // enqueue
{
int item;
if (isFull())
  printf("Queue Overflow \n");
else
 {
 printf("\nInset the element in queue : ");
 scanf("%d", &item);
 rear = rear + 1;
 queue[rear] = item;
 }
} /*End of insert()*/
void shift() // shifting elements to the left
{
    
  int i;
  for (i=front;i<=rear-1;i++)
   queue[i]=queue[i+1];

}
void delete() //dequeue
{
if (isEmpty() )
    {
    printf("\nQueue Underflow \n");
    return ;
    }
    else
    {
    printf("\nElement deleted from queue is : %d\n", queue[front]);
    shift();
    rear=rear-1;
    }
} /*End of delete() */
void display()// print queue
{
int i;
    if (isEmpty() )
        printf("\nQueue is empty \n");
    else
    {
        printf("\nQueue is : ");
        for (i = front; i <= rear; i++)
            printf("%d ", queue[i]);
        printf("\n");
    }
}


int main()
{
int choice;
while (1)
{
printf("\n1.Insert element to queue \n");
printf("2.Delete element from queue \n");
printf("3.Display all elements of queue \n");
printf("4.Quit \n");
printf("\nEnter your choice : ");
scanf("%d", &choice);
switch (choice)
{
case 1:
    insert();
    break;
case 2:
    delete();
    break;
case 3:
    display();
    break;
case 4:
    exit(1);

default:

printf("\nWrong choice \n");

} /*End of switch*/

} /*End of while*/
return 0;
} /*End of main()*/

Comments

Post a Comment

Popular posts from this blog

Data Structures CST 201 KTU Third Semester Syllabus Notes and Solved Questions- Dr Binu V P 984739060

Dr BinuV P -About Me About The Course Syllabus Data Structures Lab CSL 201 ( Do the Programs to Understand the Concept Well) Model Question Paper CST 201 Data Structures University Question Papers CST 201 Data Structures Module-1 Basic Concepts of Data Structures 1.1 System Life Cycle 1.2 Algorithms , Performance Analysis  1.3 Space Complexity, Time Complexity  1.4 Asymptotic Analysis and Notations  1.5 Complexity Calculation of Simple Algorithms Module-2 Arrays and Searching  2.1 Polynomial representation using Arrays  2.2 Sparse matrix  2.3 Stacks  2.4 Queues 2.5 Circular Queues  2.6 Priority Queues 2.7 Double Ended Queues 2.8 Infix to  Postfix Conversion  2.9  Evaluation of Postfix Expression 2.10 Linear Search  2.11 Binary Search Module-3 Linked List and Memory Management 3.1 Linked List -Self Referential Structures  3.2 Dynamic Memory Allocation  3.3 Singly Linked List-Operations on Linked List 3.4 Doubly Linked List 3.5 Circular Linked List  3.6 Stack using Linked List  3.7 Queue
Read more

Binary Search Tree ( BST) and operations

Image
A binary search tree (BST) is a data structure that organizes elements in a hierarchical structure, allowing for efficient search, insertion, and deletion operations. Here are the key properties and operations associated with a binary search tree: Properties of a Binary Search Tree: Binary Tree Structure:      Each node in the tree has at most two children: a left child and a right child.      The left subtree of a node contains only nodes with values less than the node's value.      The right subtree of a node contains only nodes with values greater than the node's value. Ordering Property:      For any node n , all nodes in its left subtree have values less than n, and all nodes in its right subtree           have values greater than n . No Duplicates:     A binary search tree does not allow duplicate values. Example: Figure  shows a binary search tree. Notice that this tree is obtained by inserting the values 13, 3, 4, 12, 14, 10, 5, 1, 8, 2, 7, 9, 11, 6, 18 in that order,
Read more

Depth First Search DFS

Image
Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. It's often used to explore and analyze the connectivity of graphs, find paths, and solve problems related to connected components. Algorithm: The DFS algorithm operates on a graph, starting from an initial vertex. It maintains a stack (or uses recursion) to keep track of the vertices to visit. Initialization: Create a boolean array to mark visited vertices. Initialize all vertices as not visited. DFS Function: Choose a starting vertex (if the graph is disconnected, this process is repeated for unvisited vertices). Mark the chosen vertex as visited. Explore the chosen vertex's neighbours: If a neighbour is not visited, recursively call the DFS function on that neighbour. Repeat until all reachable vertices are visited. Here's a simplified recursive implementation in pseudocode: procedure DFS(vertex): mark vertex as visited for ea
Read more