Data Structures using C

Introduction to Queue

A Queue is a linear data structure that follows the First In First Out (FIFO) principle. The element inserted first into the queue is removed first.

• Follows First In First Out (FIFO)
• Insertion occurs at REAR
• Deletion occurs at FRONT
• Processes elements in arrival order

Characteristics of Queue

• Follows FIFO principle
• Insertion takes place at REAR
• Deletion takes place at FRONT
• Can be implemented using arrays or linked lists
• Efficient for scheduling operations

Components of Queue

• FRONT → Points to first element
• REAR → Points to last element
• Queue Array/Nodes → Stores elements
• Size → Maximum queue capacity

Queue Representation

 FRONT                       REAR
   ↓                           ↓
 [10] → [20] → [30] → [40] → [50]

The FRONT pointer indicates the element to be removed, while the REAR pointer indicates where new elements are inserted.

Need for Queue

Queues are useful when elements need to be processed in the same order in which they arrive.

• CPU scheduling
• Task management systems
• Printer scheduling
• Request processing

Types of Queues

Queues are classified into different types based on how insertion and deletion operations are performed. Each type is designed for specific requirements and applications.

1. Simple Queue

A Simple Queue follows the FIFO (First In First Out) principle. Elements are inserted from the REAR and removed from the FRONT.

FRONT                REAR
 ↓                    ↓
[10] → [20] → [30] → [40]

Characteristics

• Insertion occurs at REAR
• Deletion occurs at FRONT
• Follows FIFO principle

Applications

• Printer scheduling
• Ticket booking systems
• CPU task scheduling

2. Circular Queue

Circular Queue is an improved version of a simple queue. The last position connects back to the first position, allowing efficient memory utilization.

      FRONT
         ↓
 [10][20][30][40]
   ↑            ↓
   └────REAR────┘

Advantages

• Reduces memory wastage
• Prevents false overflow
• Reuses empty spaces

Applications

• CPU scheduling
• Circular buffers
• Traffic control systems

3. Priority Queue

In a Priority Queue, elements are processed according to their priority instead of arrival order.

Priority : 1  2  3
Queue    : A  B  C

Output : A → B → C

Characteristics

• Highest priority processed first
• Priority can be ascending or descending
• Does not strictly follow FIFO

Applications

• Operating system scheduling
• Dijkstra's shortest path algorithm
• Network routing

4. Double Ended Queue (Deque)

Deque (Double Ended Queue) allows insertion and deletion from both FRONT and REAR ends.

Insert ← [10][20][30][40] → Delete

Types of Deque

• Input Restricted Deque
• Output Restricted Deque

Applications

• Browser history management
• Sliding window problems
• Caching systems

Queue Operations

Different operations are performed to insert, remove, and access queue elements. The following examples demonstrate queue operations using array implementation for simplicity. The same operations can also be performed using linked lists, but the insertion and deletion logic differs internally.

Enqueue Operation

Enqueue inserts a new element at the REAR of the queue.

rear++;
queue[rear]=value;

Time Complexity: O(1)

Dequeue Operation

Dequeue removes an element from the FRONT of the queue.

front++;

Time Complexity: O(1)

Peek / Front Operation

Displays the front element without removing it.

printf("%d",queue[front]);

Time Complexity: O(1)

isEmpty()

Checks whether the queue contains elements.

if(front==-1 || front>rear)
 printf("Queue Empty");

Time Complexity: O(1)

isFull()

Checks whether the queue has reached maximum capacity.

if(rear==MAX-1)
 printf("Queue Full");

Time Complexity: O(1)

Operation Flow Example

The following example demonstrates how queue operations change the queue step by step while maintaining FIFO (First In First Out) order.

Initial Queue:

FRONT → 10 → 20 → 30 ← REAR


Step 1: Enqueue(40)

FRONT → 10 → 20 → 30 → 40 ← REAR


Step 2: Dequeue()

Removed Element: 10

FRONT → 20 → 30 → 40 ← REAR


Step 3: Peek()

Front Element: 20


Step 4: isEmpty()

False


Step 5: isFull()

False

This example shows that insertion always takes place at the REAR and deletion always occurs at the FRONT.

Overflow and Underflow

Overflow occurs when insertion is attempted into a full queue.

Underflow occurs when deletion is attempted from an empty queue.

if(rear==MAX-1)
    printf("Queue Overflow");

if(front==-1 || front>rear)
    printf("Queue Underflow");

Queue Implementation in C

Array Implementation

In array implementation, queue elements are stored in a fixed-size array using FRONT and REAR pointers.

