Data Structures

Lab #3: Queues


During this activity, students will be able to:


This activity must be developed in the pre-assigned teams of two.

NOTE: The files needed to start this lab are available in this tarball file: queue.tgz. To uncompress, type at the Linux terminal:

tar xzf queue.tgz

In the queue.h file, create a generic class called Queue<T> with the operations described below. The class must be implemented using a circular array as explained in [STEPHENS]. The memory for the array must be dynamically allocated using the new operator and deallocated when appropriate using delete.

IMPORTANT: Before the definition of each operation you must include a comment that indicates its corresponding time complexity.

Operación Descripción
Queue(int capacity) Constructor. Create an empty queue. This requires dynamically allocating a circular array with the specified capacity.
~Queue() Destructor. Destroy this queue making sure that all its dynamically allocated memory is freed.
int capacity() const Member function. Returns the size of the circular array allocated for this queue.
void clear() Member function. Removes all the elements from this queue, leaving it empty.
T dequeue() Member function. Removes and returns the element at the front of this queue (its oldest element).
Throws a std::underflow_error exception if the queue is empty.
void enqueue(T value) Member function. Insert value at the end of this queue, after its current last element.
Throws a std::overflow_error exception if the queue has insufficient space.
bool is_empty() const Member function. Returns true if this queue is empty, or false otherwise.
T peek() const Member function. Returns the element at the front of this queue (its oldest element) without removing it.
Throws a std::underflow_error exception if the queue is empty.
int size() const Member function. Returns the number of elements contained in this queue.

Add the following declarations inside your class’ public section in order to avoid memory related issues produced by the default copy constructor and assignment operator:

Queue(const Queue& other) = delete;

Queue<T>& operator=(const Queue& other) = delete;

Test your code using the tests in the file tests.cpp (contains a total of 1,752 assertions). Also, run the code using valgrind to check for memory leaks and other memory related errors.


Place in a comment at the top of the queue.h source file the authors’ personal information (student ID and name), for example:

 * Lab #3: Queues
 * Implementation of the Queue class.
 * Date: 29-Sep-2023
 * Authors:
 *           A01770771 Kamala Khan
 *           A01777771 Carol Danvers

Upload Instructions

To deliver the queue.h file, please provide the following information:

Request PIN

Only one team member needs to upload the file.

Due date is Friday, September 29.