Data Structure- 5 Queue Concept using Circular Array

// In this article we will Learn concept of circular array to

implement the queue concept because as we can see the in linear array there is a no way to store new item even if there is a space after deleting an element ! 

with circular array w will use MAX-1 index of array and initially we will put front and rear to index zero position !

1. when we need to insert a data we just increment the rear and insert the data !
2. When we need to delete the data we just increase the front and print the data!

Only important point is that when during insertion if rear== front then it means the queue is full now and we will put rear one position back , if rear =0 then one position back is MAX-1; and if rear != 0 then one position back is rear-1;

In order to move rear and front we will use mod operator!

/******************************************************************************
Queue Concept using Circular Array !               
@Mukesh Mann dated 16-02-2020
*******************************************************************************/

#define MAX 4

enqueue(int);

//void delete();

void display();

int queue_array[MAX];

int rear = 0;

int front = 0;

 enqueue(int item)

{

    //int item;

     rear=(rear+1)%MAX;

    if (front==rear)

    {

        printf("Queue Overflow \n");

        if(rear==0)

        {

          rear=MAX-1; 

        }

        else {

        rear=rear-1;}

        return;

    }

    else

    {

    queue_array[rear]= item;

    printf("iTEM INSERTED is %d\n",queue_array[rear]);

       return;

    }

} /* End of Enqueue() */

 deqeue()

{

    if(front==rear)

    {

         printf("Queue is empty on");

         return -1;

    }

    else

    {

          front=(front+1)%MAX;

         int item= queue_array[front];

         printf("Deleted Item is %d\n",item);

          return item;

    }

  

} /* End of deqeue() */

 main()

 {

    

// Here we try to insert 3 item using a loop

 // initially front and rear are point to zero and we will utilize only max-1 index of circular array

     for (int i = front; i <= MAX-1; i++){

     enqueue(i);

      }

     

      for (int i = front; i <= MAX-1; i++){

       deqeue();

      }

    

}

Data Structure- 4. Queue Concept

Like Stack data Structure ! Queue is also another type of Data Structure which follows the concept of FIFO ! Thas is the element which comes first will be deleted first!

Concept to code !- We maintain two variables called front and Rear, The Front will always point to the first element in the queue and the Rear will  element will always point to the current element that is just inserted into the queue.
 If you will follow this than lets suppose we are given the following list of element

<5,6,7,8> then in queue it will look like, Initially 

                        F=R=-1

Thus whenever you wish to insert ( Enqueue) an element then simply increment the rear and put the item there ! when you wish to delete ( Dequeue ) the item the you simply increment the front and take out the item from there!

Thus here is the Code to push and pop an element from the queue !
/******************************************************************************
Queue Concept using an Array !               
@Mukesh Mann dated 16-02-2020
*******************************************************************************/
/*
 * C Program to Implement a Queue using an Array
 */
#include <stdio.h>

#define MAX 50

void insert();
void delete();
void display();
int queue_array[MAX];
int rear = - 1;
int front = - 1;
main()
{
    int choice;
    while (1)
    {
        printf("1.Insert element to queue \n");
        printf("2.Delete element from queue \n");
        printf("3.Display all elements of queue \n");
        printf("4.Quit \n");
        printf("Enter your choice : ");
        scanf("%d", &choice);
        switch (choice)
        {
            case 1:
            insert();
            break;
            case 2:
            delete();
            break;
            case 3:
            display();
            break;
            case 4:
            exit(1);
            default:
            printf("Wrong choice \n");
        } /* End of switch */
    } /* End of while */
} /* End of main() */

void insert()
{
    int add_item;
    if (rear == MAX - 1)
    printf("Queue Overflow \n");
    else
    {
        if (front == - 1)
        /*If queue is initially empty */
        front = 0;
        printf("Inset the element in queue : ");
        scanf("%d", &add_item);
        rear = rear + 1;
        queue_array[rear] = add_item;
    }
} /* End of insert() */

void delete()
{
    if (front == - 1 || front > rear)
    {
        printf("Queue Underflow \n");
        return ;
    }
    else
    {
        printf("Element deleted from queue is : %d\n", queue_array[front]);
        front = front + 1;
    }
} /* End of delete() */

void display()
{
    int i;
    if (front == - 1)
        printf("Queue is empty \n");
    else
    {
        printf("Queue is : \n");
        for (i = front; i <= rear; i++)
            printf("%d ", queue_array[i]);
        printf("\n");
    }
} /* End of display() */

Data Structure- 3. Stacks Push and POP Operation using Linked List

