Queue ADT

 

Queue ADT

Handwritten Notes- Click Here

A Queue is a linear data structure in which elements are inserted at one end and removed from the other end.(Insertion → Rear, Deletion → Front)                          

       ↓FRONT                                ↓REAR

A

B

C

D

E

  

A queue follows the FIFO (First In, First Out) principle. This means that the element inserted first is removed first.

A Queue can be implemented using:

• Array
• Linked List

Basic Queue Operations:

1. Enqueue-used to insert  a new element into the queue.

2. Dequeue-used to remove an element from the queue.

3. Peek-used to view the first element without removing it.

4. isEmpty-checks whether the queue contains any elements.

5. isFull-checks whether the queue has reached its maximum capacity

Enqueue Operation

The process of inserting a new element at the REAR end of the queue is called Enqueue.

Algorithm

1. Check whether the queue is full.
2. If the queue is full, report Queue Overflow.
3. If the queue is empty, set FRONT = 0.
4. Otherwise, increment REAR.
5. Insert the new element at the REAR position

 C Program

void enqueue(int data)
{
    if (rear == MAXSIZE - 1)
    {
        printf("Queue Overflow");
    }
    else
    {
        if (front == -1)
            front = 0;

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

}

     Before Enqueue       

 FRONT          REAR

   ↓                        ↓                                                  

A

B

C

D

  0        1        2       3

        After Enqueue  (Enqueue E)

FRONT                  REAR

   ↓                                ↓   

A

B

C

D

E

  0         1       2       3      4

Dequeue Operation

The process of removing an element from the FRONT end of the queue is called Dequeue.

Since a queue follows FIFO, the element that entered first is removed first.

Algorithm

1. Check whether the queue is empty.
2. If the queue is empty, report Queue Underflow.
3. Store the element present at FRONT.
4. Increment FRONT.
5. Return the deleted element.

C Program

int dequeue()
{
    int data;
 
    if (front == -1 || front > rear)
    {
        printf("Queue Underflow");
        return -1;
    }
 
    data = queue[front];
    front++;
 
    return data;

}

     Before Dequeue

FRONT                  REAR

   ↓                                ↓   

A

B

C

D

E

  0         1       2       3      4

           After Dequeue

The element A is removed.
The FRONT moves to the next element.

FRONT                 REAR

   ↓                               ↓   

B

C

D

E

  0         1       2       3      4

Video Explanation