Requirements:

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

1. A linked deque class: Linked_deque.

A linked deque 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_deque

Description

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

Member Variables

The class has four member variables:

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

Each array in the linked list will have a capacity of eight. When the deque is empty, the linked list is empty. As objects are placed into the deque, 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 deque 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 deque 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 deque 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 deque in Figure 2 after nine pops.

Member Functions

Constructors

The default constructor is used.

Copy constructor

Make a complete copy of the linked deque. 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 deque is empty. (O(1))

int size() const

Returns the number of objects currently in the deque. (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 deque. This member function may throw an underflow exception. (O(1))

Mutators

This class has six mutators:

void swap( Linked_deque & );

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

Linked_deque &operator=( Linked_deque & );

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_front( Type const & )

Push the argument onto the front of the deque:

• If the deque 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 deque is now one.
• If the front index already points to the first entry of the array, reset it to one less than the capacity, 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 last location.
• Otherwise, decrement the front index and place the argument at that location.

Increment the deque size. (O(1))

void push_back( Type const & )

Push the argument onto the back of the deque:

• If the deque 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 deque 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 deque size. (O(1))

Type pop_front()

Pop the front of the deque 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 deque 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))

Type pop_back()

Pop the back of the deque and decrement the iback index. If the back index equals -1, reset it to one less than the aray capacity, and pop the back of the linked list while deallocating the memory allocated to that array. If the deque 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.