Homework SourseConsider an extension of the queue abstract data type called
Solution
# include <stdlib.h>
# include <stdio.h>
struct node
{
int data;
struct node *ptr;
};
struct node *Real_Front = NULL;
struct node *Real_Rear =NULL;
struct node *Helper_Front = NULL;
struct node *Helper_Rear = NULL;
struct node *Front1 = NULL;
void print_queue()
{
Front1 = Real_Front;
if((Front1 == NULL) && (Real_Rear == NULL))
{
printf(\"\ Queue is Empty\ \");
return;
}
printf(\"\ Queue is :\ \");
while(Front1 != Real_Rear)
{
printf(\"%d -->\", Front1->data);
Front1 = Front1->ptr;
}
if(Front1 == Real_Rear)
printf(\"%d -->\", Front1->data);
}
void Enqueue(int num)
{
struct node *cur,*next,*prev,*temp,*temp1;
int value;
//Creating Node for insertion(Enqueue) in the list representation of Queue
temp = (struct node*)malloc(1 * sizeof(struct node));
temp->ptr = NULL;
temp->data = num;
temp1 = (struct node*)malloc(1 * sizeof(struct node));
temp1->data = num;
temp1->ptr = NULL;
if((Real_Rear == NULL) || (Helper_Rear == NULL)) //First Node insertion in Real Queue
{
if((Real_Rear == NULL) && (Real_Front == NULL))
{
Real_Front = temp;
Real_Rear = temp;
}
if((Helper_Rear == NULL) && (Helper_Front == NULL)) //First Node insertion in Helper Queue
{
Helper_Front = temp1;
Helper_Rear = temp1;
}
}
else
{
//Inserting Nodes other than first in Real queue
Real_Rear->ptr = temp;
Real_Rear = temp;
//Enqueue into Helper queue
Helper_Rear->ptr = temp1;
Helper_Rear = temp1;
/*
Logic Here is we are first inserting node into Helper Queue and if enqueued element is having greater elements ahead
we are removing that elements.
*/
cur = Helper_Front;
for(;cur->ptr != Helper_Rear; cur = cur->ptr)
{
for(prev = cur->ptr; prev != Helper_Rear;prev = prev->ptr)
{
if(cur->data > prev->data)
{
value = cur->data;
cur->data = prev->data;
prev->data = value;
}
}
}
//Removing greater elements ahead after enqued the element
cur = Helper_Front;
while(cur->data != num)
{
cur = cur->ptr;
}
cur->ptr = Helper_Rear;
prev = cur->ptr;
while(prev != Helper_Rear)
{
next = prev->ptr;
free(prev);
prev = next;
}
cur = NULL;
}
}
void Dequeue ()
{
Front1 = Real_Front;
int dequeue_ele;
struct node *cur,*prev;
//Condition for Queue is empty
if(Front1 == NULL)
{
printf(\"Queue is Empty\ \");
return;
}
else
{
//Dequeue an element from real queue
if(Front1->ptr != NULL)
{
Front1 = Front1->ptr;
dequeue_ele = Real_Front->data;
printf(\"\ Value Dequeued: %d\", Real_Front->data);
free(Real_Front);
Real_Front = Front1;
}
else
{
dequeue_ele = Real_Front->data;
printf(\"\ Value Dequeue: %d\", Real_Front->data);
free(Real_Front);
Real_Front = NULL;
Real_Rear = NULL;
}
//Dequeue an element from Helper Queue
/*
Purpose of below snippet is that if the element dequeue from real queue then it should not present
in Helper queue also.Hence removing from Helper queue
*/
if(Helper_Front->data == dequeue_ele)
{
if(Helper_Front->ptr == Helper_Rear)
return;
Helper_Front->data = Helper_Front->ptr->data;
cur = Helper_Front->ptr;
Helper_Front->ptr = cur->ptr;
free(cur);
return;
}
prev = Helper_Front;
while((prev->ptr != Helper_Rear) && (prev->ptr->data != dequeue_ele))
prev = prev->ptr;
if(prev->ptr == Helper_Rear)
return;
cur = prev->ptr;
prev->ptr = prev->ptr->ptr;
free(cur);
}
}
int Findmin()
{
return Helper_Front->data; // Return min element from Helper
}
int main()
{
int num,min_ele;
Real_Front=Real_Rear=Helper_Front=Helper_Rear=NULL;
char choice;
int test;
do
{
printf(\"Enter the Below choice \ \");
printf(\" 1. Enqueue \ 2. Dequeue \ 3. Findmin \ \");
scanf(\"%d\", &test);
if(test == 1)
{
printf(\"\ Enter element into queue\ \");
scanf(\"%d\", &num);
Enqueue(num); //Enqueue the elements
print_queue();
}
else if(test == 2)
{
Dequeue(); //Dequeue the elements
print_queue();
}
else if(test == 3)
{
min_ele = Findmin(); //Findmin element from Helper queue
printf(\"\ Min element is %d\", min_ele);
}
else
printf(\"Invalid Choice. Please select proper choice\ \");
printf(\"\ Do You want to Continue Y/N :\");
scanf(\" %c\",&choice);
}while((choice==\'Y\') || (choice==\'y\'));
return 0;
}
-----------------------------------------------------------------------------------------------------------------------------------------------------------------
1)Describe how the DEQUEUEand FINDMIN operation are implimented in this data structure
Answer: Please see above code for explanation
------------------------------------------------------------------------------------------------------------------------------------------------------------------
2) Give the worst case running time for each ENQUEUE,DEQUEUE and FINDMIN using this data structure
Ans:
Worst case complexities are
a) ENQUEUE - O(1) as we are simply enqueing data using rear pointer
b) DEQUEUE - O(1) as we simply dequeue using Front pointer
c) FINDMIN - O(1) as we enqueue the element and bringing minimum element at front while deleting all the elements greater than enqueuing element.
-----------------------------------------------------------------------------------------------------------------------------------------------------------------
3) Give an argument using the potential method to show that any sequence of n ENQUEUE,DEQUEUE and FINDMIN operations requires only O(n) time Or Namely the
amortized complexity of these operations is O(1)
Ans: From (2)
Complexity of ENQUEUE - O(1)
To enqueue n such elements in queue requires
n* O(1) operations
Hence total complexity of ENQUEUE is
ENQUEUE - O(n) as we have to do n such operations
same for DEQUEUE() and FINDMIN()
N dequeue elements complexity is
DEQUEUE - n* O(1)
- O(n)
FINDMIN - n * O(1)
- O(n)
Amortized complexity from above for ENQUEUE, DEQUEUE and FINDMIN is O(1).
-------------------------------------------------------------------------------------------------------------------------------------------------------------------
