AVAILABLE: 5
The process of storing queue elements using pointers is similar to the operations on a singly linked list, utilizing operations like adding to the end and removing from the beginning. The operations that can be performed on a queue represented with a linked list include:
1. Declaring a Queue
Every queue has elements (fields) such as the front position, back position, queue elements, and a pointer to the next element. Below is the declaration of a queue stored using pointers:
struct node
{
int info;
struct node *next;
};
node *head, *tail, *newnode, *ptr;
2. Queue Initialization
The initialization process for a queue stored in pointers involves assigning NULL to the head and tail pointers, indicating that the front and back pointers do not yet point to any elements.
void initialize()
{
head = NULL;
tail = NULL;
}
3. Check if Queue is Empty
This function is used to check whether a queue is empty. It is useful during the dequeue process—when an element is about to be removed, the function checks if the queue contains any data. The function returns true if both head and tail are NULL.
int isEmpty()
{
if ((head == NULL) && (tail == NULL))
{
cout << "\nQueue is empty";
return 0;
}
else
{
return 1;
}
}
4. Enqueue Operation
The enqueue process involves adding a new element to the back of the queue (by connecting the next field of the current tail to the new node). Afterward, the tail pointer is updated to point to the new node. This process is similar to appending to the end of a singly linked list.
void enqueue(int item)
{
newnode = new(node);
newnode->info = item;
if ((head == NULL) && (tail == NULL))
{
head = newnode;
tail = newnode;
newnode->next = NULL;
}
else
{
tail->next = newnode;
newnode->next = NULL;
tail = newnode;
}
}
5. Dequeue Operation
The dequeue process involves removing the data pointed to by the front pointer and then deleting the front pointer. The front pointer is updated to the next element in the queue. This process is only performed if the linked list is not empty, and it is similar to removing the first element of a singly linked list.
void dequeue()
{
if (head == tail)
{
head = NULL;
tail = NULL;
}
else
{
head = head->next;
}
}
Complete Program Implementation:
#include <stdio.h>
#include <conio.h>
#include <process.h>
#include <iostream.h>
struct node
{
int info;
struct node *next;
};
node *head, *tail, *newnode, *ptr;
void menu();
void display();
int isEmpty();
void enqueue(int);
void dequeue();
void initialize()
{
head = NULL;
tail = NULL;
}
void main()
{
clrscr();
initialize();
menu();
}
void menu()
{
int choice, item;
cout << "MENU";
cout << "\n1. Add";
cout << "\n2. Remove";
cout << "\n3. Display";
cout << "\n4. Exit";
cout << "\nEnter your choice: ";
cin >> choice;
switch (choice)
{
case 1:
clrscr();
cout << "\nEnter data to add: ";
cin >> item;
enqueue(item);
clrscr();
cout << "\nData in the queue:\n";
display();
getch();
clrscr();
menu();
break;
case 2:
clrscr();
if (isEmpty() == 1)
{
dequeue();
if (isEmpty() == 1)
{
cout << "\nData in the queue:\n";
display();
}
}
getch();
clrscr();
menu();
break;
case 3:
clrscr();
if (isEmpty() == 1)
{
cout << "Data in the queue:\n";
display();
}
getch();
clrscr();
menu();
break;
case 4:
exit(1);
default:
clrscr();
cout << "Invalid choice\n\n";
menu();
}
}
int isEmpty()
{
if ((head == NULL) && (tail == NULL))
{
cout << "\nQueue is empty";
return 0;
}
else
{
return 1;
}
}
void enqueue(int item)
{
newnode = new(node);
newnode->info = item;
if ((head == NULL) && (tail == NULL))
{
head = newnode;
tail = newnode;
newnode->next = NULL;
}
else
{
tail->next = newnode;
newnode->next = NULL;
tail = newnode;
}
}
void dequeue()
{
if (head == tail)
{
head = NULL;
tail = NULL;
}
else
{
head = head->next;
}
}
void display()
{
int i;
ptr = head;
i = 1;
while (ptr != NULL)
{
cout << "\nNode " << i << " : " << ptr->info;
ptr = ptr->next;
i++;
}
}