Deque

Requirements:

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

  1. Deque: Deque.

A deque stores elements in an ordered list and allows insertions and deletions at both the front and back of the list in O(1) time.

The elements in this deque are stored in an array.

Runtime:

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

Class Specifications:

Deque

Description

A class which implements a deque using an array. The capacity of the array is fixed at initialization time. For run-time requirements, the number of elements in the deque is n. The array is considered to be full if all entries in the array are assigned.

Member Variables

The class at least six members:

  • A pointer to an instance of Type, Type *array, to be used as an array,
  • A head index int ihead,
  • A tail index int itail,
  • A counter int entry_count,
  • The capacity of the array, int array_capacity.

Member Functions

Constructors

Deque( int n = 10 )

The constructor takes as an argument the capacity of the array and allocates memory for that array. The default initial capacity of the array is 10. If the argument n is less than one, use an array capacity of 1. Other class members are assigned as appropriate.

Destructor

~Deque()

The destructor deletes the memory allocated for the array.

Copy Constructor

Deque( Deque const & )

The copy constructor creates a new instance of the deque. (O(n))

Accessors

This class has five accessors:

Type head() const
Return the object at the head of the deque. It may throw a underflow exception). (O(1))
Type tail() const
Returns the object at the tail of the deque. It may throw a underflow exception. (O(1))
int size() const
Returns the number of elements currently stored in the deque. (O(1))
bool empty() const
Returns true if the stack is empty, false otherwise. (O(1))
int capacity() const
Returns the capacity of the deque. (O(1))

Mutators

This class has seven mutators:

void swap( Deque & );
The swap function swaps all the member variables of this deque with those of the argument. (O(1))
Deque &operator=( 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(max{nlhs, nrhs}))
void enqueue_head( Type const & )
Insert the new element at the head of the deque. This may throw a overflow exception. (O(1))
void enqueue_tail( Type const & )
Inserts the new element at the tail of the deque. This may throw a overflow exception. (O(1)).
Type dequeue_head()
Removes the element at the head of the deque. This may throw a underflow exception. (O(1))
Type dequeue_tail()
Removes the element at the tail of the deque. This may throw a underflow exception. (O(1))
void clear()
Removes all the elements in the deque. (O(1))

Friends

The class has no friends.