Data Structures Tutorial

Data Structures Tutorial Asymptotic Notation Structure and Union Array Data Structure Linked list Data Structure Type of Linked list Advantages and Disadvantages of linked list Queue Data Structure Implementation of Queue Stack Data Structure Implementation of Stack Sorting Insertion sort Quick sort Selection sort Heap sort Merge sort Bucket sort Count sort Radix sort Shell sort Tree Traversal of the binary tree Binary search tree Graph Spanning tree Linear Search Binary Search Hashing Collision Resolution Techniques

Misc Topic:

Priority Queue in Data Structure Deque in Data Structure Difference Between Linear And Non Linear Data Structures Queue Operations In Data Structure About Data Structures Data Structures Algorithms Types of Data Structures Big O Notations Introduction to Arrays Introduction to 1D-Arrays Operations on 1D-Arrays Introduction to 2D-Arrays Operations on 2D-Arrays Strings in Data Structures String Operations Application of 2D array Bubble Sort Insertion Sort Sorting Algorithms What is DFS Algorithm What Is Graph Data Structure What is the difference between Tree and Graph What is the difference between DFS and BFS Bucket Sort Dijkstra’s vs Bellman-Ford Algorithm Linear Queue Data Structure in C Stack Using Array Stack Using Linked List Recursion in Fibonacci Stack vs Array What is Skewed Binary Tree Primitive Data Structure in C Dynamic memory allocation of structure in C Application of Stack in Data Structures Binary Tree in Data Structures Heap Data Structure Recursion - Factorial and Fibonacci What is B tree what is B+ tree Huffman tree in Data Structures Insertion Sort vs Bubble Sort Adding one to the number represented an array of digits Bitwise Operators and their Important Tricks Blowfish algorithm Bubble Sort vs Selection Sort Hashing and its Applications Heap Sort vs Merge Sort Insertion Sort vs Selection Sort Merge Conflicts and ways to handle them Difference between Stack and Queue AVL tree in data structure c++ Bubble sort algorithm using Javascript Buffer overflow attack with examples Find out the area between two concentric circles Lowest common ancestor in a binary search tree Number of visible boxes putting one inside another Program to calculate the area of the circumcircle of an equilateral triangle Red-black Tree in Data Structures Strictly binary tree in Data Structures 2-3 Trees and Basic Operations on them Asynchronous advantage actor-critic (A3C) Algorithm Bubble Sort vs Heap Sort Digital Search Tree in Data Structures Minimum Spanning Tree Permutation Sort or Bogo Sort Quick Sort vs Merge Sort

Implementation of Queue

Implementation of queue: We can implement the queue through the array and linked list. An array is the easiest way to implement the queue.

When a queue is created with the help of an array, the number of its elements is declared before processing. The beginning of the array becomes its "front" end, and the end of the array becomes its "rear" end. The terms "front" and "rear" are used to describe the linear list when implemented as a queue.

The "Front" stores the index of the first element in the queue. The "rear" stores the index of the last element in the queue. At any given time, the number of elements in a queue can be calculated from the values ??of "front" and "rear".

if front = 0 then number of elements = 0 
else no of elements = front – rear + 1.

Enqueue operation

When you insert an element in the queue, that operation is called enqueue.

Algorithm of insert the element of the queue

Step 1: Before adding elements, it is checked whether the queue is full or not. 
Step 2: If the queue is full, it will print the "overflow error" message, and the program will terminate. 
Step 3: If the queue is not full, the value of the "rear" end will be increased by 1, and a new element will be added to the queue-array.  

Insertion in a queue implemented as an array

if rear = NULL then
 {      
  rear = front = 0        
  Queue [0] = ITEM 
} 
else if rear = N – 1 then
 {         
print “Queue full, overflow” 
} 
else 
{         
Queue [rear + 1] = ITEM         
rear = rear + 1
 } 
END  

Dequeue operation

When you remove an element from the queue, that operation is called dequeue.

Algorithm of insert the element of the queue

Step 1: Before removing elements, it is checked whether the queue is empty or not. 
Step 2: If the queue is empty, it will print the "underflow error" message, and the program will terminate. 
Step 3: If the queue is not empty, the value of the "front" end will be increased by 1, and an element will be removed in the queue-array.  

Deletion in a queue implemented as an array

if front = NULL then
 {       print “quere empty, underflow” 
} 
else 
{       
 ITME = Queue[front]        
 if front = rear then         
 {            
  front = rear = NULL        
  }       
 else        
  {            
  front = front + 1         
 } 
 } 
END  

Queue program in C language:

#include<stdio.h> 
#include<stdlib.h>
#define maxsize 5 
void insert();  
void delete();  
void display(); 
int front = -1, rear = -1;  
int queue[maxsize];   
void main ()  
 {      
 int choice;      
  while(choice != 4)       
 {            
  printf("\n1.insert of element\n2.Delete of element\n3.Display the queue\n4.Exit\n");         
 printf("\nenter your choice = ");          
 scanf("%d",&choice);         
  switch(choice)          
 {         
      case 1:             
  insert();              
 break;              
 case 2:             
  delete();          
     break;          
     case 3:         
      display();         
      break;             
  case 4:             
  exit(0);            
   break;            
   default:          
      printf("\nenter valid choice??\n");    
       }   
    }  
 }  
 void insert() 
  {  
int item;     
printf("\nenter the element\n");   
    scanf("\n%d",&item);        
   if(rear == maxsize-1)     
  {         
  printf("\n OVERFLOW \n");        
   return;    
   }   
    if(front == -1 && rear == -1)   
    {      
     front = 0;  
         rear = 0;      
 }      
 else      
  {        
   rear = rear+1;     
  }     
  queue[rear] = item;  
     printf("\n value inserted ");     
     }  
 void delete()  
 {    
   int item;    
    if (front == -1 || front > rear)  
     {   
        printf("\n UNDERFLOW \n");   
        return;    
                  }    
   else  
     {    
       item = queue[front];     
      if(front == rear)     
      {       
        front = -1;     
          rear = -1 ;    
       }        
   else         
   {            
   front = front + 1;     
      }       
    printf("\n value deleted ");    
   }     
            }   
       void display() 
  {      
 int i;  
     if(rear == -1)  
     {        
   printf("\n empty queue\n");   
    }    
   else    
   { 
  printf("\n printing values \n");  
         for(i=front;i<=rear;i++)   
        {          
     printf("\n%d\n",queue[i]);   
        }      
    }  
 }  

 Output:

1.insert of element 
2.Delete of element 
3.Display the queue 
4.Exit   

enter your choice = 1   
enter the element 1   
Value inserted   

1.insert of element 
2.Delete of element 
3.Display the queue 
4.Exit   

enter your choice = 1   
enter the element 2   
Value inserted   

1.insert of element 
2.Delete of element 
3.Display the queue 
4.Exit   

enter your choice = 2   
value deleted   

1.insert of element 
2.Delete of element 
3.Display the queue 
4.Exit   

enter your choice = 3   
printing values   2   
1.insert of element 
2.Delete of element 
3.Display the queue 
4.Exit   

enter your choice = 4



ADVERTISEMENT
ADVERTISEMENT