Màxim d'una pila X49526

Preliminars

En aquest exercici extendrem la classe Stack suposant que el tipus T dels elements de la pila té definits els operadors de comparació <, <=, ==, >, >=, !=, és a dir, que dues variables de tipus T es poden comparar sempre. (des d’un punt de vista algebraic, direm que hi ha un ordre total en els conjunt de valors de tipus T). També suposem que una variable x de tipus T té definit l’operador d’assignació =.

Com que en aquest exercici només instanciarem Stack de tipus int, totes dues coses ja estan garantides. Per tant, no us ha d’amoïnar.

Exercici

Implementeu un nou mètode de la classe Stack que retorni el màxim de tots els elements continguts a la pila.

D’entre els fitxers que s’adjunten en aquest exercici, trobareu stack.old.hpp, a on hi ha una implementació de la classe genèrica Stack. En primer lloc, haureu de fer:

cp stack.old.hpp stack.hpp

A continuació, haureu de buscar dins stack.hpp les següents línies:

    /*
     * Pre:  Sigui [a1,...,an] el contingut actual de la pila des 
     * del fons fins al top.
     * Post: Retorna el màxim de a1+...+an.
     * Descomenteu les següents tres línies i implementeu el mètode:
     */

    // T maxim() 
    // {
    // }

Descomenteu les tes línies que s’indiquen i implementeu el mètode. Potser necessitareu modificar més coses de la classe depenent de quin enfocament seguiu. Aquí us en recomanem dos:

• Enfocament senzill i ineficient: Una implementació senzilla consisteix en fer un mètode que cada vegada que el cridem recorri tota la pila i en calculi i retorni el màxim. Això hauria de ser suficient per a superar els jocs de proves públics, però no els privats.

• Enfocament eficient: Consisteix en crear una variable que contingui el màxim de la pila, i que cada vegada que fem un push i un pop se’n modifiqui el contingut (si calgués).

  Cal tenir en compte el fet que a la pila hi poden haver repetits, i potser l’element màxim també està repetit. Per tant, possiblement, apart de tenir una variable que indiqui quin és l’element màxim, també caldrà tenir una variable que indiqui quantes vegades és a la pila.

  Finalment, en algun cas, quan feu un pop, inevitablement caldrà fer un recorregut per tota la pila per a saber quin és el màxim i quantes vegades hi apareix, però globalment, seran menys vegades que amb la primera estratègia. Especialment, penseu que si en una pila no hi fem cap pop, aleshores aquesta estratègia serà molt més eficiant que l’anterior.

D’entre els fitxers que s’adjunten a l’exercici també hi ha program.cpp (programa principal) i Makefile per a compilar. Per a pujar la vostra solució, heu de crear el fitxer solution.tar així:

tar cf solution.tar stack.hpp

Entrada

L’entrada del programa és una seqüència d’instruccions del següent tipus que s’aniran aplicant sobre la pila:

push x (x és de tipus int)
pop
top
print
maxim

Se suposa que la seqüència d’entrada serà correcta (sense pop ni top ni maxim sobre pila buida).

El programa principal que us oferim ja s’encarrega de llegir aquestes entrades i fer les crides als corresponents mètodes de la classe pila. Només cal que implementeu el mètode abans esmentat.

Sortida

Per a cada instrucció top, s’escriurà el top actual de la pila, per a cada instrucció print, s’escriurà el contingut de la pila, i per a cada instrucció maxim, s’escriurà el màxim dels elements de la pila. El programa que us oferim ja fa això. Només cal que implementeu el mètode maxim.

Observació

Avaluació sobre 10 punts: (Afegiu comentaris si el vostre codi no és prou clar)

• Solució lenta: 4 punts.

• solució ràpida: 10 punts.

Entenem com a solució lenta una que és correcta i capaç de superar els jocs de proves públics. Entenem com a solució ràpida una que és correcta i capaç de superar els jocs de proves públics i privats.

IMPORTANT: Òbviament, a dins del mètode (o mètodes) que implementeu, no podeu fer servir els mètodes que ja té la pila ja té implementats. A més, us haureu d’assegurar que els mètodes que ja té implementats funcionen correctament després dels canvis que haureu aplicat a la classe Stack.