Objective: Experiment with Lists, Stacks, and Queues:

Implement and demonstrate fundamental operations on linked lists, queues, and stacks.

Gain hands$-$on experience with template classes in C$++.$

Understand and apply basic algorithms for list manipulations.

OS task manager $($Real world Engineering Application$)$:

In operating system implementation, the concepts of stacks, queues, and linked lists play crucial roles in

managing various aspects of system resources, tasks, and threads.

Linked lists provide dynamic structures for maintaining lists of processes and threads allowing for flexible and

dynamic allocation and deallocation of resources

Stacks are employed to manage function calls and system$-$level data, ensuring a Last$-$In$-$First$-$Out $($LIFO$)$

order, which is essential for tasks such as recursion, interrupt handling, and maintaining system states

Queues, on the other hand, facilitate orderly task scheduling and prioritization.

Linked List Operations:

Implement a generic linked list class with the following operations:

Insertion at the beginning of the list.

Insertion at a specific position.

Deletion of the front node.

Deletion by value.

Deletion of the last node.

Display the elements in the list.

Retrieve the front node.

Retrieve the size of the list.

Retrieve and delete the smallest entry.

Queue Operations:

Implement a generic queue class using the linked list implemented in step $1$ with the following operations:

Enqueue operation $($add an element to the queue$).$

Dequeue operation $($remove the front element$).$

Display the elements in the queue.

Remove the last node in the queue.

Delete the largest entry from the queue.

Stack Operations:

Implement a generic stack class using the linked list implemented in step $1$ with the following operations:

Push operation $($add an element to the stack$).$

Pop operation $($remove the top element$).$

Display the elements in the stack.

Additional Features:

Implement the main function to demonstrate the operations on the above classes.

Perform tests with integer, string, and any other data types of your choice.

Include validations for each operation to handle edge cases $($e$.$g$.,$ removing from an empty list$).$

Submission:

Submit the complete $C++$ code file.

Provide comments for each function to explain the purpose and functionality.

Include test cases in the main function to showcase the correctness of your implementations.

Clearly indicate the results of each operation in your output.

Provided Code:

#include

#include A

using namespace std;

$//$ Node class:

template

class Node $\{$

public:

T data;

Node$*$ next;

Node$*$ previous;

$//$ Constructor to initialize the node with a given value

Node$($T value$)\{$

data $=$ value;

next $=$ nullptr;

previous $=$ nullptr;

$\}$

$\}$;

$//$ Linked list class:

template

class LinkedList $\{$

public:

$//$ Default constructor

LinkedList$()\{$

head $=$ nullptr;

$\}$

$//$ Insert at the beginning of the list

void insert$($T value$)\{$

Node$*$ newNode $=$ new Node$($value$)$;

newNode$->$next $=$ head;

head $=$ newNode;

$\}$

$//$ Remove the front node in the list

void removeFront$()\{$

if $($head $!=$ nullptr$)\{$

Node$*$ temp $=$ head;

head $=$ head$->$next;

temp$->$next $=$ nullptr; $//$ Disconnect the removed node from the list

delete temp;

$\}$

$\}$

$//$ Remove the last node in the list

void removeEnd$()\{$

if $($head $==$ nullptr$)\{$

return;

$\}$

if $($head$->$next $==$ nullptr$)\{$

delete head;

head $=$ nullptr;

return;

$\}$

Node$*$ current $=$ head;

while $($current$->$next$->$next $!=$ nullptr$)\{$

current $=$ current$->$next;

$\}$

delete current$->$next;

current$->$next $=$ nullptr;

$\}$

$//$ Display the elements in the list

void display$()\{$

Node$*$ current $=$ head;

while $($current $!=$ nullptr$)\{$

cout $$ current$->$data ;

current $=$ current$->$next;

$\}$

cout $$ endl;

$\}$

$//$ Get the front node

Node$*$ getFront$()\{$

return head;

$\}$

private:

Node$*$ head;

$\}$;

$//-----------------------------------------------------$

$//$ Queue class using linked list

template

class Queue $\{$

public:

$//$ Enqueue operation

void enqueue$($T value$)\{$

list.insert$($value$)$;

$\}$

$//$ Dequeue operation

void dequeue$()\{$

list.removeEnd$()$;

$\}$

$//$ Display the elements in the queue

void display$()\{$

list.display$()$;

$\}$

$//$ Remove the last node in the queue: FIFO

void removeEnd$()\{$

list.removeEnd$()$;

$\}$

private:

LinkedList list;

$\}$;

$//-----------------------------------------------------$

$//$ Stack class using linked list

template