#include<stdio.h>

int queue[5];
int front=-1;
int rear=-1;

void enqueue(int value){

 if(rear==4)
   printf("Overflow");

 else{

   if(front==-1)
      front=0;

   rear++;
   queue[rear]=value;
 }
}

void dequeue(){

 if(front==-1 || front>rear)
    printf("Underflow");

 else
    front++;
}

int peek(){
    if(front==-1 || front>rear)
        return -1;

    return queue[front];
}

int isEmpty(){
    if(front==-1 || front>rear)
        return 1;

    return 0;
}

int isFull(){
    if(rear==4)
        return 1;

    return 0;
}

The array implementation uses FRONT and REAR indices. Peek returns the front element, while isEmpty checks whether the queue contains elements. The isFull operation prevents overflow conditions.

Linked List Implementation

In linked list implementation, nodes are dynamically created and linked together to avoid fixed-size limitations.

• Enqueue → Insert node at REAR
• Dequeue → Remove node from FRONT
• Peek → Access FRONT node data
• isEmpty → Check whether FRONT is NULL

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

struct Node{
   int data;
   struct Node* next;
};

struct Node* front=NULL;
struct Node* rear=NULL;

void enqueue(int value){

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

 newNode->data=value;
 newNode->next=NULL;

 if(rear==NULL){

   front=rear=newNode;
 }

 else{

   rear->next=newNode;
   rear=newNode;
 }
}

void dequeue(){

 if(front==NULL)
   printf("Underflow");

 else{

   struct Node* temp=front;
   front=front->next;

   free(temp);

   if(front==NULL)
      rear=NULL;
 }
}
 
int peek(){
    if(front==NULL)
        return -1;

    return front->data;
}

int isEmpty(){
    if(front==NULL)
        return 1;

    return 0;
}

Unlike arrays, linked list queues are dynamic in size and generally become full only when system memory is exhausted.

Complexity Analysis (Array and Linked List Implementation)

Operation     Time Complexity

Enqueue         O(1)
Dequeue         O(1)
Peek            O(1)
isEmpty         O(1)
isFull          O(1)
Search          O(n)

The time complexity of most queue operations remains O(1) for both array and linked list implementations. However, arrays use fixed memory allocation, whereas linked lists allocate memory dynamically.

Comparison: Array vs Linked List Implementation

• Arrays use fixed memory size
• Linked Lists use dynamic memory allocation
• Arrays are easier to implement
• Linked Lists avoid fixed-size limitations
• Linked Lists require extra memory for pointers

Applications of Queue

• CPU scheduling
• Printer scheduling
• Task management systems
• Breadth First Search (BFS)
• Network packet handling
• Call center systems

Real Life Examples of Queue

• People standing in a ticket counter line
• Waiting queue at supermarkets
• Call center customer waiting systems
• Printer job scheduling
• Traffic signal vehicle processing

Practical Example using Queue

Queues are commonly used in printer scheduling. The first print request received is processed first.

Queue:

Enqueue Operations:

Insert Job A
Insert Job B
Insert Job C


Current Queue:

FRONT → A → B → C ← REAR


Step 1:

Dequeue Job A

Queue:
FRONT → B → C ← REAR


Step 2:

Enqueue Job D

Queue:
FRONT → B → C → D ← REAR


Step 3:

Dequeue Job B

Final Queue:
FRONT → C → D ← REAR

This example demonstrates FIFO behavior where the first print request inserted into the queue is processed first.

Advantages of Queue

• Maintains processing order
• Efficient scheduling mechanism
• Easy implementation
• Useful for resource sharing

Limitations of Queue

• Only FRONT element can be accessed directly
• Overflow and underflow may occur
• Searching takes linear time

Interview Questions

1. What is FIFO?

FIFO stands for First In First Out. The element inserted first is removed first.

Enqueue: 10 → 20 → 30

Dequeue removes: 10

2. What is the difference between Queue and Stack?

Queue follows FIFO whereas Stack follows LIFO.

Queue : FIFO (First In First Out)
Stack : LIFO (Last In First Out)

3. What causes Queue Overflow?

Queue Overflow occurs when insertion is attempted on a full queue.

4. Why is Queue used in CPU scheduling?

CPU scheduling uses queues because processes must be executed in the same order they arrive.

5. How can queues be implemented?

Queues can be implemented using:

• Arrays
• Linked Lists

6. Why is Circular Queue preferred over Simple Queue?

Circular Queue avoids memory wastage by reusing empty spaces created after deletion operations.