Queue Implementation using LinkedList

Queue is a FIFO type data structure ie element which is inserted first can be deleted first or goes out first, the following program gives implementation of queue using linked list:

/*************************************************************
* Author: Aniruddha S N
* 
*/

#include<iostream>

using namespace std;

// structure node
struct node
{
    int info;
    struct node* next;
    struct node* prev;
};


//function declaration
void insertQueue(int ele);
void deleteQueue();
void displayQueue();
void freeQueueMemory();

//Global Variables
node* front = NULL;
node* rear  = NULL;

//main function
int main()
{
    int ch    = 0;
    int ele   = 0;

    while(1)
    {
        cout<<"**************QueueOperations********************\n";
        cout<<"1------->insert an element into queue\n";
        cout<<"2------->display the queue\n";
        cout<<"3------->delete an element from queue\n";
        cout<<"*************************************************\n";
        cout<<"Enter your choice\n";
        cin>>ch;
        //use the switch case to call functions for respective operations
        switch(ch)
        {
        case 1: cout<<"Enter the element to be inserted into the queue\n";
                cin>>ele;
                insertQueue(ele);
                break;
        case 2: displayQueue();
                break;
        case 3: deleteQueue();
                break;
        default:freeQueueMemory();
                exit(0);
        }
    }
}

void insertQueue(int ele)
{
    node* temp;
    if(front == NULL)
    {
     temp= new node();
     temp->info=ele;
     temp->next=NULL;
     temp->prev=NULL;
     front = temp;
     rear  = temp;
    }
    else
    {
        temp=new node();
        temp->info=ele;
        temp->next=NULL;
        rear->next=temp;
        temp->prev=rear;
        rear=temp;
    }
}

//function to delete an element from queue
void deleteQueue()
{
    node* temp;
    if(front == NULL || rear == NULL)
      cout<<"Queue is empty\n";

  else
  {
      //delete an element from front
      temp=front->next;
      if(front->next != NULL)
      temp->prev=NULL;
      front->next=NULL;
      delete front;

      //make front point to the next element
      front = temp;
    }
}
void displayQueue()
{
    node*temp;
    temp=front;
    cout<<"\nQueue Elements from front:\n";
    while(temp != NULL)
    {
        cout<<temp->info<<"\n";
        temp=temp->next;
    }
}
void freeQueueMemory()
{
    node* temp;
    node* prev = NULL;
    temp=front;
    if(front == NULL || rear == NULL)
        return;
//traverse through the queue and delete the memory assigned to all the nodes
    while(temp->next != NULL)
    {
        prev=temp;
        temp=temp->next;
        temp->prev=NULL;
        prev->next=NULL;
        prev->prev=NULL;
        delete prev;
        prev=NULL;
    }
// delete the memory of last node
    temp->prev=NULL;
    temp->next=NULL;
    delete temp;
    temp = NULL;
}

Doubly Linked List Implementation

Following program gives Implementation of Doubly Linked List with its various operations:

