Concept: Queue is an abstract data structure, somewhat similar to Stacks. Unlike stacks, a queue is open at both its ends. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue). Queue follows First-In-First-Out methodology, i.e., the data item stored first will be accessed first. Queue operations may involve initializing or defining the queue, utilizing it, and then completely erasing it from the memory. Here we shall try to understand the basic operations associated with queues.
• enqueue () − add (store) an item to the queue.
• dequeue () − remove (access) an item from the queue.
Few more functions are required to make the above-mentioned queue operation efficient. These are
• peek() − Gets the element at the front of the queue without removing it.
• isfull() − Checks if the queue is full.
• isempty() − Checks if the queue is empty
ALGORITHM:
1. Define a struct for each node in the queue. Each node in the queue contains data and link to the next node. Front and rear pointer points to first and
last node inserted in the queue.
2. The operations on the queue are
a. INSERT element into the queue
b. DELETE element out of queue
3. INSERT element INTO queue
a. Enter the element to be inserted into queue
b. If TOP is NULL
i. The input element is the first node in queue.
ii. The link of the node is NULL.
iii. TOP points to that node.
c. If TOP is NOT NULL
i. The link of TOP points to the new node.
ii. TOP points to that node.
4. DELETE DATA FROM queue
a. If TOP is NULL
i. the queue is empty
b. If TOP is NOT NULL
i. The link of TOP is the current TOP.
ii. The pervious TOP is popped from queue.
5. The queue represented by linked list is traversed to display its content.
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
class node
{
public: class node *next;
int data;
};
class queue : public node
{
node *head;
int front,rare;
public: queue()
{
front=-1;
rare=-1;
}
void enqueue(int x)
{
if (rare < 0 )
{
head =new node;
head->next=NULL;
head->data=x;
rare ++;
}
else
{
node *temp,*temp1;
temp=head;
if(rare >= 4)
{
cout <<"queue over flow";
return;
}
rare++;
while(temp->next != NULL)
temp=temp->next;
temp1=new node;
temp->next=temp1;
temp1->next=NULL;
temp1->data=x;
}
}
void display()
{
node *temp;
temp=head;
if (rare < 0)
{
cout <<" queue under flow"; return;
}
while(temp != NULL)
{
cout <<temp->data<< " ";
temp=temp->next;
}
}
void dequeue()
{
node *temp;
temp=head;
if( rare < 0)
{
cout <<"queue under flow";
return;
}
if(front == rare)
{
front = rare =-1;
head=NULL;
return;
}
front++;
head=head->next;
}
};
main()
{
queue s1;
int ch;
clrscr();
cout<<"\n\n\tQUEUE USING LINKED LIST";
cout <<"\n1.enqueue\n2.dequeue\n3.DISPLAY\n4.EXIT";
while(1)
{
cout<<"\n enter your choice:";
cin >> ch;
switch(ch)
{
case 1: cout <<"\n enter a element";
cin >> ch;
s1.enqueue(ch);
break;
case 2: s1.dequeue();
break;
case 3: s1.display();
break;
case 4: exit(0);
}
}
return (0);
}
