In the

C++ STL (

Standard Template Library), a deque (pronounced "deck") is a double-ended

queue. A deque is designed so that insertions at the

start and

end are as efficient as they are in a

list, but the

subscripting efficiency approaches that of a

vector.

Insertions and deletions in the middle are as inefficient as they are in a vector rather than as efficient as a list, so a deque is only used where most operations will be performed at the ends.

Deque is a template class, so when you define one you need to provide the type (T). To define a deque of ints, write the following:

`deque<int> numbers;`

The following is a simple deque implementation that uses templates so it can store any object. As you can see, the PushBack and PushFront functions are a lot more efficient than InsertAfter, which is a mid-structure insertion.

template<class T> struct Node {
T Data;
Node* Next;
Node* Last;
Node();
};
template<class T> class MyDeque {
private:
Node<T>* Front;
Node<T>* Rear;
bool Empty;
public:
void PushBack(T);
T PopBack(void);
void PushFront(T);
T PopFront(void);
bool InsertAfter(T, int);
bool AmIEmpty(void);
MyDeque();
~MyDeque();
};
template<class T> Node<T>::Node() {
Last = Next = 0;
}
template<class T> MyDeque<T>::MyDeque() {
Front = 0;
Rear = 0;
Empty = true;
}
template<class T> MyDeque<T>::~MyDeque() {
Node<T>* Next;
while( Front != 0 ) {
Next = Front->Last;
delete Front;
Front = Next;
}
}
template<class T> void MyDeque<T>::PushBack( T ElementToAdd ) {
Node<T>* NewNode = new Node<T>;
NewNode->Last = 0;
NewNode->Data = ElementToAdd;
if (! Empty ) {
NewNode->Next = Rear;
Rear->Last = NewNode;
} else {
Front = NewNode;
Empty = false;
}
Rear = NewNode;
}
template<class T> T MyDeque<T>::PopBack() {
if (! Rear )
return NULL;
Node<T>* OldRear = Rear;
T Data = Rear->Data;
if ( Front == Rear )
Front = 0;
if ( Rear->Next == 0 ) {
Empty = true;
Rear = 0;
} else {
Node<T>* NewRear = Rear->Next;
Rear = NewRear;
Rear->Last = NULL;
}
delete OldRear;
return Data;
}
template<class T> void MyDeque<T>::PushFront( T ElementToAdd ) {
Node<T>* NewNode = new Node<T>;
NewNode->Next = 0;
NewNode->Data = ElementToAdd;
if (! Empty ) {
NewNode->Last = Front;
Front->Next = NewNode;
} else {
Rear = NewNode;
Empty = false;
}
Front = NewNode;
}
template<class T> T MyDeque<T>::PopFront() {
if (! Front )
return NULL;
T Data = Front->Data;
Node<T>* OldFront = Front;
if ( Front == Rear )
Rear = 0;
if ( Front->Last == 0 ) {
Empty = true;
Front = 0;
} else {
Node<T>* NewFront = Front->Last;
Front = NewFront;
Front->Next = 0;
}
delete OldFront;
return Data;
}
template<class T> bool MyDeque<T>::InsertAfter(T ElementToAdd, int Place) {
Node<T>* Next = Rear;
for( int i = 0; i < Place; i++ ) {
if ( Next->Next == 0 )
return false;
Next = Next->Next;
}
Node<T>* NewNode = new Node<T>;
NewNode->Data = ElementToAdd;
NewNode->Last = Next;
NewNode->Next = Next->Next;
Next->Next = NewNode;
NewNode->Next->Last = NewNode;
return true;
}
template<class T> bool MyDeque<T>::AmIEmpty() {
return Empty;
}