In computing, queue is linear data structures that follow the First in First out (FIFO) principle. They are used to perform enqueuing and dequeuing operation.
Queue is linear data structures that follows the first in, first our principle (FIFO), which means that the element added first to the queue will be the first removed.
A linked queue consists of two fields: data and next (storing address of next node). The data field contains the value assigned to the node, and the nest points to the node containing the next item. There are two pointers in a linked queue, namely the front pointer contains the address of the first element of the queue, while the rear pointer contains the address of the last element.
When both front and rear points to NULL, it indicates the the queue is empty. Insertion takes place at the rear end and deletion at the front.
When an element is inserted into a linked queue, a new element is added to the end. This element become the queue's last element.
*ptr -> data = val;
if(front == NULL){
front = ptr;
rear = ptr;
front -> next = NULL;
rear -> next = NULL;
}rear -> next = ptr;
rear = ptr;#include<stdio.h>
#include<stdlib.h>
struct node{
int data;
struct node *next;
};
struct node *front;
struct node *rear;
void insert(struct node *ptr, int item){
ptr = (struct node *) malloc (sizeof(struct node));
if(ptr == NULL){
print("\nQUEUE IS OVERFLOW");
return;
}else{
ptr -> data = item;
if(front == NULL){
front = ptr;
rear = ptr;
front -> next = NULL;
rear -> next = NULL;
}else{
rear -> next = ptr;
rear = ptr;
rear -> next = NULL;
}
}
}
void delete(struct node *ptr){
if(front == NULL){
printf("\nQUEUE IS EMPTY");
return;
}else{
ptr = front;
front = front -> next;
free(ptr);
}
}
int main(){
struct node *head = NULL;
insert(head, 12);
insert(head, 34);
insert(head, 7);
printf("Front element of the queue %d\n", front -> data);
delete(head);
printf("Front element of the queue %d\n", front -> data);
return 0;
}
By implementing a queue using a linked list, we can allocate memory dynamically as needed. When implement a queue using a linked list, the FIFO principle will not change.
The enqueue(PUSH) function adds an element to the end of the queue. It takes O(1) time. A rear pointer can be used to track the last element.
A dequeue function removes the first element of a queue in O(1) time. To dequeue, the queue must contain at least one element, otherwise an underflow will occur.
We use the print function to display the content of a queue. Since we iterate over each element of the queue, the time complexity of the print function is O(n).
// Method 1
#include<stdio.h>
#include<stdlib.h>
struct node{
int data;
struct node *next;
};
struct node * front = NULL;
struct node * rear = NULL;
void enqueue(int value){
struct node *ptr;
ptr = (struct node*) malloc(sizeof(struct node));
ptr -> data = value;
ptr -> next = NULL;
if((front == NULL) && (rear == NULL)){
front = rear = ptr;
}else{
rear -> next = ptr;
rear = ptr;
}
printf("\nNode is Inserted\n");
}
int dequeue(){
if(front == NULL){
printf("\nQUEUE IS EMPTY");
return -1;
}else{
struct node *temp = front;
int temp_data = front -> data;
front = front -> next;
free(temp);
return temp_data;
}
}
void display(){
struct node *temp;
if((front == NULL) && (rear == NULL)){
printf("\nQUEUE IS EMPTY");
}else{
printf("The Queue is \n\n");
temp = front;
while(temp){
printf("%d-->", temp -> data);
temp = temp -> next;
}
printf("NULL\n\n");
}
}
int main(){
int choice, value;
printf("\nImplementation of Queue using Linekd List\n");
while(choice != 4){
printf("1.Enqueue\n2.Dequeue\n3.Display\n4.Exit\n\nEnter your choice : ");
scanf("%d", &choice);
switch(choice){
case 1:
printf("\nEnter the value to insert : ");
scanf("%d", &value);
enqueue(value);
break;
case 2:
printf("Popped Elemetn is : %d\n", dequeue());
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("\nWrong Choice\n");
}
}
return 0;
}
// Method 2
#include<stdio.h>
#include<stdlib.h>
struct node{
int data;
struct node *next;
};
typedef struct node NODE;
NODE *front = NULL, *rare = NULL;
void push(){
NODE *ptr;
int item;
printf("\nEnter the item : ");
scanf("%d", &item);
ptr = (NODE*)malloc(sizeof(NODE));
ptr->data = item;
ptr->next = NULL;
if(front==NULL){
front = ptr;
rare = ptr;
}
else{
rare->next = ptr;
rare = ptr;
}
}
void display(){
NODE *temp=front;
while (temp!=rare)
{
printf("%d ", temp->data);
temp = temp->next;
}
printf("%d ", temp->data);
}
void pop(){
NODE *temp = front;
while(temp->next != rare){
temp = temp->next;
}
temp->next = NULL;
free(rare);
rare = temp;
}
int main(){
char ch;
int choice;
do
{
printf("\n1.PUSH\n2.POP\n3.Display\nEnter Your Choice : ");
scanf("%d", &choice);
switch (choice)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
default:
printf("Please Choose Right Option\n");
break;
}
printf("\nDo You want to perform more Operation press[y/Y] : ");
scanf("%s", &ch);
} while (ch=='y' || ch=='Y');
return 0;
}
Comments
Oops!