Queue using Array

 

What is a Queue?

A Queue is a linear data structure that follows the First In First Out (FIFO) principle.

• First In First Out (FIFO) means:
  ➔ The element added first will be removed first.

Think of a queue in a bank or queue at a ticket counter:

• The first person to enter the queue is the first to get served.

Basic Queue Operations:

Operation	Meaning
enqueue(x)	Add element x to the rear (end) of the queue.
dequeue()	Remove the front element from the queue.
peek()	View the element at the front without removing it.
isEmpty()	Check if the queue is empty.

Important Queue Terminologies

Term	Meaning
Front	Points to the first element in the queue.
Rear	Points to the last element in the queue.
Size	Total number of elements currently in the queue.

Algorithms for Basic Queue Operations

We assume:

• queue[MAX] is an array to hold queue elements.

• front and rear are integers.(-1 initially)

• MAX is the maximum size.

Algorithm for Enqueue (Insert element)

Algorithm ENQUEUE(item)

1. If rear == MAX - 1 then

       Output "Queue Overflow"

       Exit

2. Else 

       rear = rear + 1

       queue[rear] = item

4. End If

5. Return

Algorithm for Dequeue (Remove element)

Algorithm DEQUEUE()

1. If front ==  rear then

       Output "Queue Underflow"

       Exit

2. Else

       front = front + 1

       item = queue[front]

3. End If

4. Return item

Note: if front==rear we can also reset queue to utilize space

Algorithm for Peek (View Front Element)

Algorithm PEEK()

1. If front ==  rear then

       Output "Queue is Empty"

       Exit

2. Else

       item = queue[front+1]

3. End If

4. Return item

Algorithm for isEmpty (Check if queue is empty)

Algorithm isEmpty()

1. If front == rear then

       Return TRUE

2. Else

       Return FALSE

Important Points

• Queue Overflow occurs when trying to add to a full queue.

• Queue Underflow occurs when trying to remove from an empty queue.

• In linear queue, after a lot of enqueues and dequeues, space at the front is wasted.
  ➔ To solve this, we can use a circular queue 

🚀 Time Complexity of Queue Operations

Operation                            Description                                                    Time Complexity

Enqueue (Insert)                    Add an element at the rear of the queue                 O(1)

Dequeue (Remove)                Remove an element from the front of the queue   O(1)

Front / Peek                           Get the front element without removing it            O(1)

isEmpty                                 Check if the queue is empty                                  O(1)

isFull                                     Check if the queue is full                                       O(1)
(for fixed-size array queues)

🎯 5 Important Applications of Queues

1. Process Scheduling — Managing processes waiting for CPU time in operating systems.

2. Printer Queue Management — Handling multiple print jobs in order.

3. Handling Requests in Web Servers — Managing incoming client requests.

4. Breadth-First Search (BFS) — Exploring graphs level by level.

5. Network Packet Scheduling — Queuing data packets in routers before transmission.

C Program - queue using arrays

#include <stdio.h>

#include<stdlib.h>

#include <stdbool.h>

#define MAX 10

// initilazing queue

int queue[MAX];

int rear = - 1;

int front = -1;

// 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 enqueue() // 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 dequeue() //dequeue

{

if (isEmpty() )

    {

    printf("\nQueue Underflow \n");

    return ;

    }

    else

    {

    front = front + 1;

    printf("\nElement deleted from queue is : %d\n", queue[front]);

    }

} /*End of delete() ; if front==rear we also reset queue to utilize space*/

void display()// print queue

{

int i;

    if (isEmpty() )

        printf("\nQueue is empty \n");

    else

    {

        printf("\nQueue is : ");

        for (i = front+1; 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+1];

    }

}

// Function to get the size of the queue

int size() {

    if (isEmpty()) {

        return 0;

    } else {

        return rear - (front + 1)+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:

    enqueue();

    break;

case 2:

    dequeue();

    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()*/