C++. Queues and Stacks

Stack class

The Stack class needs to use the DoubleLinkedList (or std::list) to implement the stack. Your Stack class

needs to be a template class:

template

class Stack

The Stack class needs to implement the following member functions:

bool empty() const

The empty member function will return true if the stack is empty.

std::size_t size() const

Returns the number of items in the stack.

DataType& top()

Returns a modifiable reference to the top item in the. Note, your member function can assume the stack

has at least one item, or you can throw an exception. The choice is yours.

const DataType& top() const

Returns a const reference to the top item in the stack. Note, your member function can assume the

stack has at least one item, or you can throw an exception. The choice is yours.

void push(const DataType& value)

Add a new item to the stack.

void pop()

Remove the first item from the queue. If the stack is empty you can display an error message, do

nothing, or throw an exception. The choice is yours.

Constructors and destructor

You will need a default constructor and a copy constructor and you will need a destructor.

The copy constructor needs to make a deep copy of the list. You should be able to use other member

functions to do most of the work for you.

Make sure your destructor removes any remaining items from the stack.

Other information

You can add other member functions as needed. Make sure you free up any memory you allocate.

Hopefully this is already being done for you by the DoubleLinkedList class.

You can inline trivial member functions in the Stack class (trivial being 1 or 2 lines of code).

You must implement all of the member functions shown here. You can implement additional private,

and protected member functions if you need them.

Create a header file named Stack.h that contains your Stack class definition and any implementation

code needed. Include the required header file include guards needed.

Please write a driver function (main) to test your Stack class. If you want to implement code that actually

uses the stack feel free to do so (for example, you could have an application that prints out the contents

of a linked list backwards). Make sure you try out all of the functions you have implemented. Also make

sure you test any errors that your program supports. For example, if you throw an exception in pop

when the stack or queue is empty make sure you test that. Test your pop() or back() functions throw

exceptions, or if they simply do nothing, or if they display an error message.

Queue class

The Queue class needs to use the DoubleLinkedList/std::list to implement the queue. Your Queue class

needs to be a template class:

template

class Queue

The Queue class needs to implement the following member functions:

bool empty() const

The empty member function will return true if the queue is empty.

std::size_t size() const

Returns the number of items in the queue.

DataType& front()

Returns a modifiable reference to the first item in the queue. Note, your member function can assume

the queue has at least one item, or you can throw an exception. The choice is yours.

const DataType& front() const

Returns a const reference to the first item in the queue. Note, your member function can assume the

queue has at least one item, or you can throw an exception. The choice is yours.

DataType& back()

Returns a modifiable reference to the last item in the queue. Note, your member function can assume

the queue has at least one item, or you can throw an exception. The choice is yours.

const DataType& back() const

Returns a const reference to the last item in the queue. Note, your member function can assume the

queue has at least one item, or you can throw an exception. The choice is yours.

void push(const DataType& value)

Add a new item to the back of the queue.

void pop()

Remove the first item from the queue. If the queue is empty you can display an error message, do

nothing, or throw an exception. The choice is yours.

Constructors and destructor

You will need a default constructor and a copy constructor and you will need a destructor.

The copy constructor needs to make a deep copy of the list. You should be able to use other member

functions to do most of the work for you.

Make sure your destructor removes any remaining items from the queue.

Other information

You can add other member functions as needed. Make sure you free up any memory you allocate.

Hopefully this is already being done for you by the DoubleLinkedList class.

You can inline trivial member functions in the Queue class (trivial being 1 or 2 lines of code).

You must implement all of the member functions shown here. You can implement additional private,

and protected member functions if you need them.

Create a header file named Queue.h that contains your Queue class definition and any implementation

code needed. Include the required header file include guards needed.

Update your driver function (main) to test your Queue class as well as your Stack class. If you want to

implement code that actually uses the queue feel free to do so. Make sure you try out all of the

functions you have implemented. Also make sure you test any errors that your program supports. For

example, if you throw an exception in pop when the stack or queue is empty make sure you test that.

Test your pop() or back() functions throw exceptions, or if they simply do nothing, or if they display an

error message.