Afegir el mètode getLast a la classe Queue X63230


Statement
 

pdf   zip   tar

En aquest exercici afegirem el mètode getLast a la classe Queue. Simplement, retorna l’últim element de la cua, a diferència del mètode front, que en retorna el primer. Ambdós mètodes suposen, com a precondició, que la cua no està buida.

Per exemple, suposeu que la Queue q conté els elements [1,3,6][1,3,6] (on els elements els representem en ordre des del front fins el final, i en particular 66 és l’últim element de la cua). Una crida q.getLast() retorna 6, mentre que una crida q.front() retorna 1.

D’entre els fitxers que s’adjunten en aquest exercici, trobareu queue.hh, a on hi ha una implementació de la classe genèrica Queue. Haureu de buscar dins queue.hh el següent fragment, descomentar les línies que s’indiquen i implementar el mètode.

  // Pre: el paràmetre implícit representa una cua no buida.
  // Post: retorna l'últim element de la cua representada pel paràmetre implícit.
  // Remove "//" on the following two lines and implement the method.
  // T getLast() {
  // }

D’entre els fitxers que s’adjunten a l’exercici també hi ha main.cc (programa principal), i el podeu compilar directament, doncs fa include de queue.hh. Només cal que pugeu queue.hh al jutge.

Entrada

L’entrada del programa comença amb una declaració d’unes quantes cues d’enters (q0, q1, ...), i després té una seqüència de comandes sobre les cues declarades. Com que ja us oferim el main.cc, no cal que us preocupeu d’implementar la lectura d’aquestes entrades. Només cal que implementeu la extensió de la classe cua abans esmentada.

