/*
This is a very good question. It took me good 2-3 hours to implement this.
push at rear and pop from front are O(1) operations, but to get minimum value is a really tough ask.
To implement this I used a separate queue, which is updated on push and pop operation to hold minimum value.
I have tested it in most scenarios but not all, if you find any scenario in which it will not work do let me know.
*/
#include<iostream.h>
#include<conio.h>
#include<process.h>
class Node
{
public:
int data;
Node *next;
Node()
{
next = NULL;
}
void initialiseNode(int val, Node *newNext)
{
data = val;
next = newNext;
}
};
class minimumQueue
{
public:
Node *minFront;
Node *minRear;
minimumQueue()
{
minFront = NULL;
minRear = NULL;
}
void minQueuePushRear(int val)
{
Node *newNode = new Node;
newNode->data =val;
if(minRear == NULL && minFront == NULL)
{
minRear = newNode;
minFront = newNode;
}
else
{
minRear->next = newNode;
minRear = minRear->next;
}
}
void minQueuePopFront()
{
Node *ptr = minFront;
if(minFront == minRear)
{
minFront = NULL;
minRear = NULL;
}
else
{
minFront = minFront-> next;
}
delete ptr;
}
};
class Queue
{
Node *front ;
Node *rear ;
minimumQueue minQueue;
public:
Queue()
{
front = NULL;
rear = NULL;
}
bool isEmpty()
{
if(front == NULL && rear == NULL)
{
return true;
}
else
{
return false;
}
}
void push_rear(int val)
{
Node *newNode = new Node;
newNode->data = val;
if(isEmpty())
{
front = newNode;
rear = newNode;
minQueue.minQueuePushRear(val);
}
else
{
rear->next = newNode;
rear = rear->next;
if(minQueue.minRear->data > val)
{
minQueue.minRear->data = val;
}
else
{
minQueue.minQueuePushRear(val);
}
//this is later on added code
if(val < minQueue.minFront->data)
minQueue.minFront->data = val;
}
}
void pop_front()
{
Node *deleteFront = front;
int val = front->data;
if(front == rear)
{
front = NULL;
rear = NULL;
}
else
{
front = front->next;
if(val == minQueue.minFront->data)
{
minQueue.minQueuePopFront();
}
}
delete deleteFront;
}
void display()
{
for(Node *ptr = front; ptr != rear; ptr = ptr->next)
cout<<" "<<ptr->data;
cout<<" "<<rear->data;
}
int get_min()
{
int value;
if(minQueue.minFront == NULL)
value = -1;
else if(minQueue.minFront->data > minQueue.minRear->data)
value = minQueue.minRear->data;
else
value = minQueue.minFront->data;
return value;
}
};
int main()
{
Queue q ;
int choice,value,min;
while(1)
{
system("CLS");
cout<<"1. PUSH REAR\n2. POP FRONT\n3. GET MIN\n4. DISPLAY\n5. EXIT\n\nchoice?";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter Value";
cin>>value;
q.push_rear(value);
break;
case 2:
q.pop_front();
break;
case 3:
min = q.get_min();
cout<<"\n Min is : "<<min;
getch();
break;
case 4:
q.display();
getch();
break;
case 5:
exit(0);
default:
cout<<"Invalid Input";
}
}
}
