In this task, we are given a complete implementation of a doubly linked list, and we are asked to implement $2$ data structures, namely Queue, and Stack.

A queue is a FIFO $($first$-$in$-$first$-$out$)$ container, with operations enqueue, and dequeue for putting in data at the front of the queue, and taking out data from the back of the queue, respectively.

A stack is a LIFO $($last$-$in$-$first$-$out$)$ container, with operations push and pop, for putting in data at the front$/$top of the stack, and taking out data from the front$/$top$,$ respectively.

Both data structures have a peek method, to see the value at the front$/$top$,$ but not take it out, as well as the usual size and isEmpty methods.#ifndef LINKED$\_$LIST$\_$H

#define LINKED$\_$LIST$\_$H

#include

#include

#include

template

class LinkedList;

template

struct Link$\{$

T data;

Link$*$ next;

Link$*$ prev;

Link$()\{$

data $=0$;

next $=$ nullptr;

prev $=$ nullptr;

$\}$

Link$($T data$)\{$

this$->$data $=$ data;

next $=$ nullptr;

prev $=$ nullptr;

$\}$

$\}$;

template

std::ostream& operator$<<($std::ostream& os$,$ const LinkedList& list$)\{$

Link$*$ curr $=$ list.front;

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

os $<<$ curr$->$data;

if $($curr$->$next $!=$ nullptr$)$ os $<<","$;

curr $=$ curr$->$next;

$\}$

return os;

$\}$

template

class LinkedList$\{$

protected:

Link$*$ front;

Link$*$ back;

int count;

public:

LinkedList$()\{$

front $=$ nullptr;

back $=$ nullptr;

count $=0$;

$\}$

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

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

$//$ Appending to an empty list

front $=$ new Link$($value$)$;

back $=$ front;

$\}$

else$\{$

$//$ Appending to list with elements

Link$*$ temp $=$ new Link$($value$)$;

temp$->$prev $=$ back;

back$->$next $=$ temp;

back $=$ temp;

$\}$

count$++$;

$\}$

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

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

$//$ Prepending to an empty list

front $=$ new Link$($value$)$;

back $=$ front;

$\}$

else$\{$

$//$ Prepending to a list with elements

Link$*$ temp $=$ new Link$($value$)$;

temp$->$next $=$ front;

front$->$prev $=$ temp;

front $=$ temp;

$\}$

count$++$;

$\}$

T removeFirst$()\{$

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

throw std::logic$\_$error$("$Can not remove from an empty list"$)$;

$\}$

if $($count $==1)\{$

T x $=$ front$->$data;

delete front;

front $=$ nullptr;

back $=$ nullptr;

count$--$;

return x;

$\}$

else$\{$

T x $=$ front$->$data;

Link$*$ old $=$ front;

front $=$ front$->$next;

front$->$prev $=$ nullptr;

delete old;

count$--$;

return x;

$\}$

$\}$

T peek$()$ const $\{$

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

throw std::logic$\_$error$("$Can not peek into an empty list"$)$;

$\}$

return front$->$data;

$\}$

T removeLast$()\{$

$//$ Your code goes here

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

throw std::logic$\_$error$("$Can not remove from an empty list"$)$;

$\}$

if $($front $==$ back$)\{$

T x $=$ front$->$data;

delete front;

front $=$ nullptr;

back $=$ nullptr;

count$--$;

return x;

$\}$ else$\{$

T x $=$ back$->$data;

Link$*$ old $=$ back;

back $=$ back$->$prev;

back$->$next $=$ nullptr;

delete old;

count$--$;

return x;

$\}$

$\}$

int size$()$ const $\{$

return count;

$\}$

bool isEmpty$()$ const $\{$

return count $==0$;

$\}$

void reverse$()\{$

Link$*$ oldFront $=$ front;

front $=$ back;

back $=$ oldFront;

Link$*$ curr $=$ front;

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

Link$*$ temp $=$ curr$->$next;

curr$->$next $=$ curr$->$prev;

curr$->$prev $=$ temp;

curr $=$ curr$->$next;

$\}$

$\}$

friend std::ostream& operator$<<<>($std::ostream& os$,$ const LinkedList& list$)$;

friend struct TestLinkedList;

$\}$;

#endif#ifndef QUEUE$\_$H

#define QUEUE$\_$H

#include "LinkedList.h$"$

template

class Queue;

template

std::ostream& operator$<<($std::ostream& os$,$ const Queue& q$)$;

template

class Queue$\{$

$//$ Your code here

$\}$;

template

std::ostream& operator$<<($std::ostream& os$,$ const Queue& q$)\{$

$//$ Your code here

$\}$

#endif#ifndef STACK$\_$H

#define STACK$\_$H

#include "LinkedList.h$"$

template

class Stack;

template

std::ostream& operator$<<($std::ostream& os$,$ const Stack& q$)$;

template

class Stack$\{$

$//$ Your code here

$\}$;

template

std::ostream& operator$<<($std::ostream& os$,$ const Stack& q$)\{$

$//$ Your code here

$\}$

#endif I don't know what i need to do for this.