deque

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;
}