An Interface for an Int Queue

It may seem obvious that the most fundamental operations of a queue are ENQUEUE and DEQUEUE, but there are many choices to make in the design of an interface, including:

• Naming — What exactly should we call these operations?
• Error handling — What guarantees do we want to provide if the user misuses the data structure?
• Range of Operations — What other operations should we provide?
• Complexity — How efficient do we want these operations to be?

Naming

In this assignment, we'll adopt the same member-function naming conventions that the C++ Standard Library uses for list-like data structures. In particular, this choice means we'll have to forgo the usual camelCase naming convention that we use for member functions, and instead use snake_case naming.

We'll stick to our usual naming conventions for the class name itself (IntList), and for its data members.

Error Handling

In the previous assignment, we required that your code throw an exception if the user used the data structure incorrectly (e.g., trying to access an invalid index of a list or popping when the list was empty). In this assignment, we will adopt an approach more typical in C++ standard library data structures, namely that misuse is forbidden. From an interface perspective, it is not specified what happens if the user misuses the data structure.

Operations & Complexity

We'll provide the following fundamental operations for our data structure so that it can be used as a queue:

q.push_back(value)

Add value to the end of the list (the back of the queue).

q.pop_front()

Remove value at the front of the list (the front of the queue). Does not return it, just removes it. (Popping from an empty list is misuse.)

q.front()

Return (but do not remove) the value at the front of the list. (Asking for the front item of an empty list is misuse.)

q.empty()

Return whether the list is empty.

While the abstract ENQUEUE operation maps to push_back, performing a DEQUEUE operation maps to front followed by pop_front.

In addition to these fundamental operations, we'll also provide:

(default constructor)

Create an empty list.

q.push_front(value)

Add value to the front of the list. (This is not a queue operation, in fact it allows our data structure to be used as a stack, but it's a useful operation to have.)

q.size()

Return the number of elements in the list.

q.clear()

Remove all elements from the list.

q.swap(other)

Exchange the contents of this list with another list.

With the exception of q.clear(), all the operations we've listed must run in constant time. Clearing the list requires time proportional to the number of elements in the list, since each element must be destroyed.

Building Test Cases

When it comes time for you to write your IntList class, it would be nice to have some test cases to check that it works correctly. In the previous assignment, we provided you with prewritten test cases for the CoordVector class, but in this assignment, we want you to write your own test cases for the IntList class.

Your Task, Part 1

In intlist-test.cpp, write test cases to check the behavior of the IntList class, based on the interface specified here. For now, use IntVector in place of IntList, so that you can run your test cases and check that they work.

Test the following aspects of the interface:

• The fundamental operations (push_back, pop_front, front, and empty).
• The additional operations (default constructor, push_front, size, clear, and swap).

You do not need to test the complexity of the operations (that would be hard to do in a test case!), nor should you test misuse (since we don't specify what happens in that case). If you do misuse the IntVector class, strange things may happen.

Your Task, Part 2

In intlist.hpp, you'll find declarations of many of the functions we've talked about here, but they're lacking docstring comments. Add docstring comments to each function declaration, describing what the function does, its parameters, return value, rules for usage, and complexity.

There are also a few key functions that are missing entirely. Add declarations for the missing functions, along with docstring comments. (You don't need to implement any of the functions yet, just declare them.)

(When logged in, completion status appears here.)

Previous Page Next Page