Riestainiai (2014)
Taškai: 6
Du draugai dirba kepykloje. Lina kepa riestainius, traukia iš krosnies po tris skirtingų formų ir kabina juos ant strypo iš dešinės: pirmiausia pakabina A riestainį, tada – B ir galiausiai O. Linas pardavinėja nuo strypo imdamas visuomet patį dešiniausią riestainį. Lina kepa greičiau, negu Linas juos pardavinėja.
Kiek mažiausiai riestainių pardavė Linas, jei strypas atrodo taip, kaip parodyta paveikslėlyje?
A. 5 riestainius
B. 7 riestainius
C. 9 riestainius
D. 11 riestainių
Šioje užduotyje parodoma duomenų struktūros, vadinamos dėklu (angl. stack), tvarkymas.
Naudojantis dėklu, elementai gali būti dedami tik ant viršutinės pozicijos, o imama tik nuo viršaus. Angliškai dėklas dar vadinamas LIFO duomenų struktūra (last in first out), kas reiškia, jog paskutinysis į struktūrą padėtas elementas bus paimtas pirmas.
Teisingas atsakymas C – parduoti 9 riestainiai.
Jei palyginsite paveikslėlyje pavaizduotą dėklą su „pilnu“ (tarus, kad nei vienas riestainis nebuvo parduotas), galėsite suskaičiuoti praleistus riestainius. Mažiausiai 9 buvo parduoti: ABOABOABOABOABOABO (nubraukti yra parduoti, paryškinti – likę).