As you know that in a stack the push and pop operation always done from the top, so if you imagine each index of stack a  linked list than the push operation is nothing more than inserting a node at the front of list and pop operation is nothing but deletion a node from the front of list ( i.e., TOP)

 here is the code for you ! Note that we have used power of recursion here to push the elements in the stack !
/******************************************************************************
Stacks Push and POP Operation using Linked List             
@Mukesh Mann dated 16-02-2020
*******************************************************************************/

#include <stdio.h>
/* Lets create structure of the node*/
             struct node
            {
                int data;
                struct node *link;
               
            }*head= NULL; // Creating a global head pointer of struct type
           
 createnode(int n, int item)
 {
     if(n){
     int data ;
     struct node *temp;
    /* lets create first node using malloc */
    temp=(struct node*)malloc(sizeof(struct node));
   
                  if(temp == NULL)
                 {
                     printf("Memory not allocated ");
                     return;
                    
                 }
    
     temp-> data = item;
     temp->link=head;
     head= temp;
     // now suppose second element is 1 more than previous
     createnode(n-1,item+1);
         return head;
     }
  
    
      }
      
     
      int main()
 {
        int n, item;
        printf("Enter number of elemens to be pushed in stack\n\n");
        scanf("%d", &n);
        printf("Enter the item \n\n");
        scanf("%d", &item);
        struct node *temp1=createnode(n,item);  / holding returned value of head which is a pointer
        for(int i=0;i<n;i++)
        {
        head= temp1;
        printf("Top %d in the stack is %d\n", i, temp1->data);
        temp1= temp1->link;
        }
        return 0;
 }

// The deletion of an element from the stack using concept of linked list is left as an exercise for you !
   

Data Structure- 2. Stacks Push and POP Operation

As you know that in stack we always perform push and pop f an element from the top of the stack , here is the code to do the same

/******************************************************************************
Push and Pop Operation in Stack !               
@Mukesh Mann dated 16-02-2020
*******************************************************************************/
#include <stdio.h>
 int top=-1; // Delaring a Top variable initially pointing to -1
 int stack [10]; // a stack array of 10 elements

int main()
{
   
    // Push operation in stack  array
    for (int i=0; i<=10; i++)
    {
    top=top+1;
    stack[top]=i;
      }
     
   // Printing content of stack array
     for (int i=1; i<=10; i++)
     {
     printf(" The element in the stack are %d\n",stack[i]);  
     }
   
    // pop operation in stack array
   
    for (int i=1; i<=10; i++)
     {
     printf(" poping %d  element  %d\n",i, stack[top]);
     top=top-1;
     }

    printf(" After perfroming pop operation the content of stack is %d\n",stack[top]);
    
    return 0;
}

Data Structure- 1. Stacks Introduction

 As you know that a program is supposed to take some input and is expected to give some output ! The input and the output to a program is given in some format, that format is what we called as data structure!

You can think if we give a unsorted array to a sorting program than the time taken to sort the elements is more as compared to a sorted input array ! this means that the format of input data plays an important role as far as far as performance of an algorithm is considered. !

In this respect the first and traditional way of giving the data was using - STACK.

A stack is a data structure ( i.e., a type of input format) which follows LIFO property, that is the last element is popped out first from the top of the stack.

The main application of stacks are in

1. Recursion :- Remember how recursive calls for a function is made by creating a stack activation record

2. Text Editors- use stacks for Redo & undo Operations.

3. Brower's use stacks for remembering which page is visited and then going back( i,e, POP )

In this article we will study how stack push and pop operations wor

16.Doubly Linked List :3- Insert Newnode at different positions

/* Try to insert a new node in the current doubly linked list structure at

1. Begging , 2. Last, 3. At middle after some data  */

/* this exercise is left for you */

15.Doubly Linked List :2- Create and traverse in doubly Linked List

/*****************************************************************************
Doubly linked list creation !               
@Mukesh Mann dated 10-02-2020.
*******************************************************************************/
#include <stdio.h>
/* Lets create structure of the node*/
             struct node
            {
                int data;
                struct node *prev;
                struct node *next;
            }*head; // Creating a global head pointer of struct type
