Requirements:

In this sub-project, you will implement on class:

1. A linked queue class: Linked_queue.

A linked queue may be implemented using the linked list from Project 1 which allows appropriate insertions and deletions in O(1) time. If your Project 1 did not work, you are welcome to use the implementation of a friend—only you must acknowledge that individual.

Runtime:

The run time of each member function is specified in parentheses at the end of the description.

Class Specifications:

---

Linked_queue

Description

A class which implements a linked queue (in fact, two stacks) which has the specified behaviours. For run-time requirements, the number of elements in the queue is n.

Member Variables

The class has four member variables:

• A linked list of pointers to arrays of Type: Single_list<Type *> array_list (or whatever linked list you created in Project 1),
• An integer storing the queue size, and
• Two integers ifront and itail.

Each array in the linked list will have a capacity of eight. When the queue is empty, the linked list is empty. As objects are placed into the queue, they are placed into the arrays that will be stored in the linked list. As necessary, additional arrays are added to the linked list. For example, suppose we begin with an empty queue and then push six times and pop once. The result will appear as shown in Figure 1 where the member variables ifront = 1 and iback = 5.

Figure 1. The queue after six pushes and one pop.

Now, suppose that there is a sequence of fourteen pushes: when the array at the back of the linked list is filled, a new array is pushed onto the back of the linked list, and new entries are pushed into the array pointed to by that node. When this array also becomes filled, another array will be pushed onto the linked list. The member variables ifront and iback keep track of the locations in the first and last entries in their respective arrays. As shown in Figure 2, ifront = 1 and itail = 3 and the linked list has three entries.

Figure 2. The queue in Figure 1 after another fourteen pushes.

Suppose next there is a sequence of nine pops. After the seventh pop, the node at the front of the linked list would be popped and the memory for the array it points to would be deallocated and ifront would be reset to 0. After two more pops, ifront = 2, as shown in Figure 3.

Figure 3. The queue in Figure 2 after nine pops.

Member Functions

Constructors

The default constructor is used.

Copy constructor

Make a complete copy of the linked queue. For each array in the original linked list, a new array must be allocated and the entries copied over.

Destructor

The destructor will have to empty the linked list and deallocate the memory pointed to by the entries of the linked list.

Accessors

This class has three accessors:

bool empty() const

Returns true if the queue is empty. (O(1))

int size() const

Returns the number of objects currently in the queue. (O(1))

int list_size() const

Returns the number of nodes in the linked list data structure. This must be implemented as provided. (O(1))

Type front() const

Returns the object at the front of the queue. This member function may throw an underflow exception. (O(1))

Mutators

This class has four mutators:

void swap( Linked_queue & );

The swap function swaps all the member variables of this stack with those of the argument. (O(n))

Linked_queue &operator=( Linked_queue & );

The assignment operator makes a copy of the argument and then swaps the member variables of this node with those of the copy. (O(n_lhs + n_rhs))

void push( Type const & )

Push the argument onto the back of the queue:

• If the queue is empty, allocate memory for a new array with the required capacity, push the address of that array onto the linked list, set both indices to zero and place the new argument at that location. The size of the queue is now one.
• If the back index already points to the last entry of the array, reset it to zero, allocate memory for a new array with the required capacity, push the address of that array onto the linked list, and insert the argument into the first location.
• Otherwise, increment the back index and place the argument at that location.

Increment the queue size. (O(1))

Type pop()

Pop the front of the queue and increment the ifront index. If the front index equals the aray capacity, reset it to zero and pop the front of the linked list while deallocating the memory allocated to that array. If the queue is emptied, also pop the front of the linked list while deallocated the memory allocated to that array. This member function may throw a underflow exception. (O(1))

Friends

The class has no friends.