Hot Topics
Data Structure
Dequeue using LinkedList
Algorithm
Create a node structure with data and next as two data members
Also create two pointers front and rear and set them to NULL
Check if the queue is empty
pushFront() – To push a node at front we have 2 case
When the dequeue is empty we create a new node and set front and rear pointers on it.
When there is atleast 1 node we create a new node and put it before the existing node and reassign front to the newly created node
pushRear() – To push at the rear we can have 2 cases
We are creating a new node in dequeue and setting both front and rear pointer on that node
We already have atleast one node in dequeue and we will add other nodes by creating a new node and set rear to the last created node
popFront() – To remove a node from front we have 2 cases
When the dequeue is empty we can’t delete any element
When there is atleast one node present we remove that node and reassign front to the next node of front
popRear() – To remove a node from rear we have 3 cases
When the dequeue is empty we can’t delete anything
When there is only one node present we have to remove that node and reassign front and rear to NULL to say that it is empty
When more than one node is present we have to traverse the list until we reach the second last node and then remove the last node and reassign rear to the second last node
getFront() – Get the data pointed by the front pointer when the dequeue is not empty
getRear() – Get the data pointed by the rear pointer when dequeue is not empty
display() – To display elements in dequeue attach a temp pointer to the front node and traverse until we reach the last node.
#include
struct QNode
{
int data;
QNode *next;
QNode(int d)
{
data = d;
next = NULL;
}
};
struct Queue
{
QNode *front, *rear;
Queue() { front = rear = NULL; }
bool isEmpty()
{
if (front == NULL && rear == NULL)
{
return true;
}
return false;
}
void pushFront(int x)
{
if (front == NULL)
{
QNode *temp = new QNode(x);
temp->data = x;
temp->next = NULL;
front = temp;
rear = temp;
}
else
{
QNode *temp = new QNode(x);
temp->data = x;
temp->next = front;
front = temp;
}
std::cout << "Element " << x << " is added at front" <data = x;
temp->next = NULL;
front = temp;
rear = temp;
}
else
{
QNode *temp = new QNode(x);
temp->data = x;
rear->next = temp;
rear = temp;
}
std::cout << "Element " << x << " is added at rear" << std::endl;
}
void popFront()
{
if (front == NULL)
{
std::cout << "Queue is empty" <next;
std::cout <data << " is deleted from front" << std::endl;
delete temp;
if (front == NULL)
{
rear = NULL;
}
}
}
void popRear()
{
if (front == NULL)
{
std::cout << "Queue is empty" <next == NULL)
{
std::cout <data <next != rear)
{
temp = temp->next;
}
std::cout <data << " is deleted from rear" <next = NULL;
}
}
void getFront()
{
if (isEmpty())
{
std::cout << "Dequeue is empty" << std::endl;
}
std::cout << "The data at front node is:" <data << std::endl;
}
void getRear()
{
if (isEmpty())
{
std::cout << "Dequeue is empty" << std::endl;
}
std::cout << "The data at rear node is:" <data << std::endl;
}
void display()
{
if (front != NULL)
{
QNode *temp = front;
while (temp != NULL)
{
std::cout <data <next;
}
std::cout << std::endl;
}
}
};
int main()
{
Queue q;
q.pushFront(10);
q.pushFront(20);
q.display();
q.pushRear(30);
q.pushRear(40);
q.display();
q.getFront();
q.getRear();
q.popFront();
q.display();
q.popRear();
q.display();
return 0;
}
Output
Element 10 is added at front
Element 20 is added at front
20 10
Element 30 is added at rear
Element 40 is added at rear
20 10 30 40
The data at front node is:20
The data at rear node is:40
20 is deleted from front
10 30 40
40 is deleted from rear
10 30
Automata Fixing