Write a program to implement queue data structure using linked list.
A stack is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle. In other words the item which in inserted(pushed) last, will be the first item to be popped.
Operations to be performed.
1] Enqueue if queue is not full
2] Dequeue if queue is not empty
A queue has two end. one for entering and one for exit.
Queue follows the First In First Out(FIFO) rule – the item that goes in first is the item that comes out first too.
#include<stdio.h> #include<stdlib.h> #define MAX 5 unsigned int inc = 0; typedef struct SingleLinkList { int num; struct SingleLinkList *next; }SLL; void enqueue(int,SLL**); int dequeue(SLL**); int top_of_queqe(SLL*); int print(SLL*); int main() { SLL *hp = 0; int n,op; printf("1] Enqueue 2] Dequeue 3] Top of Queue 4] Print 0] Exit\n"); scanf("%d",&op); while(op != 0) { switch(op) { case 1: if(inc == 5) { printf("Queue is full\n"); break; } printf("Enter Value to Enqueue = "); scanf("%d",&n); enqueue(n,&hp); printf("Count = %d\n",print(hp)); break; case 2: if(inc == 0) { printf("Queue Empty\n"); break; } printf("Dequeued Value is = %d\n",dequeue(&hp)); printf("Count = %d\n",print(hp)); break; case 3: printf("Top of Queue = %d\n",top_of_queue(hp)); break; case 4: printf("Count = %d\n",print(hp)); break; default: printf("Invalid option.\n"); } printf("1] Enqueue 2] Dequeue 3] Top of Queue 4] Print 0] Exit\n"); scanf("%d",&op); } return 0; } void enqueue(int n,SLL**p) { SLL *p1,*p2; p1 = (SLL*)malloc(sizeof(SLL)); p1->num = n; inc++; if(*p == 0) { p1->next = *p; *p = p1; } else { p2 = *p; while(p2->next) p2 = p2->next; p1->next = p2->next; p2->next = p1; } } int dequeue(SLL**p) { SLL *p1; int n; p1 = *p; n = p1->num; *p = p1->next; free(p1); inc--; return n; } int top_of_queue(SLL*p) { return (p->num); } int print(SLL*p) { unsigned int c = 0; while(p) { c++; printf("%d ",p->num); p = p->next; } printf("\n"); return c; }
Output
1] Enqueue 2] Dequeue 3] Top of Queue 4] Print 0] Exit 1 Enter Value to Enqueue = 10 10 Count = 1 1] Enqueue 2] Dequeue 3] Top of Queue 4] Print 0] Exit 1 Enter Value to Enqueue = 20 10 20 Count = 2 1] Enqueue 2] Dequeue 3] Top of Queue 4] Print 0] Exit 1 Enter Value to Enqueue = 30 10 20 30 Count = 3 1] Enqueue 2] Dequeue 3] Top of Queue 4] Print 0] Exit 1 Enter Value to Enqueue = 40 10 20 30 40 Count = 4 1] Enqueue 2] Dequeue 3] Top of Queue 4] Print 0] Exit 1 Enter Value to Enqueue = 50 10 20 30 40 50 Count = 5 1] Enqueue 2] Dequeue 3] Top of Queue 4] Print 0] Exit 1 Queue is full 1] Enqueue 2] Dequeue 3] Top of Queue 4] Print 0] Exit 2 Dequeued Value is = 10 20 30 40 50 Count = 4 1] Enqueue 2] Dequeue 3] Top of Queue 4] Print 0] Exit 2 Dequeued Value is = 20 30 40 50 Count = 3 1] Enqueue 2] Dequeue 3] Top of Queue 4] Print 0] Exit 2 Dequeued Value is = 30 40 50 Count = 2 1] Enqueue 2] Dequeue 3] Top of Queue 4] Print 0] Exit 2 Dequeued Value is = 40 50 Count = 1 1] Enqueue 2] Dequeue 3] Top of Queue 4] Print 0] Exit 2 Dequeued Value is = 50 Count = 0 1] Enqueue 2] Dequeue 3] Top of Queue 4] Print 0] Exit 2 Queue Empty 1] Enqueue 2] Dequeue 3] Top of Queue 4] Print 0] Exit 2 Queue Empty 1] Enqueue 2] Dequeue 3] Top of Queue 4] Print 0] Exit 0