Hot Topics
Data Structure
Queue using Linked List
As we have seen previously in queue we use two pointers front and rear where front denotes the first element and rear the last element in queue.
push():To push element in queue we need to add a new node after the rear pointer and point the rear pointer to newly created node.
pop():To remove element from queue the node pointed by front pointer is removed and the front pointer will be pointing to the next node.
Algorithm
Create a structure with data members of a linked list and a constructor that sets data as the given data and points the next pointer to NULL.
Create a structure for queue which has qfront and rear as its data members.The constructor should initialize qfront and rear as NULL because at first queue is empty.
To push a node into queue create a node with the given data.If the queue is empty i.e the qfront and rear of queue is pointing to NULL then set the qfornt and rear to the temp node and return.If the queue has atleast one node then at rear’s next put the new node and point temp to new node.
To pop a node if qfront is set to NULL or both qfront and rear is set to NULL then return.If the node is present then copy the node denoted by qfront into another pointer and move the qfront pointer to the next node and delete the copied node.
To display all the nodes in queue attach a pointer to first node denoted by qfront and print the nodes until the attached pointer reaches NULL.
Lorem ipsum dolor sit amet, consectetur adipiscing elit. Ut elit tellus, luctus nec ullamcorper mattis, pulvinar dapibus leo.
#include
using namespace std;
// Creating a linked list with its data members
struct QNode
{
int data;
QNode *next;
QNode(int d)
{
data = d;
next = NULL;
}
};
// Initializing queue
struct Queue
{
// Taking two pointers to denote front and rear of queue
QNode *front, *rear;
Queue() { front = rear = NULL; }
bool isempty()
{
if (front == NULL && rear == NULL)
return true;
else
return false;
}
// Function to push node into queue
void push(int x)
{
// Create a new LL node
QNode *temp = new QNode(x);
// If queue is empty, then new node is front and rear both
if (rear == NULL)
{
front = rear = temp;
return;
}
// Add the new node at the end of queue and change rear
rear->next = temp;
rear = temp;
}
// Function to remove a key from given queue q
void pop()
{
// If queue is empty, return NULL.
if (front == NULL)
return;
// Store previous front and
// move front one node ahead
QNode *temp = front;
front = front->next;
// If front becomes NULL, then
// change rear also as NULL
if (front == NULL)
rear = NULL;
delete (temp);
}
// function to show the element at front
void showfront()
{
if (isempty())
cout << "Queue is empty\n"
<< endl;
else
cout << "Queue front :" <data << endl;
}
// Function to display elements in the queue
void display()
{
// Checking if the queue is empty
if (isempty())
cout << "Queue is empty\n"
<< endl;
else
{
QNode *ptr = front;
cout << "The elements in queue are" << endl;
while (ptr != NULL)
{
cout <data <next;
}
cout << endl;
}
}
};
// Driven Program
int main()
{
Queue q;
q.display();
q.push(10);
q.push(20);
q.push(30);
q.push(40);
q.push(50);
q.display();
q.pop();
q.display();
q.push(60);
q.display();
q.showfront();
cout << "Queue Rear : " <data;
}
Output
Queue is empty
The elements in queue are
10 20 30 40 50
The elements in queue are
20 30 40 50
The elements in queue are
20 30 40 50 60
Queue front :20
Queue Rear : 60
Automata Fixing