/*  lets declare a function to create nodes*/
void createnode();
void traverselist();
int main()
 {
        int n;
        printf("Enter number of node\n\n");
        scanf("%d", &n);
        createnode(n);
        printf("\nTraversing the created list\n");
        traverselist();
 }
 void createnode(int n)
 {
     struct node *temp;
     int x ;
     //struct node *temp;
    /* lets create first node using malloc */
    head=(struct node*)malloc(sizeof(struct node));
    
                 if(head == NULL)
                 {
                     printf("Memory not allocated ");
                     return;
                   
                 }
     printf("Enter first node data ");
     scanf("%d", &x);
     temp=head;
     temp->prev=NULL;
     temp->next=NULL;
     temp->data = x;
     int k;
                       for(int i=2; i<=n; i++)
                  {
                     
                   struct node  *NewNode=(struct node *)malloc(sizeof(struct node));
                          if(NewNode== NULL)
                            {
                               printf("Memory not allocated ");
                               break;
                            }
                         printf("Enter  node data ");
                         scanf("%d", &k);
                         NewNode->data=k;
                         NewNode->next=NULL;
                         NewNode->prev=temp;
                         temp->next=NewNode;
                         //head->next->prev=head;
                         temp=temp->next;
                        
//printf("Printing Element of Linked List %d\n",head->data);
                  }
        printf("List created successfuly!\n");
       
 }
   
/*****
traverselist function
*****/ 
void traverselist()
{
   struct node *temp;
   temp=head;
   // printf("Value in temp is %d and temp points to %d", temp,temp->data);
    int i=1;
           while(temp!=NULL)
               {
               printf("Printing %d Element of Linked List - %d\n",i,temp->data);
                   i++;
                   temp=temp->next;
               }
               return;
}

14. Doubly Linked List :1- Creating a Structure node for doubly Linked List

#include <stdio.h>
/* Lets create structure of the node*/
             struct node
            {
                int data;
                struct node *prev;
                struct node *next;
            }*head; // Creating a global head pointer of struct type

13. Complete Program for Singly Linked List

// This program is summation of all the sub function we have covered from 1-12

/*****************************************************************************
                    
@Mukesh Mann dated 27-01-2020.
*******************************************************************************/
#include <stdio.h>
/* Lets create structure of the node*/
             struct node
            {
                int data;
                struct node *link;
            }*head; // Creating a global head pointer of struct type
/*  lets declare a function to create nodes*/
 void createnode(int n);
 void inseratbegning();
 void inseratend();
 void traverselist();
 void inseratanyindex();
 void deletnodefrombegning();
 void deletelastnode();
 void deleteatanyindex();
 void movelastnodetofront();
 struct node * Reverseiterative(struct  node *);
void ReverseusingRecursion(struct  node *,struct node *);

  //void struct node *ReverseusingRecurssion(struct node);
/* lets call main function */

 int main()
 {
        int n;
        printf("Enter number of node\n\n");
        scanf("%d", &n);
        createnode(n);
        printf("Inserting a new node with value 40 at the begning of  list\n\n");
        inseratbegning();
        printf("Inserting a new node with value 70 at the end of list\n\n");
        inseratend();
        printf("\nTraversing the created list\n");
        traverselist();
        printf("Inserting a new node with value 90 after node 2 in the linked list\n\n");
        inseratanyindex();
        printf("After inserting current list is as under\n\n ");
        traverselist();
        printf("Deleteing firt node from list\n");
        deletnodefrombegning();
        printf("After deleteing current list values are\n\n ");
       traverselist();
       printf("----------------------------------Delete node from last--------------------\n");
       deletelastnode();
       printf("After deleteing last node the  current list values are\n\n ");
       traverselist();
       printf("----------------------------------Delete node WITH VALUE =3 IN THE LIST--------------------\n");
       deleteatanyindex();
       printf("After deleteing node WITH VALUE =3;  the  current list values are\n\n ");
       traverselist();
       printf("Move last node to front of node\n\n ");
       movelastnodetofront();
       printf("----------------------AfterMoving last node to front the list is --------------\n\n ");
       traverselist();
     printf("----------------------An Iterative verison to reverse data in linked list --------------\n\n ");
     //*Reverseiterative function will return a pointer and takes a pointer
     head= (*Reverseiterative)(head); 
      traverselist();
     
     printf("----------------------A Recursive verison to reverse data in linked list --------------\n\n ");
     //*Reverseiterative function will return a pointer and takes a pointer
     ReverseusingRecursion(NULL,head); 
      traverselist();
       return 0;
 }
 void createnode(int n)
 {
    
     int data ;
     struct node *temp;
    /* lets create first node using malloc */
    head=(struct node*)malloc(sizeof(struct node));
    
                 if(head == NULL)
                 {
                     printf("Memory not allocated ");
                     return;
                    
                 }
     printf("Enter first node data ");
     scanf("%d", &data);
     temp=head;     
     head-> data = data;
     head->link=NULL;
     
     
                  for(int i=2; i<=n; i++)
                  {
                     
                   struct node  *NewNode=(struct node *)malloc(sizeof(struct node));
                          if(NewNode== NULL)
                            {
                               printf("Memory not allocated ");
                               break;
                             }
                         printf("Enter  node data ");
                         scanf("%d", &data);
                         NewNode->data=data;
                         NewNode->link=NULL;
                         temp->link=NewNode;         // linking current node with NewNode
                         temp = temp->link;   // Moving temp node to NewNode location
                  }
        printf("List created successfuly!\n");
                
      }
   