Se suposa que la seqüència d’entrada serà correcta (sense pop ni front ni getLast sobre cua 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 cua. Només cal que feu els canvis abans esmentats.

Sortida

Per a cada comanda d’escriptura sobre la sortida s’escriurà el resultat corresponent. El main.cc que us oferim ja fa això. Només cal que implementeu la extensió de la classe cua abans esmentada.

Observació

Avaluació sobre 10 punts:

  • Solució lenta: 5 punts.

  • solució ràpida: 10 punts.

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

Public test cases

  • Input

    Queue<int> q0 , q1 ;
q0 .push( 1 );
q0 .push( 3 );
q0 .push( 6 );
q1 .push( 6 );
q1 .push( 3 );
q1 .push( 1 );
cout<< q0 <<endl;
cout<< q1 <<endl;
cout<< q0 .size()<<endl;
cout<< q1 .size()<<endl;
cout<< q0 .front()<<endl;
cout<< q1 .front()<<endl;
cout<< q0 .getLast()<<endl;
cout<< q1 .getLast()<<endl;
q0 .push( 7 );
q1 .push( 7 );
cout<< q0 <<endl;
cout<< q1 <<endl;
cout<< q0 .size()<<endl;
cout<< q1 .size()<<endl;
cout<< q0 .front()<<endl;
cout<< q1 .front()<<endl;
cout<< q0 .getLast()<<endl;
cout<< q1 .getLast()<<endl;
q0 .pop();
q1 .pop();
cout<< q0 <<endl;
cout<< q1 <<endl;
cout<< q0 .size()<<endl;
cout<< q1 .size()<<endl;
cout<< q0 .front()<<endl;
cout<< q1 .front()<<endl;
cout<< q0 .getLast()<<endl;
cout<< q1 .getLast()<<endl;
q0 .push( 8 );
q1 .push( 2 );
cout<< q0 <<endl;
cout<< q1 <<endl;
cout<< q0 .size()<<endl;
cout<< q1 .size()<<endl;
cout<< q0 .front()<<endl;
cout<< q1 .front()<<endl;
cout<< q0 .getLast()<<endl;
cout<< q1 .getLast()<<endl;
q0 .pop();
q1 .pop();
cout<< q0 <<endl;
cout<< q1 <<endl;
cout<< q0 .size()<<endl;
cout<< q1 .size()<<endl;
cout<< q0 .front()<<endl;
cout<< q1 .front()<<endl;
cout<< q0 .getLast()<<endl;
cout<< q1 .getLast()<<endl;
q0 .pop();
q1 .pop();
cout<< q0 <<endl;
cout<< q1 <<endl;
cout<< q0 .size()<<endl;
cout<< q1 .size()<<endl;
cout<< q0 .front()<<endl;
cout<< q1 .front()<<endl;
cout<< q0 .getLast()<<endl;
cout<< q1 .getLast()<<endl;

    Output

    1 3 6
6 3 1
3
3
1
6
6
1
1 3 6 7
6 3 1 7
4
4
1
6
7
7
3 6 7
3 1 7
3
3
3
3
7
7
3 6 7 8
3 1 7 2
4
4
3
3
8
2
6 7 8
1 7 2
3
3
6
1
8
2
7 8
7 2
2
2
7
7
8
2

  • Input

    Queue<int> q0 , q1 , q2 ;
cout<< q1 .size()<<endl;
q0 .push( -38 );
q0 .pop();
cout<< q0 .size()<<endl;
cout<< q0 .size()<<endl;
cout<< q2 .size()<<endl;
q0 .push( 47 );
q1 .push( 20 );
cout<< q0 <<endl;
cout<< q1 .front()<<endl;
cout<< q2 .size()<<endl;
q0 .push( 50 );
cout<< q1 .size()<<endl;
q2 .push( -14 );
cout<< q1 .front()<<endl;
cout<< q0 .getLast()<<endl;
cout<< q0 .front()<<endl;
q2 .push( -9 );
cout<< q1 .size()<<endl;
q0 .push( 55 );
q0 .pop();
q0 .push( 51 );
cout<< q0 .front()<<endl;
cout<< q1 .front()<<endl;
q0 .push( 59 );
q0 .push( 56 );
q2 .push( -7 );
q0 .pop();
cout<< q0 .getLast()<<endl;
q1 .push( 20 );
cout<< q0 .getLast()<<endl;
cout<< q0 .size()<<endl;
cout<< q2 .getLast()<<endl;
q2 .pop();
q2 .push( -5 );
q0 .pop();
q2 .push( 0 );
cout<< q2 .getLast()<<endl;
q0 .pop();
q1 .push( 24 );
cout<< q1 .front()<<endl;
cout<< q2 .front()<<endl;
q2 .pop();
cout<< q1 .getLast()<<endl;
q1 .push( 19 );
q0 .push( 17 );
cout<< q2 .getLast()<<endl;
q2 .push( 5 );
q2 .pop();
cout<< q0 .size()<<endl;
q0 .push( 17 );
q2 .push( 2 );
cout<< q0 .getLast()<<endl;
cout<< q2 .size()<<endl;
cout<< q2 .size()<<endl;
cout<< q1 .getLast()<<endl;
q2 .pop();
q2 .push( 8 );
cout<< q2 .size()<<endl;
q1 .push( 19 );
cout<< q0 .getLast()<<endl;
cout<< q2 .size()<<endl;
cout<< q0 .getLast()<<endl;
cout<< q2 .size()<<endl;
q0 .pop();
q1 .push( 28 );
q1 .push( 26 );
cout<< q2 .front()<<endl;
cout<< q2 .size()<<endl;
q0 .push( 26 );
cout<< q2 .front()<<endl;
cout<< q0 .size()<<endl;
q0 .push( 30 );
cout<< q1 .getLast()<<endl;
q2 .push( 6 );
cout<< q1 .getLast()<<endl;
cout<< q1 .front()<<endl;
q0 .push( 35 );
cout<< q2 .size()<<endl;
cout<< q2 .size()<<endl;
q0 .pop();
q2 .push( 10 );
cout<< q2 .getLast()<<endl;
cout<< q0 <<endl;
cout<< q2 .front()<<endl;
cout<< q1 .front()<<endl;
q2 .pop();
cout<< q2 .front()<<endl;
cout<< q0 <<endl;
cout<< q1 .size()<<endl;
q2 .pop();
cout<< q0 .front()<<endl;
q0 .push( 31 );
q1 .push( 30 );
q1 .pop();
cout<< q1 .getLast()<<endl;
q0 .pop();
cout<< q2 .getLast()<<endl;
q2 .push( 13 );
q0 .push( 32 );
cout<< q1 .front()<<endl;
cout<< q2 .getLast()<<endl;
cout<< q0 .size()<<endl;
cout<< q2 .getLast()<<endl;
q0 .push( 33 );
q0 .push( 32 );
q2 .push( 18 );
cout<< q0 .front()<<endl;
cout<< q1 <<endl;
cout<< q1 .size()<<endl;
q1 .push( 29 );
cout<< q1 .front()<<endl;
cout<< q0 <<endl;
q0 .pop();
cout<< q1 .size()<<endl;
cout<< q2 .front()<<endl;
cout<< q0 .size()<<endl;
q2 .pop();
cout<< q1 <<endl;
cout<< q0 <<endl;
cout<< q0 .size()<<endl;
q2 .pop();
q1 .push( 26 );
cout<< q2 .size()<<endl;
q0 .push( -50 );
q0 .push( -53 );
cout<< q2 .getLast()<<endl;
cout<< q0 .size()<<endl;
q1 .push( 33 );
q2 .push( 20 );
q2 .push( 24 );
cout<< q1 .getLast()<<endl;
q1 .push( 35 );
q2 .push( 27 );
cout<< q2 .front()<<endl;
cout<< q0 .front()<<endl;
q2 .pop();
cout<< q0 .front()<<endl;
cout<< q1 .getLast()<<endl;
q2 .pop();
cout<< q2 <<endl;
cout<< q2 <<endl;
cout<< q2 .front()<<endl;
q0 .push( -48 );
q0 .pop();
q2 .push( 23 );
q2 .pop();
q2 .push( 31 );
q1 .push( 30 );
cout<< q1 .size()<<endl;
cout<< q1 .size()<<endl;
q1 .push( 32 );
cout<< q1 .size()<<endl;
cout<< q0 .front()<<endl;
q1 .push( 38 );
cout<< q2 .size()<<endl;
q1 .push( 38 );
cout<< q0 <<endl;
cout<< q1 .getLast()<<endl;
cout<< q0 .size()<<endl;
q0 .push( -44 );
q2 .pop();
q1 .push( 43 );
q0 .push( -42 );
cout<< q0 .getLast()<<endl;
cout<< q0 .getLast()<<endl;
q0 .pop();
q2 .push( 30 );
cout<< q1 .getLast()<<endl;
q0 .push( -45 );
q1 .pop();
cout<< q0 .getLast()<<endl;
cout<< q1 .getLast()<<endl;
cout<< q2 .front()<<endl;
cout<< q0 .getLast()<<endl;
cout<< q0 .getLast()<<endl;
q0 .pop();
q2 .pop();
q1 .pop();
q2 .pop();
q2 .push( 39 );
q1 .pop();
cout<< q2 .size()<<endl;
cout<< q0 .front()<<endl;
cout<< q2 .front()<<endl;
q2 .pop();
cout<< q1 .front()<<endl;
cout<< q1 .getLast()<<endl;
cout<< q0 .size()<<endl;
cout<< q0 .size()<<endl;
cout<< q1 .getLast()<<endl;
q2 .push( 9 );
cout<< q1 .size()<<endl;
cout<< q1 .size()<<endl;
q2 .pop();
q0 .push( -37 );
q0 .pop();
cout<< q0 .size()<<endl;
q0 .pop();
q2 .push( -9 );
cout<< q0 .size()<<endl;
cout<< q0 <<endl;
cout<< q1 <<endl;
cout<< q2 <<endl;

    Output

    0
0
0
0
47
20
0
1
20
50
47
1
50
20
56
56
4
-7
0
20
-9
24
0
3
17
4
4
19
4
17
4
17
4
0
4
0
4
26
26
20
5
5
10
17 17 26 30 35
0
20
5
17 17 26 30 35
7
17
30
10
20
13
6
13
17
20 24 19 19 28 26 30
7
20
17 26 30 35 31 32 33 32
8
2
7
20 24 19 19 28 26 30 29
26 30 35 31 32 33 32
7
4
18
9
33
6
26
26
35
13 18 20 24 27
13 18 20 24 27
13
12
12
13
30
6
30 35 31 32 33 32 -50 -53 -48
38
9
-42
-42
43
-45
43
20
-45
-45
5
31
27
19
43
10
10
43
13
13
10
9
33 32 -50 -53 -48 -44 -42 -45 -37
19 28 26 30 29 26 33 35 30 32 38 38 43
31 30 39 9 -9
    • Information
    Author
    PRO2
    Language
    Catalan
    Official solutions
    Unknown.
    User solutions
    C++