FoodForFutureGeeks

Thursday 10 January 2013

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;
}

1 comment:

  1. some of the cout statements have shifted to next line, please ensure that they end on same line after copying code, else u mite get some errors.

    ReplyDelete