In this assignment, you need to design a queue that supports push and pop operations in the

front, middle, and back. We already gave you a draft FrontMiddleBackQueue.cpp code to start

with. You need to use the linked List implementation of queues. You need to complete the

undefined functions in this file and submit the complete code.

Specifically, you need to Implement theFrontMiddleBack class and its methods:

FrontMiddleBack$()$ Initializes the queue.

void pushFront$($int val$)$ Adds val to the front of the queue.

void pushMiddle$($int val$)$ Adds val to the middle of the queue.

void pushBack$($int val$)$ Adds val to the back of the queue.

int popFront$()$ Removes the front element of the queue and returns it$.$ If the queue is

empty, return $-1.$

int popMiddle$()$ Removes the middle element of the queue and returns it$.$ If the queue is

empty, return $-1.$

int popBack$()$ Removes the back element of the queue and returns it$.$ If the queue is

empty, return $-1.$

void reverse$()$ Reverse the queue

Note: For pushMiddle and popMiddle functions, when there are two middle position choices, the

operation is performed on the frontmost middle position choice. For example:

Pushing $4$ into the middle of $123$ results in $1423$

Poping the middle of $1423$ results Examples:

$//$current queue q: $12$

q$.$pushMiddle$(3)$; $//132$

q$.$pushMiddle$(4)$; $//1432$

q$.$popFront$()$; $//$ return $1$ and remove $1->432$

q$.$reverse$()$; $//234$

q$.$popMiddle$()$; $//$ return $3$ and remove $3->24$

q$.$popMiddle$()$; $//$ return $2$ and remove $2->4$

q$.$popBack$()$; $//$ return $4$ and remove $4->$

q$.$popFront$()$; $//$ return $-1($The queue is

empty$)$in $123$

How to test:

In FrontMiddleBackQueue.cpp$,$ you can find a main$()$ function including some test cases. After

completing the code, you need to get the following output by running that main$()$ function.

$624513$

$6$

$5$

$3$

$4$

$21$

$-1$

$-1$

$-1$

$1$

$1$

$1$

$1234$

FrontMiddleBackQueue.cpp file

#include

using namespace std;

class Node $\{$

public:

int val;

Node$*$ next;

Node$($int x$)\{$

val $=$ x;

next $=$ NULL;

$\}$

$\}$;

class FrontMiddleBackQueue $\{$

public:

Node $*$front$,*$back;

int size;

FrontMiddleBackQueue$()\{$

$\}$

void pushFront$($int val$)\{$

$\}$

void pushMiddle$($int val$)\{$

$\}$

void pushBack$($int val$)\{$

$\}$

int popFront$()\{$

$\}$

int popMiddle$()\{$

$\}$

int popBack$()\{$

$\}$

void reverse$()\{$

$\}$

$\}$;

int main$()\{$

FrontMiddleBackQueue q;

$//$ Test case $1$: Pushing elements to the front, middle, and back of the queue

q$.$pushFront$(1)$; $//1$

q$.$pushMiddle$(2)$; $//21$

q$.$pushBack$(3)$; $//213$

q$.$pushMiddle$(4)$; $//2413$

q$.$pushMiddle$(5)$; $//24513$

q$.$pushFront$(6)$; $//624513$

$//$ Expected output: $624513$

Node$*$ temp $=$ q$.$front;

while$($temp$)\{$

cout $<<$ temp$->$val $<<""$;

temp $=$ temp$->$next;

$\}$

cout $<<$ endl;

$//$ Test case $2$: Popping elements from the front, middle, and back of the queue

cout $<<$ q$.$popFront$()<<$ endl; $//$ Expected output: $6$

cout $<<$ q$.$popMiddle$()<<$ endl; $//$ Expected output: $5$

cout $<<$ q$.$popBack$()<<$ endl; $//$ Expected output: $3$

cout $<<$ q$.$popMiddle$()<<$ endl; $//$ Expected output: $4$

$//$ Expected output after popping: $21$

temp $=$ q$.$front;

while$($temp$)\{$

cout $<<$ temp$->$val $<<""$;

temp $=$ temp$->$next;

$\}$

cout $<<$ endl;

$//$ Edge case: Popping elements from an empty queue

FrontMiddleBackQueue q$2$;

cout $<<$ q$2.$popFront$()<<$ endl; $//$ Expected output: $-1$

cout $<<$ q$2.$popMiddle$()<<$ endl; $//$ Expected output: $-1$

cout $<<$ q$2.$popBack$()<<$ endl; $//$ Expected output: $-1$

$//$ Edge case: Popping elements from a queue of size $1$

FrontMiddleBackQueue q$3$;

q$3.$pushFront$(1)$;

cout $<<$ q$3.$popFront$()<<$ endl; $//$ Expected output: $1$

q$3.$pushFront$(2)$;

cout $<<$ q$3.$popMiddle$()<<$ endl; $//$ Expected output: $2$

q$3.$pushFront$(3)$;

cout $<<$ q$3.$popBack$()<<$ endl; $//$ Expected output: $3$

FrontMiddleBackQueue q$4$;

$//$ Test case $3$: reversing the queue

q$4.$pushFront$(1)$;

q$4.$pushFront$(2)$;

q$4.$pushFront$(3)$;

q$4.$pushFront$(4)$;

q$4.$reverse$()$;

temp $=$ q$4.$front;

while$($temp$)\{$

cout $<<$ temp$->$val $<<""$;

temp $=$ temp$->$next;

$\}$

cout $<<$ endl;

return $0$;

$\}$