Queue in Data Structure

What is a Queue?

A queue is a sequential data structure that follows the FIFO (First in Last Out) approach. 

A queue can be defined as an ordered list which enables insert operations to be performed at one end called Rear end delete operations to be performed at another end called Front. 

For example:-  people waiting in line for a rail ticket from a queue.


Representation of Queue in Memory:-

1. Static Implementation (Using Array):-

Static implementation of Queue is represented by arrays. If Queue is implemented using arrays, we must be sure about the exact number of elements we want to store in the queue, because we have to declare the size of the array at design time or before the processing starts.


  2. Dynamic implementation (Using Linked list):-

In a linked queue, each node of the queue consists of two parts i.e. data part and the link part. Each element of the queue points to its immediate next element in the memory. 

In the linked queue, there are two pointers maintained in the memory i.e. front pointer and rear pointer. The front pointer contains the address of the starting element of the queue while the rear pointer contains the address of the last element of the queue. 


Types of Queue:-

1. Linear Queue:-

• It is a linear data structure. 

• It is considered as sequence of items. It is a linear data structure. It is considered as sequence of items. FIFO (First In First Out) property. 

• It supports FIFO (First In First Out) 

• It has three components:

  •  A Container of items o A pointer front that points the first item of the queue. 
  •  A pointer rear that points the last item of the queue. 
  • Container of items that contains elements of queue. that points the first item of the queue. 
• Insertion is performed from that points the last item of the queue. performed from REAR end. • Deletion is performed from 
• Insertion operation is also known as Deletion is performed from FRONT end. Insertion            operation is also known as ENQUEUE in queue. Deletion operation is also known as               DEQUEUE in queue. 

Structure of Linear Queue:-

2. Circular Queue:-

• It is a linear data structure in which the last position is connected back to the first position to make a circle.

• It follows FIFO (First In First Out) principle.

• It overcomes the limitation of linear queue such as memory wastage.

• In circular queue, when the rear reaches the last position, it starts again from the beginning (if space is available).

• It has two pointers:

  • Front → points to the first element
  • Rear → points to the last element

• Insertion is performed from REAR end.

• Deletion is performed from FRONT end.

• Insertion operation is also known as ENQUEUE.

• Deletion operation is also known as DEQUEUE.

Advantages of Circular Queue:-
• Efficient use of memory
• No false overflow condition

Structure of Circular Queue:-


3. Priority Queue:-

• It is a special type of queue in which each element is associated with a priority.

• Elements are processed based on priority instead of FIFO.

• The element with highest priority is removed first.

• If two elements have the same priority, then they are served according to FIFO.

• It can be implemented using arrays, linked list or heap.

Types of Priority Queue:-
• Ascending Priority Queue (Lower value = higher priority)
• Descending Priority Queue (Higher value = higher priority)

Applications of Priority Queue:-
• CPU scheduling
• Dijkstra’s shortest path algorithm

Structure of Priority Queue:-


4. Deque (Double Ended Queue):-

• Deque stands for Double Ended Queue.

• It is a type of queue in which insertion and deletion can be performed from both ends (front and rear).

• It does not strictly follow FIFO.

Types of Deque:-

  1. Input Restricted Deque:-
    • Insertion is allowed at only one end (usually rear).
    • Deletion is allowed at both ends.
  2. Output Restricted Deque:-
    • Insertion is allowed at both ends.
    • Deletion is allowed at only one end (usually front).

Applications of Deque:-
• Sliding window problems
• Palindrome checking

Structure of Deque:-



1.Write a C program to implement a Linear Queue using array and perform:
ENQUEUE, DEQUEUE, DISPLAY.

Code : 
#include <stdio.h>
#define MAX 5

int queue[MAX];
int front = -1, rear = -1;

// ENQUEUE Operation
void enqueue(int value)
{
    if (rear == MAX - 1)
    {
        printf("Queue Overflow\n");
    }
    else
    {
        if (front == -1)
            front = 0;

        rear++;
        queue[rear] = value;
        printf("%d inserted into queue\n", value);
    }
}

// DEQUEUE Operation
void dequeue()
{
    if (front == -1 || front > rear)
    {
        printf("Queue Underflow\n");
    }
    else
    {
        printf("%d deleted from queue\n", queue[front]);
        front++;
    }
}

// DISPLAY Operation
void display()
{
    if (front == -1 || front > rear)
    {
        printf("Queue is empty\n");
    }
    else
    {
        printf("Queue elements are: ");
        for (int i = front; i <= rear; i++)
        {
            printf("%d ", queue[i]);
        }
        printf("\n");
    }
}

// MAIN Function
int main()
{
    int choice, value;

    while (1)
    {
        printf("\n--- Linear Queue Menu ---\n");
        printf("1. ENQUEUE\n");
        printf("2. DEQUEUE\n");
        printf("3. DISPLAY\n");
        printf("4. EXIT\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);

        switch (choice)
        {
            case 1:
                printf("Enter value to insert: ");
                scanf("%d", &value);
                enqueue(value);
                break;

            case 2:
                dequeue();
                break;

            case 3:
                display();
                break;

            case 4:
                return 0;

            default:
                printf("Invalid choice\n");
        }
    }

    return 0;
}
output :-