Doble cua (deque) implementada amb una llista doblement encadenada, amb fantasma i circular X82275

La classe doble cua (en anglès double-ended queue o abreviadament deque) és una classe que permet fer insercions, supressions i consultes en els dos extrems de la cua. És a dir, ha de disposar de les següents operacions (mira el PDF de l’enunciat):

Donada la classe $deque$ que permet guardar elements en una doble cua implementada amb una llista doblement encadenada, amb fantasma i circular, cal implementar els mètodes:

    void push(T e);
    // Pre: True
    // Post: Insereix un element al davant de la deque.

    void inject(T e);
    // Pre: True
    // Post: Insereix un element al darrera de la deque.

    void pop();
    // Pre: La deque no és buida.
    // Post: Elimina el primer element de la deque.

    void eject();
    // Pre: La deque no és buida.
    // Post: Elimina l’últim element de la deque.

Pots veure exemples de cada mètode en els jocs de prova públics. Cal enviar a jutge.org la següent especificació de la classe $deque$ i la implementació dels quatre mètodes anteriors dins del mateix fitxer (la resta de mètodes públics ja estan implementats en el fitxer $main.cc$). Indica dins d’un comentari a la capçalera de cada mètode el seu cost en funció del nombre d’elements $n$ de la deque.

#include <cstddef>
using namespace std;
typedef unsigned int nat;

template <typename T>
class deque {
  public:
    deque();
    // Pre: True
    // Post: El p.i. és una deque buida.

    deque(const deque &dq);
    // Pre: True
    // Post: El p.i. conté una còpia de dq.

    ~deque();
    // Post: Destrueix els elements del p.i.

    nat size() const;
    // Pre: True
    // Post: Retorna el nombre d'elements de la deque.

    bool empty() const;
    // Pre: True
    // Post: Retorna true si la deque és buida; false en cas contrari.

    T front() const;
    // Pre: La deque no és buida.
    // Post: Retorna el primer element de la deque.

    T rear() const;
    // Pre: La deque no és buida.
    // Post: Retorna l’últim element de la deque.

    void push(T e);
    // Pre: True
    // Post: Insereix un element al davant de la deque.

    void inject(T e);
    // Pre: True
    // Post: Insereix un element al darrera de la deque.

    void pop();
    // Pre: La deque no és buida.
    // Post: Elimina el primer element de la deque.

    void eject();
    // Pre: La deque no és buida.
    // Post: Elimina l’últim element de la deque.

  private:
  /* Double-ended queue implementada amb una llista doblement encadenada,
     amb fantasma i circular. */
    struct node {
      T info;    // Informació del node
      node *seg; // Punter al següent element
      node *ant; // Punter a l'anterior element
    };
    node *_prim; // Punter al fantasma
    nat _long;   // Nombre d'elements

    // Aquí va l'especificació dels mètodes privats addicionals
};

// Aquí va la implementació dels mètodes públics i privats addicionals

Degut a que jutge.org només permet l’enviament d’un fitxer amb la solució del problema, en el mateix fitxer hi ha d’haver l’especificació de la classe i la implementació dels mètodes que falten (el que normalment estarien separats en els fitxers $.hpp$ i $.cpp$).

Per testejar la solució, jutge.org ja té implementats la resta de mètodes de la classe $deque$ i un programa principal que crea una deque d’enters i processa comandes que executen els diferents mètodes de la classe.

Entrada

L’entrada conté vàries comandes, una per línea, amb el següent format (e és un enter):

• size

• empty

• front

• rear

• push e

• inject e

• pop

• eject

• mostra

• mostra_invertida

Sortida

Per a cada línia d’entrada, escriu una línia amb la comanda d’entrada, el separador ": " i el resultat de la comanda.

El resultat de les comandes $push$ i $inject$ és el mateix element inserit, el resultat de les comandes $pop$ i $eject$ és l’element que s’eliminarà. La comanda $mostra$ envia tots els elements al canal de sortida entre claudàtors i separats per espais. La comanda $mostra\_invertida$ és similar a $mostra$ però els envia al revés, començant amb el darrer i acabant amb el primer.

Observació

Només cal enviar la classe requerida i la implementació dels mètodes que falten. Pots ampliar la classe amb mètodes privats. Segueix estrictament la definició de la classe de l’enunciat.

Les comandes $mostra$ i $mostra\_invertida$ criden als mètodes $pop$ i $eject$ respectivament. Fins que aquests mètodes no estiguin ben implementats, no es mostraran correctament els elements de la deque per pantalla.

Indica dins d’un comentari a la capçalera de cada mètode el seu cost en funció del nombre d’elements $n$ de la deque.