/************************************************************* * Author: Aniruddha S N * */ #include<iostream> using namespace std; // structure node struct node { int info; struct node* next; struct node* prev; }; //function declarations void display_list(); void Insert_Element_List(int ele); void DeleteElementAtPos(int pos); void display_Prev_Next(int pos); void delete_Entire_list(); //global variable first node* first = NULL; //main function int main() { int ele = 0; int ch = 0; int pos = 0; //Menu to display Doubly linked list operations while(1) { cout<<"**************DoublyLinkedListOperationsMenu*************\n"; cout<<"1---->Insert an element in list\n"; cout<<"2---->displayList\n"; cout<<"3---->DeleteAnElement at specified position in list\n"; cout<<"4---->Display Previous and Next ele of the mentioned node\n"; cout<<"5---->exit\n"; cout<<"***************************************************\n"; cout<<"\n\n"; cout<<"Enter your choice:\n"; cin>>ch; //using switch case call respective functions for respective choices switch(ch) { case 1: cout<<"Enter the element to be inserted into list\n"; cin>>ele; Insert_Element_List(ele); break; case 2:display_list(); break; case 3:cout<<"Enter the position to delete elements\n"; cin>>pos; DeleteElementAtPos(pos); break; case 4:cout<<"Enter the Node Position to display previous and next ele\n"; cin>>pos; display_Prev_Next(pos); break; default: delete_Entire_list(); exit(0); } } return 0; }//end of main //function to insert an element in singly linked list void Insert_Element_List(int ele) { node* temp; if(first == NULL) { first= new node(); first->info=ele; first->next=NULL; first->prev=NULL; } else { node* temp1; temp1 = new node(); temp=first; //find the end of list while( temp->next != NULL) temp=temp->next; temp1->info=ele; temp1->next=NULL; //attach the new node at the end of list temp->next=temp1; temp1->prev=temp; } } //function to display the elements in the list void display_list() { if ( first == NULL) cout<<"list doesnt have any elements"; else if(first->next == NULL) { cout<<"List Contents:\n"; cout<<first->info<<"\n"; } else { node* temp; temp=first; cout<<"List Contents:\n"; while( temp != NULL) { cout<<temp->info<<"\n"; temp=temp->next; } } } //function to delete element at specified position void DeleteElementAtPos(int pos) { int flag = 0; node* prev; node* temp; if( first == NULL ) { cout<<"List Empty\n"; } else if( pos >1 && first->next == NULL ) { cout<<"No element at specified position in list\n"; } else if( pos ==1) { temp=first; prev=temp; temp=temp->next; temp->prev=NULL; //re initiate first first=temp; prev->next=NULL; prev->prev=NULL; delete prev; prev= NULL; } // for all other positions else { temp=first; flag=1; while(flag < pos && temp->next != NULL) { prev=temp; temp=temp->next; flag++; } //check whether the specified position exists if( flag < pos) { cout<<"No element at specified position in list\n"; } //delete the node at the specified position else { prev->next = temp->next; temp->next->prev=prev; temp->next=NULL; temp->prev=NULL; delete temp; temp=NULL; } }//end of else for all other positions } void display_Prev_Next(int pos) { if(first == NULL) cout<<"List empty\n"; else if(first->next == NULL) cout<<"Only one element in List\n"; //for other valid cases else { node* temp=first; node* prev; int flag=1; while( flag < pos && temp->next!=NULL) { prev=temp; flag++; temp=temp->next; } //check whether its an invalid node position if(flag < pos) { cout<<"No element at specified position in the list\n"; } //if the position is valid else { cout<<"Previous Node:"<<prev->info<<"\n"; cout<<"Current Node:"<<temp->info<<"\n"; if(temp->next == NULL) cout<<"Next Node:End of List\n"; else cout<<"Next Node:"<<temp->next->info<<"\n"; } } //end of else other valid cases } //function to delete entire list and prevent memory leakage when exit is called void delete_Entire_list() { node* temp; node* curr; temp=first; if(first == NULL) return; while(temp->next != NULL) { curr=temp; temp=temp->next; delete curr; } delete temp; }

LinkedListImplementationUsing Structures

Singly Linked List with its operations :

/*************************************************************
* Author: Aniruddha S N
* 
*/

#include<iostream>
using namespace std;

// structure node
struct node
{
    int info;
    struct node* next;
};

//function declarations
 void display_list();
 void Insert_Element_List(int ele);
 void DeleteElementAtPos(int pos);

 //global variable first
 node* first = NULL;

 //main function
int main()
{    
    int ele = 0;
    int ch  = 0;
    int pos = 0;

//Menu to display single linked list operations
    while(1)
    {
        cout<<"**************LinkedListOperationsMenu*************\n";
        cout<<"1---->Insert an element in list\n";
        cout<<"2---->displayList\n";
        cout<<"3---->DeleteAnElement at specified position in list\n";
        cout<<"4---->exit\n";
        cout<<"***************************************************\n";
        cout<<"\n\n";
        cout<<"Enter your choice:\n";
        cin>>ch;

        //using switch case call respective functions for respective choices
        switch(ch)
        {
        case 1: cout<<"Enter the element to be inserted into list\n";
                cin>>ele;
                Insert_Element_List(ele);
                break;
        case 2:display_list();
               break;
        case 3:cout<<"Enter the position to delete elements\n";
               cin>>pos;
               DeleteElementAtPos(pos);
               break;
        default: exit(0);
        }

    }
     return 0;
}//end of main