/*****
traverselist function
*****/ 
void traverselist()
{
    struct node *temp=head;
    int i=1;
           while(temp)
               {
               printf("Printing %d Element of Linked List %d\n",i,temp->data);
                   i++;
                   temp= temp->link;
               }
}
/*****
inseratbegning function
*****/     
void inseratbegning()
{
          printf("\nLets insert a node at the begninig\n");
          struct node *mynode;
          mynode=(struct node *)malloc(sizeof(struct node));
         
          mynode->link=head;
          mynode->data=40;
          head=mynode;
        printf("New Node Inserted Successfuly at the begning!\n");
}
         
/*****
inseratEnd function
*****/     
void inseratend()
{
          printf("\nLets insert a node at the End\n");
          struct node *mynode;
          struct node *temp=head;
          mynode=(struct node *)malloc(sizeof(struct node));
         
          while(temp->link!=NULL)
          {
             
             temp=temp->link;
             
          }
          temp->link=mynode;
          mynode->link=NULL;
          mynode->data=70;
          printf("New Node Inserted Successfuly at the End!\n");
}
    
/*****
inseratanyindex function
*****/     
void inseratanyindex()
{
printf("\nLets insert a node at the End\n");
 struct node *mynode;
 struct node *temp=head;
 mynode=(struct node *)malloc(sizeof(struct node));
         
          while(temp->data!=2)
          {
             temp=temp->link;
             
          }
          mynode->link=temp->link;
          temp->link=mynode;
          mynode->data=90;
         printf("New Node Inserted Successfuly at the after node 2!\n"); 
}
/*****
deletnodefrombegning()
*****/
deletnodefrombegning()
{
 struct node *temp=head;
 if(head== NULL)
 {
    printf("THERE IS NO NODE TO DELETE\n");  
 }
 if(head->link==NULL) // there is only one node
 {
     free(head);
     head=NULL;
 }
 head=head->link;
 free(temp);
}

   /*****
deletelastnode()
*****/
deletelastnode()
{
 struct node *temp=head;
 while(temp->link->link!=NULL)
 {
   temp=temp->link;  
 }
 temp->link->link=NULL;
 free(temp->link);
 temp->link=NULL;
}
/*****
deleteatanyindex()
*****/
deleteatanyindex()
{
  struct node *temp=head;
  while(temp->link->data!=3)
  {
     temp=temp->link;  
  }
  struct node *temp1=temp->link;
  temp->link=temp1->link->link;
  free(temp1);
  temp1= NULL;
}
 /*****
Moving Last node to the front of linked list
movelastnodetofront()
*****/
// Lets have two pointer (p,q) one will be one step ahead of other;
// the moment one pointer (p) reaches last node ; point its link to head,
// and put null into q ;
movelastnodetofront()
{

 struct node *p,*q;
 p=head;
  while(p->link != NULL)
{
   
    q=p;
    p=p->link;
}
 q->link= NULL;
 p->link=head;
 head=p;
}
/*****
Reverseing content of linked list using Iterative version
Reverseiterative() is a function pointer which returns a pointer to a structure
and it takes head as its initial pointer as parameter
*****/
 struct node *Reverseiterative(struct  node *curr)
{
  
struct node *prev= NULL;
   struct node *nextnode= NULL;
    while(curr)
    {
     nextnode =curr->link;
     curr->link= prev;
     prev=curr;
     curr=nextnode;
    }
    head=prev;
      printf("value of current node is%d",head);
   return prev;
   }
  
 /*****
Reverseing content of linked list using Recursion
ReverseusingRecursion() is a function  which returns a pointer to a structure
and it takes NULL in prev node and head in curr.
*****/
void ReverseusingRecursion(struct node *prev, struct node *curr)
{
    if(curr)
    {
     ReverseusingRecursion(curr,curr->link);
     curr->link=prev;
    }
    else
    head=prev;
}