Queue – Introduction, Explanation and Implementation

A queue is a data structure used to store items that has defined way of Insertion and Deletion operation. It follows First in First Out(FIFO) means items inserted first will be removed first.

People waiting in a line, maybe for a railway ticket or for an interview are very commonly seen. Every time a person arrives will join the line at the back end side while the front end side will be served. The line referred is termed as Queue. There could be several examples of a queue.
For simplification, that back end is referred as Rear and the front end is referred as Front.
Following two operations are mainly carried on a queue:

• Push – It refers to inserting an item in the Queue. Insertion is always done at the rear of the queue.
• Pop – It refers to removing an item from the Queue. Deletion is always done at the front of the queue.

See the following picture. At the left, item 30 is pushed at the rear side and in the right shown item 10 is popped. After 10 if further pop operation is carried then it’ll be item 20.

Interestingly, in a stack, the insertion and deletion end is same i.e. both the operations are done at the Top of Stack, however, in case of queue both operations are done at different ends.

Read – Stack – Introduction, Explanation and Implementation

Implementation

For implementing Queue there are two possible ways-

1. Using Array
2. Using Linked list

Note:-
If the queue is empty and pop operation is applied which is not possible then it is called Queue Underflow (like buffer underflow).
If the queue is full and push operation is applied which is not possible then it is called Queue Overflow (like buffer overflow).

1. Using Array

Under this, an array is defined and items are pushed to and popped from this array. Since an array is a static data structure, such a queue will be bounded by a fixed number of max allowed items. We can use dynamic array but, then the queue will no longer be persistent.

Implementation of Queue in C Using Array

In the following program array of size of 3 is declared i.e. Max 3 items can be stored in the queue. Pushing more than three items result in Queue Overflow.

#include<stdio.h>
#define MAX 3
     
    int Queue[MAX];   //creating an array for queue with capacity 3
    int FRONT = -1;  //item deleted at FRONT index
    int REAR = -1;   //item inserted at REAR index

/* insertion of item in the Queue*/     
void push(int item){
		
    if( (FRONT == REAR + 1) || (FRONT == 0 && REAR == MAX-1)){
        printf("Queue Overflow\n");
	return ;
     }
     if(FRONT == -1)
        FRONT = 0;
     REAR = (REAR + 1) % MAX;
     Queue[REAR] = item;
     printf("Item pushed = %d\n", item);
}

/*deleting item from the Queue*/     
void pop(){

    if(FRONT == -1){
        printf("Queue Underflow\n");
	return ;
    }
    printf("Item popped = %d\n", Queue[FRONT]);
/* causes next time insertion will be with REAR = 0; */
    if(REAR == FRONT)
	FRONT = REAR = -1;
    else
	FRONT = (FRONT + 1) % MAX;
}
     
int main(void){
    push(10);
    push(20);
    push(30);
    push(40);  // pushing more than 3 item lead to overflow
    
    pop();     //item 10 popped
    pop();     //item 20 popped
    pop();     //item 30 popped
    pop();    // lead to underflow
return 0;   
}

Output:-

Item 10 pushed
Item 20 pushed
Item 30 pushed
Queue overflow

Item 10 poped
Item 20 poped
Item 30 poped
Queue Underflow

2.Using Linked list

While implementing Queue using linked list, a linked list is defined and items are pushed to start and popped from the end of the linked list. Using Linked list implementation we can create Queue of the desirable size which is bounded in array implementation, this also removes Queue Overflow problem until the memory is full. That’s the advantage of using linked list over an array.

Implementation of Queue in C Linked List

#include<stdio.h>
#include<stdlib.h>
 
typedef struct node{
    int data;
    struct node *next;
    }Node;
 
Node *head = NULL;
 
Node *push(Node *head, int item){
 
    Node *list = head;
    Node *temp = (Node*)malloc(sizeof(Node));
 
    temp->data = item;
    temp->next = NULL;
 
    if(list)
        temp->next = list;
 
    printf("Item %d pushed\n", temp->data);  
 
    return temp;
    }
 
Node *pop(Node *head){
     
    Node *list = head;
   Node *temp = (Node*)malloc(sizeof(Node));
 
   /* if queue has no element */
    if(!list){
        printf("Queue underflow\n");
        return head;
    }
    /* if queue containing one element */
    else if(!list->next){
        printf("Item %d popped\n", list->data);
        free(list);
        return NULL;
        }
   /* at the end of loop temp points to second last node*/
    else
        while(list->next){
            temp = list;
            list = list->next;
            }
 
    printf("Item %d popped\n", list->data);
    temp->next = NULL;
    free(list);
 
    return head;
}
     
int main(void){
 
    Node *head = NULL;
    /* Inserting the item  10, 20, 30*/
    head = push(head, 10);
    head = push(head, 20);
    head = push(head, 30);
 
    printf("\n");
    /* Deleting the item 10, 20, 30*/
    head = pop(head);
    head = pop(head);
    head = pop(head);
 
    pop(head); // will cause queue underflow
 
    return 0;
}

Output:-

Item 10 pushed
Item 20 pushed
Item 30 pushed

Item 10 popped
Item 20 popped
Item 30 popped
Queue underflow

Uses of Queue in computer science:

• If a resource(CPU scheduling, Disk Scheduling) is shared among multiple processes(equal priority). They are made to wait in a queue.
• If there is asynchronous data transfer(can be IO Buffers, pipes, file IO, etc.), again a queue is used. Data entered first in the queue will be consumed first. Here queue is basically a small sized memory sometimes referred as Mailboxes.

Knowledge is most useful when liberated and shared. Share this to motivate us to keep writing such online tutorials for free and do comment if anything is missing or wrong or you need any kind of help.
Keep Learning… Happy Learning.. 🙂

Recommended -