Write a C++ template class named \"dequeue.template\" based on the following hea

Question

Write a C++ template class named "dequeue.template" based on the following header declarations. Also write a test program to test every member functions implemented in the class.

// dequeue.h

#ifndef _DEQUE_H_

#define _DEQUE_H_

#include <iostream>

#include <cstdlib>

using namespace std;

template <class T>

class dequeue

{

public:

typedef size_t size_type;

static const size_type CAPACITY = 10;

//postcondition: empty deque has been created

dequeue();

//precondition: deque is not empty

// postcondition: reference to element at front of deque

// has been returned

T& front();

// precondition: deque is not empty

// postcondition: copy of element at front of deque

// has been returned

T front() const;

// precondition: deque is not empty

// postcondition: reference to element at front of deque

// has been returned

T& back();

// precondition: deque is not empty

// postcondition: copy of element at back of deque

// has been returned

T back() const;

// precondition: deque is not full

// postcondition: entry has been inserted at the front

// of the deque

void push_front (const T& entry);

// precondition: deque is not full

// postcondition: entry has been inserted at the back

// of the deque

void push_back (const T& entry);

// precondition: deque is not empty

// postcondition: element at front of deque has been removed

void pop_front();

// precondition: deque is not empty

// postcondition: element at back of deque has been removed

void pop_back();

// postcondition: number of elements in deque has been returned

size_type size() const;

// postcondition: whether deque is empty has been returned

bool empty() const;

// postcondition: whether deque is full has been returned

bool full() const;

// postcondition: returned whether 2 deques are equal - equal is defined

// as the deques have the same number of elements &

// corresponding elements are equal

template <class T>

friend bool operator == (const dequeue<T>& dq1, const dequeue<T>& dq2);

// postcondition: dq has been display from front to rear on out

template <class T>

friend ostream& operator<< (ostream& out, const dequeue<T>& dq);

private:

T data[CAPACITY]; // Circular array

size_type first; // Index of item at front of the queue

size_type last; // Index of item at rear of the queue

size_type count; // Total number of items in the queue

// postcondition: returned next index in array

size_type next_index(size_type i) const;

// postcondition: returned previous index in array

size_type prev_index (size_type i) const;

};

#include "dequeue.template"

#endif

Explanation / Answer

class template

<deque>

std::deque

Double ended queue

deque (usually pronounced like "deck") is an irregular acronym of double-ended queue. Double-ended queues are sequence containers with dynamic sizes that can be expanded or contracted on both ends (either its front or its back).

Specific libraries may implement deques in different ways, generally as some form of dynamic array. But in any case, they allow for the individual elements to be accessed directly through random access iterators, with storage handled automatically by expanding and contracting the container as needed.

Therefore, they provide a functionality similar to vectors, but with efficient insertion and deletion of elements also at the beginning of the sequence, and not only at its end. But, unlike vectors, deques are not guaranteed to store all its elements in contiguous storage locations: accessing elements in a deque by offsetting a pointer to another element causes undefined behavior.

Both vectors and deques provide a very similar interface and can be used for similar purposes, but internally both work in quite different ways: While vectors use a single array that needs to be occasionally reallocated for growth, the elements of a deque can be scattered in different chunks of storage, with the container keeping the necessary information internally to provide direct access to any of its elements in constant time and with a uniform sequential interface (through iterators). Therefore, deques are a little more complex internally than vectors, but this allows them to grow more efficiently under certain circumstances, especially with very long sequences, where reallocations become more expensive.

For operations that involve frequent insertion or removals of elements at positions other than the beginning or the end, deques perform worse and have less consistent iterators and references than lists and forward lists.

Template parameters

T

Type of the elements.
Aliased as member type deque::value_type.

Alloc

Type of the allocator object used to define the storage allocation model. By default, the allocator class template is used, which defines the simplest memory allocation model and is value-independent.
Aliased as

member type deque::allocator_type.

and the operator mentioned above like :: is called "SCOPE RESOLUTION OPERATOR"

   Ex:   

The :: (scope resolution) operator is used to qualify hidden names so that you can still use them. You can use the unary scope operator if a namespace scope or global scope name is hidden by an explicit declaration of the same name in a block or class. For example:

The declaration of count declared in the main() function hides the integer named count declared in global namespace scope. The statement ::count = 1 accesses the variable named count declared in global namespace scope.

You can also use the class scope operator to qualify class names or class member names. If a class member name is hidden, you can use it by qualifying it with its class name and the class scope operator.

Passing a template to deque :

}

Implementation of Deque in C++ :

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.