//function to insert an element in singly linked list
void  Insert_Element_List(int ele)
{
    node* temp;
     if(first == NULL)
     {
         first= new node();
         first->info=ele;
         first->next=NULL;
     }
     else
     {
         node* temp1;
         temp1 = new node();
         temp=first;

     //find the end of list
         while( temp->next != NULL)
             temp=temp->next;

         temp1->info=ele;
         temp1->next=NULL;
     //attach the new node at the end of list
         temp->next=temp1;
     }
}


//function to display the elements in the list
void  display_list()
{
    if ( first == NULL)
        cout<<"list doesnt have any elements";

    else if(first->next == NULL)
    {
        cout<<"List Contents:\n";
        cout<<first->info<<"\n";
    }

    else
    {
        node* temp;
        temp=first;
        cout<<"List Contents:\n";
        while( temp != NULL)
        {
            cout<<temp->info<<"\n";
            temp=temp->next;
        }
    }
}

//function to delete element at specified position
void DeleteElementAtPos(int pos)
{
    int flag = 0;
    node* prev;
    node* temp;


    if( first == NULL )
    { cout<<"List Empty\n";
    }

    else if( pos >1 && first->next == NULL )
    {
        cout<<"No element at specified position in list\n";
    }
            
    else if( pos ==1)
      {
            temp=first;
            prev=temp;
            temp=temp->next;

            //re initiate first
            first=temp;
            delete prev;
            prev= NULL;
            
        }

    // for all other positions
    else
    {

        temp=first;
        flag=1;
        while(flag < pos && temp->next != NULL)
        {
           prev=temp;
           temp=temp->next;
           flag++;
        }
        //check whether the specified position exists
        if( flag < pos)
        {
            cout<<"No element at specified position in list\n";
        }
        //delete the node at the specified position
        else
        {
            prev->next = temp->next;
            delete temp;
            temp=NULL;
        }
    
    }//end of else for all other positions
}

Stack Implementation using arrays with Menu for various operations.

This Program gives stack implementation using arrays, max stack size input is considered as 100 during implementation, modify it suitably. #include<stdio.h> #include<conio.h> //Max stack size can be 99 //function declaration void push(int* top,int* stackarray,int size, int ele); void pop(int *top,int* stackarray); void display_stack(int stackarray[],int top); //main function void main() { int stackarr[100]; int top =-1; int size =0; int ele =0; int ch =0; printf("enter the stack size less than 100\n"); scanf("%d",&amp;size); //this menu will be displayed till user chooses to exit while(1) { printf("***************stackOperationsMenu*****************\n"); printf("1--------->push an element int stack\n"); printf("2--------->pop an element into stack\n"); printf("3--------->display stack contents\n"); printf("otherNum------>exit the program\n"); printf("Enter your choice\n"); scanf("%d", &ch); switch(ch) { case 1:printf("Enter the element to be pushed to stack\n"); scanf("%d", &ele); push( &top,stackarr,size,ele); break; case 2:pop( &top,stackarr); break; case 3: display_stack(stackarr,top); break; default:return; }//end of switch }//end of while }// end of main //function definitions void push(int* top,int* stackarray,int size, int ele) { if(*top == size-1) { printf("stack is full\nPlease pop some elements and try to insert again\n"); } else { *top=*top+1; stackarray[*top]=ele; } } void pop(int* top,int* stackarray) { if(*top == -1) printf(" stack is empty no element to pop\n"); else { printf("Popped element is %d",stackarray[*top--]); } } void display_stack(int stackarray[],int top) { int i=0; printf("Stack contents:\n"); for(int i=0;i&amp;lt;=top;i++) { printf("%d\n",stackarray[i]); }  }