Deque V79239

En aquest exercici cal completar la implementació d’una estructura de dades anomenada Deque<T>. (La llibreria estàndard de C++ conté una classe deque però la implementació que fem en aquest exercici n’és una simplificació.)

Un Deque<T> (double-ended queue) funciona com una pila i una cua alhora. Podem introduir elements a l’inici (push_front) i també al final (push_back), i eliminar elements de l’inici (pop_front) i també del final (pop_back). Per tant, els mètodes push i pop, que a la pila i la cua afegeixen i eliminen elements d’un sol extrem, ara han d’indicar de quin extrem es tracta, i n’hi ha dos per a cada costat.

Amb la finalitat de poder aprofitar la implementació de Queue i simplement afegir operacions noves, hem usat queue.hh de base i hem canviat la implementació de Item, que ara també té un apuntador a l’element anterior. És a dir, l’estructura de nodes és equivalent a la de Queue, però està doblement enllaçada.

Primer familiaritza’t amb la classe Deque<T>, i després implementa els dos mètodes nous següents:

1. Un mètode públic que elimini l’últim element del Deque<T> (pop_back). La declaració és la següent:

/**
 * @brief  El Deque<T> (p.i.) perd l'últim element si no està buit. 
 *         Si està buit, s'aborta l'execució i s'envia un 
 *         missatge d'error.
 *
 * @pre   El Deque<T> (p.i.) no està buit.
 * @post  El Deque<T> perd l'últim element.
 */
void pop_back();

2. Un mètode públic que afegeixi un element pel principi (pel "front"), del Deque<T> (push_front). La declaració és la seguent:

/**
 * @brief  Afegeix un element al principi del Deque<T> (el "front").
 *
 * @param x L'element a afegir.
 * @post  El Deque<T> (p.i.) té un element més al principi i el nou 
 *        element té el valor `x`.
 */
void push_front(const T& x);

Observació

Per poder avaluar l’ús de punters, no useu altres mètodes, ni públics ni privats de la classe per resoldre el problema, accediu sempre als membres privats directament.

Si teniu dubtes sobre com produir el missatge d’error, mireu com es fa a les operacions que ja us donem implementades.

Els jocs de prova estan separats en dos grups per poder treballar per separat en cada mètode. Un grup de jocs de prova inclou crides als mètodes existents de Deque<T> i també push_front; i l’altre grup inclou crides als mètodes de Deque<T> i també pop_back.

Els fitxers públics (icona del gatet) contenen:

Per lliurar només cal enviar el fitxer deque.hh modificat.

Entrada

De l’entrada ja s’encarrega el programa principal. L’entrada està formada per diferents operacions sobre el Deque<T>: push_back, push_front, pop_back, pop_front, size, front, back, write_deque, acabades amb end.

Sortida

De la sortida també s’encarrega el programa principal. La sortida mostra els resultats de les operacions de consulta i l’estat del Deque<T> quan se sol·licita.