Friday, November 8, 2019

Simple Queue Implementation using linked list in C++

#ifndef MYQUEUE_H
#define MYQUEUE_H


#include<iostream>
template<class T>
class MyQueue
{
private:
    struct Node
    {
        int data;
        struct Node* next=nullptr;
    };
    struct Node *front=nullptr;
    struct Node *rear=nullptr;
    struct Node *qPoint=nullptr;
public:
    struct Node* createNode();
    void insert(T e);
    struct Node* deQueue();
    void qDisplay();
    MyQueue();
};

#endif // MYQUEUE_H

template<class T>
MyQueue<T>::MyQueue()
{

}


template<class T>
typename MyQueue<T>::Node* MyQueue<T>::deQueue()
{
    if(!front){std::cout<<"Q emptry\n";return nullptr;}
 typename MyQueue<T>::Node* temp=front;
    front=front->next;
    rear=front;
    return temp;
}

template<class T>
typename MyQueue<T>::Node* MyQueue<T>::createNode()
{
 return new Node;
}
template<class T>
void MyQueue<T>::insert(T e)
{
    typename MyQueue<T>::Node*newNode=nullptr;
    try{
        newNode=createNode();
        newNode->data=e;
    }catch(const std::bad_alloc &e)
    {
        std::cout<<" Allocation Failed"<<e.what()<<"\n";
    }
    if (!front)
    {
        newNode->next=front=rear;
        qPoint=rear=front=newNode;
    }else {
        newNode->next=front;
        front=newNode;
    }
    //! to make it circular
   //! rear->next=front;

}
template<class T>
void MyQueue<T>::qDisplay()
{
    while(rear) {
    std::cout<<"Q Value= "<<rear->data<<"\n ";
    rear=rear->next;
    }
}




#include <iostream>
#include"myqueue.h"
using namespace std;

int main()
{
    MyQueue<int> mm;
    mm.insert(11);
    mm.insert(12);
    mm.insert(13);
    mm.insert(14);
    mm.insert(15);
//mm.qDisplay();
//! you can delete mode here
    std::cout<<"Q popped value ="<<mm.deQueue()->data<<std::endl;
    std::cout<<"Q popped value ="<<mm.deQueue()->data<<std::endl;
    std::cout<<"Q popped value ="<<mm.deQueue()->data<<std::endl;
    std::cout<<"Q popped value ="<<mm.deQueue()->data<<std::endl;
    std::cout<<"Q popped value ="<<mm.deQueue()->data<<std::endl;
    std::cout<<"Q popped value ="<<mm.deQueue()->data<<std::endl;
    return 0;
}

Time Complexity: Time complexity of both operations insert() and deQueue() is O(1) as we only change few pointers in both operations. There is no loop in any of the operations


No comments:

Post a Comment