FIFO First In First Out
Since the time complexity for the both Enqueue and Dequeue operations is O(1), So, You can't traverse the whole list to perform any of the enqueue/dequeue operations. Hence, you have to maintain two pointers for that, i.e. a head and tail pointer.
Now, suppose in singly linked list you want to delete element from tail side and insert from head side, than you easily can perform the insertion operation but, for deletion you have to delete the last node and for that you have to shift tail pointer back in list which is not possible(so that tail pointer point to last second element), without traversing the whole list, And for traversing time complexity becomes O(n), which is not possible for Queue.
So, Delete from Head side and insert from tail side i.e. head as front end and tail as rear end.
#include<conio.h>
#include<stdlib.h>
#include<stdio.h>
struct node
{
int data;
struct node *next;
};
struct node *newnode, *temp;
void enqueue(struct node **f, struct node **r)
{
int data,choice=1;
while(choice==1)
{
newnode=(struct node*)malloc(sizeof(struct node));
printf("Enter the data: ");
scanf("%d",&newnode->data);
newnode->next=0;
if(*f==0 && *r==0)
{
*f = newnode;
*r = newnode;
}
else
{
(*r)->next=newnode;
*r=newnode;
}
printf("want another element to be inserted(0,1): ");
scanf("%d",&choice);
}
}
void dequeue(struct node **f, struct node **r)
{
int choice=1;
while(choice==1)
{
if(*f==0 && *r==0)
{printf("Queue is Empty\n");break;}
else if(*f==*r)
{
printf("Deleted element is: %d",(*f)->data);
free(*f);
*f=0;
*r=0;
}
else
{
printf("Deleted element is: %d",(*f)->data);
temp=*f;
*f=(*f)->next;
free(temp);
}
printf("\nWant another element to be deleted(0,1): ");
scanf("%d",&choice);
}
}
void display(struct node *f, struct node *r)
{
temp=f;
if(f==0 && r==0)
printf("Queue is empty\n");
else
{
printf("Queue is:\n");
while(temp!=0)
{
printf("%d\n",temp->data);
temp=temp->next;
}
}
}
void peek(struct node *f, struct node *r)
{
if(f==0 && r==0)
printf("Queue is empty\n");
else
printf("The element at the top of Queue is: %d\n", f->data);
}
int main()
{
int ch,choice=1;
struct node *frnt, *rear;
frnt=0;rear=0;
while(choice==1){
printf("\nEnter 1. to enqueue(insert in queue) \n");
printf("Enter 2. to dequeue (to delete from queue)\n");
printf("Enter 3. to display \n");
printf("Enter 4. to peek (to show the element at front) \n choice: ");
scanf("%d",&ch);
if(ch==1)
enqueue(&frnt, &rear);
else if(ch==2)
dequeue(&frnt, &rear);
else if(ch==3)
display(frnt, rear);
else if(ch==4)
peek(frnt, rear);
else
printf("invalid choice:");
printf("\nDo you want to continue(0,1): ");
scanf("%d",&choice);
}
}
Comments
Post a Comment